Submission #136755

#	Time	Username	Problem	Language	Result	Execution time	Memory
136755		rajarshi_basu	Bridges (APIO19_bridges)	C++14	13 / 100	3085 ms	7052 KiB

bridges

    #include <iostream>
    #include <vector>
    #include <set>
    #include <iomanip>
    #include <algorithm>
    #include <functional>
    #include <stdio.h>
    #include <cmath>
    #include <queue>
    #include <string>
    #include <map>
    #include <unordered_map>
    #include <fstream>
    #include <complex>
    #include <random>
    #include <stack>
    #include <chrono>
    #include <set>
     
    #define FOR(i,n) for(int i=0;i<n;i++)
    #define FORE(i,a,b) for(int i=a;i<=b;i++)
    #define ll long long int
    #define vi vector<int>
    #define ii pair<int,int>
    #define pb push_back
    #define mp make_pair
    #define ff first
    #define ss second
    #define pll pair<ll,ll>
    #define cd complex<double> 
    #define ld long double
    #define pld pair<ld,ld>
    #define iii pair<ii,int>
    #define vv vector
     
    using namespace std;
     
    const int MAXN = 50*1000+1;
    const int MAXM = 2*MAXN;
    int n;
    struct DSU{
    	struct Oper{
    		int type; // change in parent = 1, change in rank = 2;checkpoint = 3;size =4
    		int a;
    		int b;
    		Oper(int t,int aa = 0,int bb = 0){
    			type = t;
    			a = aa;
    			b = bb;
    		}
		};
    	stack<Oper> st;
    	int parent[MAXN];
    	int sz[MAXN];
    	int rnk[MAXN];
    	void init(){
    		FOR(i,n)parent[i] = i;
    		FOR(i,n)sz[i] = 1;
    		FOR(i,n)rnk[i] = 1;
    	}
    	inline int find(int a){
    		if(a == parent[a])return a;
    		return find(parent[a]);
    	}
    	inline void merge(int a,int b){
    		if(isSame(a,b))return;
    		int pa = find(a);
    		int pb = find(b);
    		if(rnk[pa] > rnk[pb]){
    			st.push(Oper(1,pb));
    			st.push(Oper(2,pa,sz[pb]));
    			sz[pa] += sz[pb];
    			parent[pb] = pa;
    		}else if(rnk[pa] < rnk[pb]){
       			st.push(Oper(1,pa));
    			st.push(Oper(2,pb,sz[pa]));

				sz[pb] += sz[pa];
				parent[pa] = pb;
			}else{
				st.push(Oper(1,pb));
    			st.push(Oper(2,pa,sz[pb]));
				st.push(Oper(4,pa));
				sz[pa] += sz[pb];
				parent[pb] = pa;
				rnk[pa]++;
			}
    		
    		
    		
    	};
    	int getSize(int a){
    		return sz[find(a)];
    	}
    	bool isSame(int a,int b){
    		return find(a) == find(b);
    	}
    	void setCheckPoint(){
    		st.push(Oper(3));
		}
		void rollback(){
			while(!st.empty()){
				auto e = st.top();st.pop();
				if(e.type == 3)break;
				else if(e.type == 1){
					parent[e.a] = e.a;
				}else if(e.type == 2){
					sz[e.a] -= e.b;
				}else{
					rnk[e.a]--;
				}
			}
		}
    };
     
    struct edge{
    	int ID;
    	int a,b;
    	int w;
    	edge(int id,int aa,int bb,int ww){
    		ID = id;
    		a = aa;
    		b = bb;
    		w = ww;
    	}
    };
    struct query{
    	int type; // 1 is update, 2 is query
    	int tm;
    	int info1; // node for query, edge for update
    	int info2; // value for either
    	int id;
    	query(int t,int a,int b,int c){
    		type = t;
    		tm = id = a;
    		info1 = b;
    		info2 = c;
     
    	}
    };
     
    int finalANS[MAXM];
    vv<edge> allEdges;
     
    vi rem;
    bool edg[MAXM];
     
    void processQueries(vv<query> allQueries){
    	FOR(i,MAXM)edg[i] = 0;
    	rem.clear();
    	for(auto e : allQueries){
    		if(e.type == 1){
    			edg[e.info1] = 1;
    			rem.pb(e.info1);
    		}
    	}
    	//cout << "REM CONTENTS : " ;
    	//for(auto e : rem)cout << e << " ";cout << endl;
    	//DSU dsu;
    	//dsu.init();
     
    	vv<query> actualQueries;
    	for(auto e : allQueries){
    		if(e.type == 2){
    			actualQueries.pb(e);
    		}
    	}
    	vv<edge> nonBlockEdges;
    	FOR(i,allEdges.size()){
    		if(edg[i])continue;
    		nonBlockEdges.pb(allEdges[i]);
		}
     	sort(nonBlockEdges.begin(),nonBlockEdges.end(),[&](edge a,edge b){
     		return a.w > b.w;
     	});
    	sort(actualQueries.begin(), actualQueries.end(), [&](query a,query b){
    		return a.info2 > b.info2;
    	});
     	int PTR = 0;
     	DSU dsu;
    	dsu.init();
    		
    	for(auto q : actualQueries){
    		//cout << "PROCESSING FOR QUERY : " << q.info1 << " " << q.info2 << endl;
    		while(PTR < nonBlockEdges.size() and nonBlockEdges[PTR].w >= q.info2){
				dsu.merge(nonBlockEdges[PTR].a,nonBlockEdges[PTR].b);
				PTR++;
			}	
    		dsu.setCheckPoint();
    		/*
    		FOR(i,allEdges.size()){
    			if(edg[i])continue;
    			if(allEdges[i].w < q.info2)continue;
    			//cout << "PERMEDGE PROCESSED : " << i+1 << endl;
    			dsu.merge(allEdges[i].a,allEdges[i].b);
    		}*/
    		unordered_map<int,int> mp;
    		for(auto xx : rem){
    			mp[xx] = allEdges[xx].w;
    		}
    		for(auto e : allQueries){
    			if(e.type == 2)continue;
    			if(e.tm > q.tm)continue;
     
    			//cout << "BLOCK EDGE SEEN : " << e.info1+1 << " " << e.info2 << endl;
    			mp[e.info1] = e.info2;
    		}
    		for(auto x : mp){
     
    			
    			if(x.ss >= q.info2){
    				//cout << "BLOCK EDGE SEEN : " << x.ff+1 << " " << x.ss << endl;				
    				dsu.merge(allEdges[x.ff].a,allEdges[x.ff].b);
    			}
    		}
    		finalANS[q.id] = dsu.getSize(q.info1);
    		dsu.rollback();
    	}
     
    	for(auto e : allQueries){
    		if(e.type == 1){
    			allEdges[e.info1].w = e.info2;
    		}
    	}
    }
    bool quer[MAXM];
    #define endl '\n'
    int main(){
    	ios_base::sync_with_stdio(0);
    	cin.tie(0);
    	cout.tie(0);
    	int m;
    	cin >> n >> m;
    	FOR(i,m){
    		int a,b,c;
    		cin >> a >> b >> c;
    		a--;b--;
    		allEdges.pb(edge(i,a,b,c));
    	}
    	int q;
    	cin >> q;
    	FOR(i,MAXM)finalANS[i] = -1;
    	int BLOCK = 300;
    	vv<query> allq;
     
    	FOR(i,q){
    		int a,b,c;
    		cin >> a >> b >> c;
    		if(a == 2)quer[i] = 1;
    		b--;
    		allq.pb(query(a,i,b,c));
    		if((i+1)%BLOCK == 0){
    			processQueries(allq);
    			allq.clear();
    		}
    	}
    	if(allq.size() > 0)processQueries(allq);
    	FOR(i,q){
    		//if(finalANS[i] == -1 and quer[i])while(1);
    		if(quer[i])cout << finalANS[i] << endl;
    	}
    	return 0;
    }

Compilation message (stderr)

bridges.cpp: In function 'void processQueries(std::vector<query>)':
bridges.cpp:20:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     #define FOR(i,n) for(int i=0;i<n;i++)
bridges.cpp:169:10:
      FOR(i,allEdges.size()){
          ~~~~~~~~~~~~~~~~~         
bridges.cpp:169:6: note: in expansion of macro 'FOR'
      FOR(i,allEdges.size()){
      ^~~
bridges.cpp:185:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       while(PTR < nonBlockEdges.size() and nonBlockEdges[PTR].w >= q.info2){
             ~~~~^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 13 / 13
• Subtask 2: 0 / 16
• Subtask 3: 0 / 17
• Subtask 4: 0 / 14
• Subtask 5: 0 / 13
• Subtask 6: 0 / 27