Submission #398605

# Submission time Handle Problem Language Result Execution time Memory
398605 2021-05-04T15:25:30 Z mosiashvililuka Bridges (APIO19_bridges) C++17
73 / 100
3000 ms 10180 KB
#include<bits/stdc++.h>
using namespace std;
int T=340;
int a,b,c,d,e,i,j,ii,jj,zx,xc,tes,t,te,fx[100009],pi,msh[100009],sz[100009],cnt,bo[100009],ans[100009];
int qi,qqi;
int A,B,C,D,E,sub4;
stack <pair <int, int> > M,S;
pair <pair <int, int>, int> P[100009];
pair <int, pair <int, int> > Q[100009],p[100009];
pair <int, int> q[100009],qq[100009];
int fnd(int q){
	while(msh[q]!=0) q=msh[q];
	return q;
}
void mrg(int q, int w){
	q=fnd(q);w=fnd(w);
	if(q==w) return;
	if(sz[q]<sz[w]) swap(q,w);
	M.push(make_pair(w,msh[w]));
	S.push(make_pair(q,sz[q]));
	msh[w]=q;
	sz[q]+=sz[w];
}
void rollback(){
	msh[M.top().first]=M.top().second;
	sz[S.top().first]=S.top().second;
	M.pop();S.pop();
}
void ROLL(int q){
	while(M.size()>q){
		msh[M.top().first]=M.top().second;
		sz[S.top().first]=S.top().second;
		M.pop();S.pop();
	}
}
int main(){
	ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>a>>b;
	for(i=1; i<=b; i++){
		cin>>P[i].first.first>>P[i].first.second>>P[i].second;
		P[i].second=-P[i].second;
	}
	cin>>tes;
	for(t=1; t<=tes; t++){
		cin>>Q[t].first>>Q[t].second.first>>Q[t].second.second;
		Q[t].second.second=-Q[t].second.second;
		if(Q[t].first==1) sub4=1;
	}
	if(sub4==0){
		T=a;
		for(t=1; t<=tes; t++){
		ans[t]=-1;
	}
	for(t=T; ; t+=T){
		te=t-T+1;
		if(t>tes) t=tes;
		if(te>t) break;
		pi=0;
		for(i=te; i<=t; i++){
			if(Q[i].first==1){
				fx[Q[i].second.first]=t;
			}
		}
		for(i=1; i<=a; i++){
			msh[i]=0;sz[i]=1;
		}
		while(M.size()) M.pop();
		while(S.size()) S.pop();
		for(i=1; i<=b; i++){
			if(fx[i]==t) continue;
			pi++;
			p[pi].first=P[i].second;
			p[pi].second=P[i].first;
		}
		sort(p+1,p+pi+1);
		qi=0;qqi=0;
		for(i=te; i<=t; i++){
			if(Q[i].first==1){
				
			}else{
				qqi++;
				qq[qqi].first=Q[i].second.second;
				qq[qqi].second=i;
			}
		}
		sort(qq+1,qq+qqi+1);
		A=1;B=1;
		for(i=1; i<=qqi; i++){
			while(A<=pi&&p[A].first<=qq[i].first){
				mrg(p[A].second.first,p[A].second.second);
				A++;
			}
			E=M.size();
			c=Q[qq[i].second].second.first;d=qq[i].second;
			ans[d]=sz[fnd(c)];
		}
		for(i=te; i<=t; i++){
			if(Q[i].first==1){
				P[Q[i].second.first].second=Q[i].second.second;
			}
		}
	}
	for(t=1; t<=tes; t++){
		if(ans[t]==-1) continue;
		cout<<ans[t]<<endl;
	}
	
	return 0;
	}
	for(t=1; t<=tes; t++){
		ans[t]=-1;
	}
	for(t=T; ; t+=T){
		te=t-T+1;
		if(t>tes) t=tes;
		if(te>t) break;
		pi=0;
		for(i=te; i<=t; i++){
			if(Q[i].first==1){
				fx[Q[i].second.first]=t;
			}
		}
		for(i=1; i<=a; i++){
			msh[i]=0;sz[i]=1;
		}
		while(M.size()) M.pop();
		while(S.size()) S.pop();
		for(i=1; i<=b; i++){
			if(fx[i]==t) continue;
			pi++;
			p[pi].first=P[i].second;
			p[pi].second=P[i].first;
		}
		sort(p+1,p+pi+1);
		qi=0;qqi=0;
		for(i=te; i<=t; i++){
			if(Q[i].first==1){
				
			}else{
				qqi++;
				qq[qqi].first=Q[i].second.second;
				qq[qqi].second=i;
			}
		}
		sort(qq+1,qq+qqi+1);
		A=1;B=1;
		for(i=1; i<=qqi; i++){
			while(A<=pi&&p[A].first<=qq[i].first){
				mrg(p[A].second.first,p[A].second.second);
				A++;
			}
			E=M.size();
			cnt++;
			for(j=qq[i].second; j>=te; j--){
				if(Q[j].first==2) continue;
				if(bo[Q[j].second.first]==cnt){
					
				}else{
					bo[Q[j].second.first]=cnt;
					if(Q[j].second.second<=qq[i].first){
						mrg(P[Q[j].second.first].first.first,P[Q[j].second.first].first.second);
					}
				}
			}
			for(j=qq[i].second+1; j<=t; j++){
				if(Q[j].first==1&&bo[Q[j].second.first]!=cnt){
					if(P[Q[j].second.first].second<=qq[i].first){
						mrg(P[Q[j].second.first].first.first,P[Q[j].second.first].first.second);
					}
					bo[Q[j].second.first]=cnt;
				}
			}
			c=Q[qq[i].second].second.first;d=qq[i].second;
			ans[d]=sz[fnd(c)];
			ROLL(E);
		}
		for(i=te; i<=t; i++){
			if(Q[i].first==1){
				P[Q[i].second.first].second=Q[i].second.second;
			}
		}
	}
	for(t=1; t<=tes; t++){
		if(ans[t]==-1) continue;
		cout<<ans[t]<<endl;
	}
	return 0;
}

Compilation message

bridges.cpp: In function 'void ROLL(int)':
bridges.cpp:30:16: warning: comparison of integer expressions of different signedness: 'std::stack<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   30 |  while(M.size()>q){
      |        ~~~~~~~~^~
# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 34 ms 720 KB Output is correct
4 Correct 19 ms 600 KB Output is correct
5 Correct 27 ms 672 KB Output is correct
6 Correct 24 ms 676 KB Output is correct
7 Correct 31 ms 588 KB Output is correct
8 Correct 31 ms 660 KB Output is correct
9 Correct 33 ms 612 KB Output is correct
10 Correct 31 ms 604 KB Output is correct
11 Correct 31 ms 672 KB Output is correct
12 Correct 33 ms 664 KB Output is correct
13 Correct 35 ms 716 KB Output is correct
14 Correct 33 ms 588 KB Output is correct
15 Correct 32 ms 668 KB Output is correct
16 Correct 33 ms 604 KB Output is correct
17 Correct 32 ms 612 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 2441 ms 4936 KB Output is correct
2 Correct 2427 ms 5260 KB Output is correct
3 Correct 2439 ms 5052 KB Output is correct
4 Correct 2443 ms 4952 KB Output is correct
5 Correct 2443 ms 4932 KB Output is correct
6 Correct 2789 ms 5140 KB Output is correct
7 Correct 2753 ms 5092 KB Output is correct
8 Correct 2807 ms 5252 KB Output is correct
9 Correct 177 ms 2244 KB Output is correct
10 Correct 2205 ms 5168 KB Output is correct
11 Correct 2373 ms 5184 KB Output is correct
12 Correct 2473 ms 5612 KB Output is correct
13 Correct 2281 ms 5344 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 1698 ms 4116 KB Output is correct
2 Correct 798 ms 2756 KB Output is correct
3 Correct 1840 ms 4176 KB Output is correct
4 Correct 1691 ms 4244 KB Output is correct
5 Correct 181 ms 2244 KB Output is correct
6 Correct 1742 ms 4152 KB Output is correct
7 Correct 1668 ms 4036 KB Output is correct
8 Correct 1620 ms 4116 KB Output is correct
9 Correct 1645 ms 4252 KB Output is correct
10 Correct 1598 ms 4128 KB Output is correct
11 Correct 1434 ms 4036 KB Output is correct
12 Correct 1364 ms 3988 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 260 ms 6468 KB Output is correct
2 Correct 178 ms 3472 KB Output is correct
3 Correct 318 ms 4684 KB Output is correct
4 Correct 341 ms 4824 KB Output is correct
5 Correct 242 ms 8516 KB Output is correct
6 Correct 252 ms 10044 KB Output is correct
7 Correct 241 ms 8600 KB Output is correct
8 Correct 227 ms 7524 KB Output is correct
9 Correct 224 ms 7576 KB Output is correct
10 Correct 223 ms 7536 KB Output is correct
11 Correct 254 ms 8624 KB Output is correct
12 Correct 235 ms 8772 KB Output is correct
13 Correct 242 ms 8824 KB Output is correct
14 Correct 240 ms 8548 KB Output is correct
15 Correct 245 ms 8624 KB Output is correct
16 Correct 269 ms 9956 KB Output is correct
17 Correct 290 ms 9888 KB Output is correct
18 Correct 265 ms 10052 KB Output is correct
19 Correct 274 ms 9964 KB Output is correct
20 Correct 262 ms 9184 KB Output is correct
21 Correct 254 ms 9080 KB Output is correct
22 Correct 269 ms 9852 KB Output is correct
23 Correct 248 ms 7792 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 2441 ms 4936 KB Output is correct
2 Correct 2427 ms 5260 KB Output is correct
3 Correct 2439 ms 5052 KB Output is correct
4 Correct 2443 ms 4952 KB Output is correct
5 Correct 2443 ms 4932 KB Output is correct
6 Correct 2789 ms 5140 KB Output is correct
7 Correct 2753 ms 5092 KB Output is correct
8 Correct 2807 ms 5252 KB Output is correct
9 Correct 177 ms 2244 KB Output is correct
10 Correct 2205 ms 5168 KB Output is correct
11 Correct 2373 ms 5184 KB Output is correct
12 Correct 2473 ms 5612 KB Output is correct
13 Correct 2281 ms 5344 KB Output is correct
14 Correct 1698 ms 4116 KB Output is correct
15 Correct 798 ms 2756 KB Output is correct
16 Correct 1840 ms 4176 KB Output is correct
17 Correct 1691 ms 4244 KB Output is correct
18 Correct 181 ms 2244 KB Output is correct
19 Correct 1742 ms 4152 KB Output is correct
20 Correct 1668 ms 4036 KB Output is correct
21 Correct 1620 ms 4116 KB Output is correct
22 Correct 1645 ms 4252 KB Output is correct
23 Correct 1598 ms 4128 KB Output is correct
24 Correct 1434 ms 4036 KB Output is correct
25 Correct 1364 ms 3988 KB Output is correct
26 Correct 2468 ms 5180 KB Output is correct
27 Correct 2724 ms 5224 KB Output is correct
28 Correct 2602 ms 4964 KB Output is correct
29 Correct 2408 ms 5080 KB Output is correct
30 Correct 2700 ms 5176 KB Output is correct
31 Correct 2794 ms 5092 KB Output is correct
32 Correct 2707 ms 5236 KB Output is correct
33 Correct 2540 ms 4996 KB Output is correct
34 Correct 2571 ms 4984 KB Output is correct
35 Correct 2573 ms 4952 KB Output is correct
36 Correct 2426 ms 4976 KB Output is correct
37 Correct 2434 ms 5276 KB Output is correct
38 Correct 2415 ms 5036 KB Output is correct
39 Correct 2421 ms 5068 KB Output is correct
40 Correct 2402 ms 5140 KB Output is correct
41 Correct 2417 ms 5104 KB Output is correct
42 Correct 2117 ms 5004 KB Output is correct
43 Correct 2097 ms 5136 KB Output is correct
44 Correct 2089 ms 5000 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 34 ms 720 KB Output is correct
4 Correct 19 ms 600 KB Output is correct
5 Correct 27 ms 672 KB Output is correct
6 Correct 24 ms 676 KB Output is correct
7 Correct 31 ms 588 KB Output is correct
8 Correct 31 ms 660 KB Output is correct
9 Correct 33 ms 612 KB Output is correct
10 Correct 31 ms 604 KB Output is correct
11 Correct 31 ms 672 KB Output is correct
12 Correct 33 ms 664 KB Output is correct
13 Correct 35 ms 716 KB Output is correct
14 Correct 33 ms 588 KB Output is correct
15 Correct 32 ms 668 KB Output is correct
16 Correct 33 ms 604 KB Output is correct
17 Correct 32 ms 612 KB Output is correct
18 Correct 2441 ms 4936 KB Output is correct
19 Correct 2427 ms 5260 KB Output is correct
20 Correct 2439 ms 5052 KB Output is correct
21 Correct 2443 ms 4952 KB Output is correct
22 Correct 2443 ms 4932 KB Output is correct
23 Correct 2789 ms 5140 KB Output is correct
24 Correct 2753 ms 5092 KB Output is correct
25 Correct 2807 ms 5252 KB Output is correct
26 Correct 177 ms 2244 KB Output is correct
27 Correct 2205 ms 5168 KB Output is correct
28 Correct 2373 ms 5184 KB Output is correct
29 Correct 2473 ms 5612 KB Output is correct
30 Correct 2281 ms 5344 KB Output is correct
31 Correct 1698 ms 4116 KB Output is correct
32 Correct 798 ms 2756 KB Output is correct
33 Correct 1840 ms 4176 KB Output is correct
34 Correct 1691 ms 4244 KB Output is correct
35 Correct 181 ms 2244 KB Output is correct
36 Correct 1742 ms 4152 KB Output is correct
37 Correct 1668 ms 4036 KB Output is correct
38 Correct 1620 ms 4116 KB Output is correct
39 Correct 1645 ms 4252 KB Output is correct
40 Correct 1598 ms 4128 KB Output is correct
41 Correct 1434 ms 4036 KB Output is correct
42 Correct 1364 ms 3988 KB Output is correct
43 Correct 260 ms 6468 KB Output is correct
44 Correct 178 ms 3472 KB Output is correct
45 Correct 318 ms 4684 KB Output is correct
46 Correct 341 ms 4824 KB Output is correct
47 Correct 242 ms 8516 KB Output is correct
48 Correct 252 ms 10044 KB Output is correct
49 Correct 241 ms 8600 KB Output is correct
50 Correct 227 ms 7524 KB Output is correct
51 Correct 224 ms 7576 KB Output is correct
52 Correct 223 ms 7536 KB Output is correct
53 Correct 254 ms 8624 KB Output is correct
54 Correct 235 ms 8772 KB Output is correct
55 Correct 242 ms 8824 KB Output is correct
56 Correct 240 ms 8548 KB Output is correct
57 Correct 245 ms 8624 KB Output is correct
58 Correct 269 ms 9956 KB Output is correct
59 Correct 290 ms 9888 KB Output is correct
60 Correct 265 ms 10052 KB Output is correct
61 Correct 274 ms 9964 KB Output is correct
62 Correct 262 ms 9184 KB Output is correct
63 Correct 254 ms 9080 KB Output is correct
64 Correct 269 ms 9852 KB Output is correct
65 Correct 248 ms 7792 KB Output is correct
66 Correct 2468 ms 5180 KB Output is correct
67 Correct 2724 ms 5224 KB Output is correct
68 Correct 2602 ms 4964 KB Output is correct
69 Correct 2408 ms 5080 KB Output is correct
70 Correct 2700 ms 5176 KB Output is correct
71 Correct 2794 ms 5092 KB Output is correct
72 Correct 2707 ms 5236 KB Output is correct
73 Correct 2540 ms 4996 KB Output is correct
74 Correct 2571 ms 4984 KB Output is correct
75 Correct 2573 ms 4952 KB Output is correct
76 Correct 2426 ms 4976 KB Output is correct
77 Correct 2434 ms 5276 KB Output is correct
78 Correct 2415 ms 5036 KB Output is correct
79 Correct 2421 ms 5068 KB Output is correct
80 Correct 2402 ms 5140 KB Output is correct
81 Correct 2417 ms 5104 KB Output is correct
82 Correct 2117 ms 5004 KB Output is correct
83 Correct 2097 ms 5136 KB Output is correct
84 Correct 2089 ms 5000 KB Output is correct
85 Execution timed out 3069 ms 10180 KB Time limit exceeded
86 Halted 0 ms 0 KB -