oj.uz

Submission #136763

# Submission time Handle Problem Language Result Execution time Memory
136763 2019-07-26T08:22:12 Z rajarshi_basu Bridges (APIO19_bridges) C++14
30 / 100
 3000 ms 6824 KB 
	

    #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]++;
			}
    		
    		
    		
    	};
    	inline int getSize(int a){
    		return sz[find(a)];
    	}
		inline bool isSame(int a,int b){
    		return find(a) == find(b);
    	}
    	inline void setCheckPoint(){
    		st.push(Oper(3));
		}
		inline 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);
    		}
    	}
     	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();
    		map<int,int> mp;
    		//mp.max_load_factor(0.25);
    		//mp.reserve(1024);
    		for(auto xx : rem){
    			mp[xx] = allEdges[xx].w;
    		}
    		for(auto e : allQueries){
    			if(e.type == 2)continue;
    			if(e.tm > q.tm)continue;
    			mp[e.info1] = e.info2;
    		}
    		for(auto x : mp){
    			if(x.ss >= q.info2){
    				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

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

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 760 KB Output is correct
2 Correct 2 ms 888 KB Output is correct
3 Correct 84 ms 1016 KB Output is correct
4 Correct 13 ms 888 KB Output is correct
5 Correct 50 ms 888 KB Output is correct
6 Correct 49 ms 888 KB Output is correct
7 Correct 56 ms 960 KB Output is correct
8 Correct 59 ms 960 KB Output is correct
9 Correct 60 ms 888 KB Output is correct
10 Correct 60 ms 1016 KB Output is correct
11 Correct 61 ms 924 KB Output is correct
12 Correct 62 ms 888 KB Output is correct
13 Correct 68 ms 968 KB Output is correct
14 Correct 66 ms 888 KB Output is correct
15 Correct 58 ms 888 KB Output is correct
16 Correct 58 ms 888 KB Output is correct
17 Correct 59 ms 888 KB Output is correct

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3036 ms 4936 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2923 ms 3484 KB Output is correct
2 Correct 1389 ms 1700 KB Output is correct
3 Correct 2862 ms 3516 KB Output is correct
4 Correct 2941 ms 5980 KB Output is correct
5 Correct 97 ms 2504 KB Output is correct
6 Correct 2843 ms 5692 KB Output is correct
7 Correct 2717 ms 5720 KB Output is correct
8 Correct 2683 ms 5976 KB Output is correct
9 Correct 2092 ms 5876 KB Output is correct
10 Correct 2050 ms 5908 KB Output is correct
11 Correct 2325 ms 5824 KB Output is correct
12 Correct 2200 ms 5840 KB Output is correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3050 ms 6824 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3036 ms 4936 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 760 KB Output is correct
2 Correct 2 ms 888 KB Output is correct
3 Correct 84 ms 1016 KB Output is correct
4 Correct 13 ms 888 KB Output is correct
5 Correct 50 ms 888 KB Output is correct
6 Correct 49 ms 888 KB Output is correct
7 Correct 56 ms 960 KB Output is correct
8 Correct 59 ms 960 KB Output is correct
9 Correct 60 ms 888 KB Output is correct
10 Correct 60 ms 1016 KB Output is correct
11 Correct 61 ms 924 KB Output is correct
12 Correct 62 ms 888 KB Output is correct
13 Correct 68 ms 968 KB Output is correct
14 Correct 66 ms 888 KB Output is correct
15 Correct 58 ms 888 KB Output is correct
16 Correct 58 ms 888 KB Output is correct
17 Correct 59 ms 888 KB Output is correct
18 Execution timed out 3036 ms 4936 KB Time limit exceeded
19 Halted 0 ms 0 KB -