SPOJ, C++ (gcc) - rextester

Language: Layout:

#include <bits/stdc++.h>

using namespace std;

#define mp make_pair
#define pii pair<int, int>
#define F first
#define pb push_back
#define S second

struct DSU_ROLLBACKS{
	int u, v;
	int sz_u, sz_v, p_u, p_v;

DSU_ROLLBACKS(int _u, int _v, int _sz_u, int _sz_v, int _p_u, int _p_v) : u(_u), v(_v), sz_u(_sz_u), sz_v(_sz_v), p_u(_p_u), p_v(_p_v){}
};

struct DSU{
	vector<int> p, sz;
	int n, comps;
	stack<DSU_ROLLBACKS> roll;

DSU(int x) : n(x), comps(n){
		p.resize(n+1, 0);
		sz.resize(n+1, 1);
		for(int j = 1; j <= n; j++) p[j] = j;
	}

int par(int u){
		return (p[u] == u)? u : par(p[u]);
	}

void rollback(){
		assert(!roll.empty());
		DSU_ROLLBACKS lst = roll.top();
		comps ++;
		roll.pop();
		sz[lst.u] = lst.sz_u;
		sz[lst.v] = lst.sz_v;
		p[lst.u] = lst.p_u;
		p[lst.v] = lst.p_v;
	}

int merge(int u, int v){
		int p1 = par(u);
		int p2 = par(v);
		if(p1 == p2) return 0;
		comps --;
		roll.push(DSU_ROLLBACKS(u, v, sz[u], sz[v], p[u], p[v]));
		if(sz[p1] > sz[p2]) swap(p1, p2);
		sz[p2] += sz[p1];
		p[p1] = p2;
		return 1;
	}
};

struct DYNAMIC_CONNECTIVITY_OFFLINE{
	vector< vector<int> > seg;
	int n, N;
	vector<pii> edges;
    vector<pii> queries;

DYNAMIC_CONNECTIVITY_OFFLINE(int x, int vertices) : n(x), N(vertices){
		seg.resize(4*n+5);
        queries.resize(n+5, {-1, -1});
	}

void add_edge(int x, int y, pii edge, int edge_no = 0, int l = 0, int r = -1, int i = 0){
		if(r == -1){
			r += n;
			edge_no = edges.size();
			edges.pb(edge);
		}
		if(r < x || l > y) return ;
		if(l >= x && r <= y) return (seg[i].pb(edge_no));
		int m = (l+r) >> 1;
		add_edge(x, y, edge, edge_no, l, m, i*2+1);
		add_edge(x, y, edge, edge_no, m+1, r, i*2+2);
	}
    
    void add_query(int ind, pii q){
        queries[ind] = q;
    }
    
	void dfs(vector<int>& ans, DSU& dsu, int l = 0, int r = -1, int i = 0){
		if(r == -1) r += n;
		// cout << l << " " << r << " " << dsu.comps << endl;
		int added = 0;
		for(auto j : seg[i])
			added += dsu.merge(edges[j].F, edges[j].S);

if(l == r){
            if(queries[l].F != -1){
                int p1 = dsu.par(queries[l].F);
                int p2 = dsu.par(queries[l].S);
                ans[l] = (p1 == p2);
            }
        }
		else{
			int m = (l+r) >> 1;
			dfs(ans, dsu, l, m, i*2+1);
			dfs(ans, dsu, m+1, r, i*2+2);
		}

while(added --) dsu.rollback();
		// cout << l << " " << r << " " << dsu.comps << endl;
	}

vector<int> solve(){
		vector<int> ans(n, 0);
		DSU dsu(N);
		dfs(ans, dsu);
		return ans;
	}

void print(int l = 0, int r = -1, int i = 0){
		if(r == -1) r += n;
        if(l <= 2 && r >= 2){ 
            cout << "(" << l << " " << r << ") --> "; 
            for(auto j : seg[i]) cout << "(" << edges[j].F << " " << edges[j].S << ") "; cout << endl;
        }
		if(l == r) return;
		int m = (l+r) >> 1;
		print(l, m, i*2+1);
		print(m+1, r, i*2+2);
	}
};

int main(){
	ios_base :: sync_with_stdio(0);
	cin.tie(0);

int n, m;
	cin >> n >> m;
	vector<int> query;

map<pii, int> active;
	DYNAMIC_CONNECTIVITY_OFFLINE dcp(m, n);

for(int j = 0; j < m; j++){
		string ch;
		cin >> ch;
        if(ch == "conn"){
            int u, v;
            cin >> u >> v;
            dcp.add_query(j, mp(u, v));
            query.pb(j);
        }
		else{
			int u, v;
			cin >> u >> v;
			if(u > v) swap(u, v);
            if(ch == "add"){
                if(active.find(mp(u, v)) != active.end());
                else active[mp(u, v)] = j;
            }
            else {
                if(active.find(mp(u, v)) == active.end());
                else dcp.add_edge(active[mp(u, v)], j, mp(u, v)), active.erase(mp(u, v));
            }
		}
	}
	for(auto i : active) dcp.add_edge(i.S, m-1, i.F);
	// dcp.print();
	vector<int> ans = dcp.solve();
	for(auto i : query) cout << (ans[i]? "YES" : "NO") << '\n';
	return 0;
}

100 100
add 24 79
rem 24 79
conn 24 79
conn 24 79
conn 24 79
rem 24 79
rem 24 79
rem 24 79
conn 24 79
add 79 100
conn 79 100
rem 24 79
conn 79 100
conn 79 100
rem 79 100
add 22 68
conn 79 100
add 46 86
conn 46 86
add 2 58
conn 46 86
rem 46 86
conn 2 58
conn 24 79
rem 22 68
rem 2 58
conn 79 100
rem 22 68
add 29 34
rem 79 100
rem 79 100
add 15 64
add 26 70
add 30 95
rem 22 68
conn 15 64
conn 24 79
add 24 89
conn 22 68
add 17 67
add 39 45
add 72 98
conn 29 34
conn 29 34
add 5 95
conn 24 89
conn 39 45
add 43 99
rem 30 95
conn 24 79
rem 24 89
rem 17 67
add 14 31
rem 22 68
rem 29 34
rem 72 98
rem 5 95
add 13 72
conn 72 98
add 39 58
rem 22 68
conn 5 95
conn 13 72
conn 17 67
add 20 55
conn 30 95
conn 5 95
add 7 24
conn 17 67
add 21 95
conn 79 100
rem 21 95
add 39 64
rem 72 98
conn 26 70
rem 29 34
rem 79 100
conn 5 95
conn 39 45
rem 39 58
rem 22 68
conn 13 72
rem 5 95
add 35 43
conn 14 31
add 45 96
conn 21 95
add 16 92
conn 7 24
rem 46 86
rem 24 79
conn 72 98
add 9 78
rem 46 86
rem 30 95
conn 2 58
add 40 75
add 2 57
rem 30 95
conn 24 79

Show compiler warnings [ + ] Compiler args [ - ] Show input
Compilation time: 2.23 sec, absolute running time: 0.07 sec, cpu time: 0.01 sec, memory peak: 3 Mb, absolute service time: 2,31 sec