답안 #398598

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
398598 2021-05-04T15:17:36 Z mosiashvililuka 다리 (APIO19_bridges) C++14
59 / 100
3000 ms 5500 KB
#include<bits/stdc++.h>
using namespace std;
const int T=400;
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){
      |        ~~~~~~~~^~
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 32 ms 552 KB Output is correct
4 Correct 32 ms 512 KB Output is correct
5 Correct 29 ms 524 KB Output is correct
6 Correct 29 ms 520 KB Output is correct
7 Correct 33 ms 524 KB Output is correct
8 Correct 34 ms 504 KB Output is correct
9 Correct 38 ms 516 KB Output is correct
10 Correct 34 ms 512 KB Output is correct
11 Correct 33 ms 524 KB Output is correct
12 Correct 35 ms 460 KB Output is correct
13 Correct 38 ms 520 KB Output is correct
14 Correct 36 ms 520 KB Output is correct
15 Correct 34 ms 520 KB Output is correct
16 Correct 36 ms 460 KB Output is correct
17 Correct 37 ms 532 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 2264 ms 4824 KB Output is correct
2 Correct 2330 ms 4772 KB Output is correct
3 Correct 2270 ms 4800 KB Output is correct
4 Correct 2321 ms 4832 KB Output is correct
5 Correct 2336 ms 4888 KB Output is correct
6 Correct 2632 ms 4944 KB Output is correct
7 Correct 2812 ms 4928 KB Output is correct
8 Correct 2755 ms 4944 KB Output is correct
9 Correct 314 ms 1988 KB Output is correct
10 Correct 2115 ms 5012 KB Output is correct
11 Correct 2330 ms 4764 KB Output is correct
12 Correct 2270 ms 5168 KB Output is correct
13 Correct 2166 ms 4848 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 1653 ms 3864 KB Output is correct
2 Correct 832 ms 2484 KB Output is correct
3 Correct 1828 ms 3864 KB Output is correct
4 Correct 1662 ms 3764 KB Output is correct
5 Correct 344 ms 2084 KB Output is correct
6 Correct 1708 ms 3860 KB Output is correct
7 Correct 1594 ms 3872 KB Output is correct
8 Correct 1557 ms 3860 KB Output is correct
9 Correct 1557 ms 4112 KB Output is correct
10 Correct 1544 ms 3952 KB Output is correct
11 Correct 1326 ms 3744 KB Output is correct
12 Correct 1299 ms 3744 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3057 ms 5500 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 2264 ms 4824 KB Output is correct
2 Correct 2330 ms 4772 KB Output is correct
3 Correct 2270 ms 4800 KB Output is correct
4 Correct 2321 ms 4832 KB Output is correct
5 Correct 2336 ms 4888 KB Output is correct
6 Correct 2632 ms 4944 KB Output is correct
7 Correct 2812 ms 4928 KB Output is correct
8 Correct 2755 ms 4944 KB Output is correct
9 Correct 314 ms 1988 KB Output is correct
10 Correct 2115 ms 5012 KB Output is correct
11 Correct 2330 ms 4764 KB Output is correct
12 Correct 2270 ms 5168 KB Output is correct
13 Correct 2166 ms 4848 KB Output is correct
14 Correct 1653 ms 3864 KB Output is correct
15 Correct 832 ms 2484 KB Output is correct
16 Correct 1828 ms 3864 KB Output is correct
17 Correct 1662 ms 3764 KB Output is correct
18 Correct 344 ms 2084 KB Output is correct
19 Correct 1708 ms 3860 KB Output is correct
20 Correct 1594 ms 3872 KB Output is correct
21 Correct 1557 ms 3860 KB Output is correct
22 Correct 1557 ms 4112 KB Output is correct
23 Correct 1544 ms 3952 KB Output is correct
24 Correct 1326 ms 3744 KB Output is correct
25 Correct 1299 ms 3744 KB Output is correct
26 Correct 2240 ms 4728 KB Output is correct
27 Correct 2632 ms 4796 KB Output is correct
28 Correct 2425 ms 4784 KB Output is correct
29 Correct 2272 ms 4808 KB Output is correct
30 Correct 2539 ms 4896 KB Output is correct
31 Correct 2624 ms 4816 KB Output is correct
32 Correct 2552 ms 4952 KB Output is correct
33 Correct 2470 ms 4852 KB Output is correct
34 Correct 2409 ms 4860 KB Output is correct
35 Correct 2493 ms 4732 KB Output is correct
36 Correct 2193 ms 4864 KB Output is correct
37 Correct 2186 ms 4708 KB Output is correct
38 Correct 2175 ms 4772 KB Output is correct
39 Correct 2243 ms 4856 KB Output is correct
40 Correct 2180 ms 4796 KB Output is correct
41 Correct 2297 ms 4896 KB Output is correct
42 Correct 1922 ms 4672 KB Output is correct
43 Correct 1914 ms 4764 KB Output is correct
44 Correct 1868 ms 4812 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 32 ms 552 KB Output is correct
4 Correct 32 ms 512 KB Output is correct
5 Correct 29 ms 524 KB Output is correct
6 Correct 29 ms 520 KB Output is correct
7 Correct 33 ms 524 KB Output is correct
8 Correct 34 ms 504 KB Output is correct
9 Correct 38 ms 516 KB Output is correct
10 Correct 34 ms 512 KB Output is correct
11 Correct 33 ms 524 KB Output is correct
12 Correct 35 ms 460 KB Output is correct
13 Correct 38 ms 520 KB Output is correct
14 Correct 36 ms 520 KB Output is correct
15 Correct 34 ms 520 KB Output is correct
16 Correct 36 ms 460 KB Output is correct
17 Correct 37 ms 532 KB Output is correct
18 Correct 2264 ms 4824 KB Output is correct
19 Correct 2330 ms 4772 KB Output is correct
20 Correct 2270 ms 4800 KB Output is correct
21 Correct 2321 ms 4832 KB Output is correct
22 Correct 2336 ms 4888 KB Output is correct
23 Correct 2632 ms 4944 KB Output is correct
24 Correct 2812 ms 4928 KB Output is correct
25 Correct 2755 ms 4944 KB Output is correct
26 Correct 314 ms 1988 KB Output is correct
27 Correct 2115 ms 5012 KB Output is correct
28 Correct 2330 ms 4764 KB Output is correct
29 Correct 2270 ms 5168 KB Output is correct
30 Correct 2166 ms 4848 KB Output is correct
31 Correct 1653 ms 3864 KB Output is correct
32 Correct 832 ms 2484 KB Output is correct
33 Correct 1828 ms 3864 KB Output is correct
34 Correct 1662 ms 3764 KB Output is correct
35 Correct 344 ms 2084 KB Output is correct
36 Correct 1708 ms 3860 KB Output is correct
37 Correct 1594 ms 3872 KB Output is correct
38 Correct 1557 ms 3860 KB Output is correct
39 Correct 1557 ms 4112 KB Output is correct
40 Correct 1544 ms 3952 KB Output is correct
41 Correct 1326 ms 3744 KB Output is correct
42 Correct 1299 ms 3744 KB Output is correct
43 Execution timed out 3057 ms 5500 KB Time limit exceeded
44 Halted 0 ms 0 KB -