# D. Cutting a graph https://codeforces.com/edu/course/2/lesson/7/1/practice/conte

#define ll long long
#define skip cin>>ws;
#define vll vector
#define vi vector
#define vb vector
#define vpll vector<pair<ll,ll>>
#define vvll vector<vector>
#define vvi vector<vector>
#define pll pair<ll,ll>
#define vs vector
#define vvpll vector<vector<pair<ll, ll>>>
#define pb push_back
#define pob pop_back()
#define MOD (ll)(1e9)
#define MOD2 (ll)(998244353)
#define INF (ll)(1e18 + 5)
#define count1(n) __builtin_popcountll(n)
#define test ll t; cin>>t; while(t–)
#define enter(a) for(ll i=0;i<a.size();i++) cin>>a[i];
#define show(a) for(ll e: a) cout<<e<<" “; cout<<”\n";

using namespace std;

ll mo(ll a){ return a%MOD;}

ll po(ll x, ll y, ll p)
{
ll res = 1; x = x % p;
while (y > 0) { if (y & 1) res = (res * x) % p; y >>= 1; x = (x * x) % p; }
return res%p;
}

struct dsu
{
int n;
vll a, rank, siz;

void init(ll si)
{
n = si;
a.resize(n); rank.resize(n); siz.assign(n, 1);
for(ll i=0;i<n;i++)
{
rank[i] = 1; a[i] = i;
}
}

ll get(ll i)
{
return a[i] = ((i==a[i])?i:get(a[i]));
}

void unio(ll i, ll j)
{
ll x = get(i), y = get(j);
if(x==y) return;
if(rank[x]==rank[y]) rank[x]++;
if(rank[y]>rank[x]) swap(x, y);
a[y] = x;
siz[x] += siz[y];
}

ll get_size(ll i)
{
return siz[get(i)];
}


};

struct ed
{
ll x, y;
};
struct query{
string q;
ll x,y;
};

int main()
{

//freopen(“input.txt”,“r”,stdin),freopen(“output.txt”,“w”,stdout);

ios_base::sync_with_stdio(false);
cin.tie(NULL);


ll n,m,k;
cin>>n>>m>>k;
ed edge[m+1];
query qt[k+1];
for(ll i=0;i<m;i++)
{cin>>edge[i].x>>edge[i].y;}
for(ll i=0;i<k;i++){
cin>>qt[i].q>>qt[i].x>>qt[i].y;
}

dsu dt;
vector ans;
dt.init(n);
for(ll i=(k-1);i>=0;i–){
string qy=qt[i].q;
ll x=qt[i].x;
ll y=qt[i].y;
x–,y–;

//cout<<x<<" "<<y<<endl;
if(dt.get(x)==dt.get(y)){
ans.pb(“YES”);

}else{
ans.pb(“NO”);
}}else{

dt.unio(x,y);
}
}

for(ll i=ans.size()-1;i>=0;i–){
cout<<ans[i]<<endl;
}

// cout<<ans<<"\n";

return 0;


}

it was my code i am try many times but .every time i was getting runtime error can anyone tell that what is wrong in my code

Has anyone got the algorithm of this problem? If so, pls explain it briefly.

I have an idea for “cut” part, but that seems to be linear in time…

I heard this phrase: \text{Offline queries}. It was given that the graph contains no edges at the end. This information should be a hint for \text{Offline queries}.

Offline Queries: What is an offline solution? - Codeforces

Btw, here is the link for the problem: Courses - Codeforces

My accepted submission:

CPP Code
#include <bits/stdc++.h>
using namespace std;

// cut = 2

#define yes "YES"
#define no "NO"

typedef struct query {
int query_type, a, b;
}query;

class DSU {
public:
int size = 0;
vector<int> parent;
vector<int> weight;

DSU(int N) {
size = N + 1;
parent.resize(size);
weight.resize(size, 1);
iota(parent.begin(), parent.end(), 0);
}

int get(int a) {
int p = parent[a];
for(; parent[p] != p; p = parent[parent[p]]);
for(int b = parent[a]; a != p; parent[a] = p, a = b, b = parent[a]);
return p;
}

bool connected(int a, int b) {
return get(a) == get(b);
}

void join(int a, int b) {
int parent_of_a = get(a);
int parent_of_b = get(b);
if(parent_of_a == parent_of_b) {
return;
}
if(weight[parent_of_a] < weight[parent_of_b]) {
parent[parent_of_a] = parent[parent_of_b];
weight[parent_of_b] += weight[parent_of_a];
}
else {
parent[parent_of_b] = parent[parent_of_a];
weight[parent_of_a] += weight[parent_of_b];
}
}
};

int main() {
int N = 0, M = 0, K = 0;
cin >> N >> M >> K;
for(int i = 0; i < M; i++) {
int a = 0, b = 0;
cin >> a >> b;
}
vector<query> queries(K);
for(int i = 0; i < K; i++) {
string query_type;
int a = 0, b = 0;
cin >> query_type >> a >> b;
queries[i].query_type = 1;
}
else {
queries[i].query_type = 2;
}
queries[i].a = a;
queries[i].b = b;
}

DSU dsu(N);

for(int i = K - 1; i >= 0; i--) {
if(queries[i].query_type == 1) {
answer.push(dsu.connected(queries[i].a - 1, queries[i].b - 1) ? yes: no);
}
else {
dsu.join(queries[i].a - 1, queries[i].b - 1);
}
}

}

return 0;
}


This is just reversing all the queries and then doing DSU.

1 Like

Thankyou @suman_18733097 @leo_valdez , now it seems I can solve it further.

Didn’t heard of offline queries before, but sounds like a great thing!

1 Like