Submission #398600

# Submission time Handle Problem Language Result Execution time Memory
398600 2021-05-04T15:18:12 Z mosiashvililuka Bridges (APIO19_bridges) C++14
30 / 100
3000 ms 5620 KB
#include<bits/stdc++.h>
using namespace std;
const 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;
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;
	}
	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=te-1; i>=1; i--){
			if(Q[i].first==1){
				if(fx[Q[i].second.first]==t) continue;
				pi++;
				p[pi].first=Q[i].second.second;
				p[pi].second=P[Q[i].second.first].first;
				fx[Q[t].second.first]=t;
			}
		}*/
		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 336 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 31 ms 548 KB Output is correct
4 Correct 34 ms 512 KB Output is correct
5 Correct 26 ms 516 KB Output is correct
6 Correct 24 ms 520 KB Output is correct
7 Correct 31 ms 460 KB Output is correct
8 Correct 34 ms 516 KB Output is correct
9 Correct 34 ms 508 KB Output is correct
10 Correct 31 ms 528 KB Output is correct
11 Correct 32 ms 520 KB Output is correct
12 Correct 32 ms 460 KB Output is correct
13 Correct 35 ms 508 KB Output is correct
14 Correct 37 ms 516 KB Output is correct
15 Correct 34 ms 520 KB Output is correct
16 Correct 33 ms 516 KB Output is correct
17 Correct 33 ms 532 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 2634 ms 4728 KB Output is correct
2 Correct 2576 ms 4812 KB Output is correct
3 Correct 2500 ms 4688 KB Output is correct
4 Correct 2537 ms 4728 KB Output is correct
5 Correct 2592 ms 4836 KB Output is correct
6 Execution timed out 3011 ms 4996 KB Time limit exceeded
7 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 1806 ms 3860 KB Output is correct
2 Correct 820 ms 2528 KB Output is correct
3 Correct 1961 ms 3856 KB Output is correct
4 Correct 1736 ms 3868 KB Output is correct
5 Correct 290 ms 1972 KB Output is correct
6 Correct 1791 ms 3860 KB Output is correct
7 Correct 1737 ms 3844 KB Output is correct
8 Correct 1629 ms 3812 KB Output is correct
9 Correct 1696 ms 4052 KB Output is correct
10 Correct 1677 ms 3964 KB Output is correct
11 Correct 1466 ms 3732 KB Output is correct
12 Correct 1371 ms 3736 KB Output is correct
# Verdict Execution time Memory Grader output
1 Execution timed out 3036 ms 5620 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 2634 ms 4728 KB Output is correct
2 Correct 2576 ms 4812 KB Output is correct
3 Correct 2500 ms 4688 KB Output is correct
4 Correct 2537 ms 4728 KB Output is correct
5 Correct 2592 ms 4836 KB Output is correct
6 Execution timed out 3011 ms 4996 KB Time limit exceeded
7 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 31 ms 548 KB Output is correct
4 Correct 34 ms 512 KB Output is correct
5 Correct 26 ms 516 KB Output is correct
6 Correct 24 ms 520 KB Output is correct
7 Correct 31 ms 460 KB Output is correct
8 Correct 34 ms 516 KB Output is correct
9 Correct 34 ms 508 KB Output is correct
10 Correct 31 ms 528 KB Output is correct
11 Correct 32 ms 520 KB Output is correct
12 Correct 32 ms 460 KB Output is correct
13 Correct 35 ms 508 KB Output is correct
14 Correct 37 ms 516 KB Output is correct
15 Correct 34 ms 520 KB Output is correct
16 Correct 33 ms 516 KB Output is correct
17 Correct 33 ms 532 KB Output is correct
18 Correct 2634 ms 4728 KB Output is correct
19 Correct 2576 ms 4812 KB Output is correct
20 Correct 2500 ms 4688 KB Output is correct
21 Correct 2537 ms 4728 KB Output is correct
22 Correct 2592 ms 4836 KB Output is correct
23 Execution timed out 3011 ms 4996 KB Time limit exceeded
24 Halted 0 ms 0 KB -