oj.uz

Submission #398595

# Submission time Handle Problem Language Result Execution time Memory
398595 2021-05-04T15:15:59 Z mosiashvililuka Bridges (APIO19_bridges) C++14
30 / 100
 3000 ms 5864 KB 
#include<bits/stdc++.h>
using namespace std;
const int T=200;
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){
      |        ~~~~~~~~^~

Subtask #1
13.0 / 13.0

# 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 26 ms 464 KB Output is correct
4 Correct 25 ms 516 KB Output is correct
5 Correct 21 ms 524 KB Output is correct
6 Correct 19 ms 460 KB Output is correct
7 Correct 25 ms 532 KB Output is correct
8 Correct 29 ms 520 KB Output is correct
9 Correct 28 ms 512 KB Output is correct
10 Correct 26 ms 524 KB Output is correct
11 Correct 25 ms 536 KB Output is correct
12 Correct 28 ms 536 KB Output is correct
13 Correct 27 ms 524 KB Output is correct
14 Correct 26 ms 460 KB Output is correct
15 Correct 26 ms 524 KB Output is correct
16 Correct 26 ms 528 KB Output is correct
17 Correct 26 ms 532 KB Output is correct

Subtask #2
0 / 16.0

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

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2449 ms 4028 KB Output is correct
2 Correct 827 ms 2484 KB Output is correct
3 Correct 2491 ms 3860 KB Output is correct
4 Correct 2564 ms 3860 KB Output is correct
5 Correct 261 ms 2028 KB Output is correct
6 Correct 2556 ms 3788 KB Output is correct
7 Correct 2468 ms 3860 KB Output is correct
8 Correct 2431 ms 3872 KB Output is correct
9 Correct 2400 ms 4120 KB Output is correct
10 Correct 2392 ms 3908 KB Output is correct
11 Correct 2200 ms 3768 KB Output is correct
12 Correct 2153 ms 3736 KB Output is correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3079 ms 5864 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 3070 ms 4996 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# 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 26 ms 464 KB Output is correct
4 Correct 25 ms 516 KB Output is correct
5 Correct 21 ms 524 KB Output is correct
6 Correct 19 ms 460 KB Output is correct
7 Correct 25 ms 532 KB Output is correct
8 Correct 29 ms 520 KB Output is correct
9 Correct 28 ms 512 KB Output is correct
10 Correct 26 ms 524 KB Output is correct
11 Correct 25 ms 536 KB Output is correct
12 Correct 28 ms 536 KB Output is correct
13 Correct 27 ms 524 KB Output is correct
14 Correct 26 ms 460 KB Output is correct
15 Correct 26 ms 524 KB Output is correct
16 Correct 26 ms 528 KB Output is correct
17 Correct 26 ms 532 KB Output is correct
18 Execution timed out 3070 ms 4996 KB Time limit exceeded
19 Halted 0 ms 0 KB -