Submission #136728

#	Time	Username	Problem	Language	Result	Execution time	Memory
136728		rajarshi_basu	Bridges (APIO19_bridges)	C++14	0 / 100	3053 ms	2956 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{
    	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);
    		sz[pa] += sz[pb];
    		parent[pb] = pa;
    	}
    	int getSize(int a){
    		return sz[find(a)];
    	}
    	bool isSame(int a,int b){
    		return find(a) == find(b);
    	}
    };
     
    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);
    		}
    	}
     
    	sort(actualQueries.begin(), actualQueries.end(), [&](query a,query b){
    		return a.info2 >= b.info2;
    	});
     
    	for(auto q : actualQueries){
    		//cout << "PROCESSING FOR QUERY : " << q.info1 << " " << q.info2 << endl;
    		DSU dsu;
    		dsu.init();
    		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);
    	}
     
    	for(auto e : allQueries){
    		if(e.type == 1){
    			allEdges[e.info1].w = e.info2;
    		}
    	}
    }
    bool quer[MAXM];
     
    int main(){
    	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 = 100;
    	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(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:130:11:
       FOR(i,allEdges.size()){
           ~~~~~~~~~~~~~~~~~        
bridges.cpp:130:7: note: in expansion of macro 'FOR'
       FOR(i,allEdges.size()){
       ^~~

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