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

help
1

#include
#include
#include
#include
#include
#include
#include
#include
#include

#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–;
if(qy==“ask”){

//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;

}

2
3

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

4

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…

5

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

6

My accepted submission:

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

// ask = 1
// 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;
		if(query_type == "ask") {
			queries[i].query_type = 1;
		}
		else {
			queries[i].query_type = 2;
		}
		queries[i].a = a;
		queries[i].b = b;
	}

	DSU dsu(N);

	stack<string> answer;
	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);
		}
	}

	while(!answer.empty()) {
		cout << answer.top() << '\n';
		answer.pop();
	}

	return 0;
}
7

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

1 Like
8

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

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

1 Like