oj.uz

답안 #409779

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
409779 2021-05-21T13:59:37 Z amunduzbaev 다리 (APIO19_bridges) C++14
100 / 100
 2495 ms 112660 KB 
#include "bits/stdc++.h"
#define MAXN 100009
#define INF 1000000007
#define mp(x,y) make_pair(x,y)
#define all(v) v.begin(),v.end()
#define pb(x) push_back(x)
#define wr cout<<"----------------"<<endl;
#define ppb() pop_back()
#define tr(ii,c) for(__typeof((c).begin()) ii=(c).begin();ii!=(c).end();ii++)
#define ff first
#define ss second
#define my_little_dodge 46
#define debug(x)  cerr<< #x <<" = "<< x<<endl;
using namespace std;
 
typedef long long ll;
typedef pair<int,int> PII;
template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
const int BLOK=1000;
pair<PII,int>edge[MAXN];
pair<int,PII>query[MAXN];
int ans[MAXN],ata[MAXN],sz[MAXN];
bool ban[MAXN],ban1[MAXN];
stack<int>st;
vector<pair<PII,int> >history;
int tap(int x){
	if(ata[x]==x)return x;
	return tap(ata[x]);	
}
bool merge(PII v){
	int x=tap(v.ff),y=tap(v.ss);
	if(x==y)return 0;
	if(sz[x]<sz[y])swap(x,y);
	history.pb(mp(mp(x,y),sz[y]));
	ata[y]=x;sz[x]+=sz[y]; return 1;	
}
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    //freopen("file.in", "r", stdin);
    int n,m;
    cin>>n>>m;
    set<PII>edges;
    for(int i=1;i<=m;i++){
    	int u,v,w;
		cin>>u>>v>>w;
		edge[i]=mp(mp(u,v),w);
		edges.insert(mp(w,i));
    }
    int q;
    cin>>q;
    for(int i=1;i<=q;i++){
    	int t,a,b;
		cin>>t>>a>>b;
		query[i]=mp(t,mp(a,b));	
    }
    for(int i=1;i<=q;i+=BLOK){
    	memset(ban,0,sizeof ban);
    	for(int i=1;i<=n;i++)ata[i]=i,sz[i]=1;
    	vector<PII>v,g;int r=min(i+BLOK-1,q);
    	for(int j=i;j<=r;j++){
    		if(query[j].ff==1)
    			ban[query[j].ss.ff]=j;
    		else
    			g.pb(mp(query[j].ss.ss,j));
    	}
    	tr(it,edges)
    		if(!ban[it->ss])
    			v.pb(*it);
    	sort(all(g));
		int p=int(v.size())-1,rec;
    	for(int j=int(g.size())-1,ind,k;j>=0;j--){
    		rec=0;
    		while(p>=0 and v[p].ff>=g[j].ff)
				merge(edge[v[p].ss].ff),p--;
			for(k=g[j].ss-1;k>=i;k--){
				ind=query[k].ss.ff;
				if(query[k].ff==1 and !ban1[ind]){
					if(query[k].ss.ss>=g[j].ff)rec+=merge(edge[ind].ff);
					ban1[ind]=1;st.push(ind);
				}
			}
			for(k=g[j].ss+1;k<=r;k++){
				ind=query[k].ss.ff;
				if(query[k].ff==1 and !ban1[ind]){
					if(edge[ind].ss>=g[j].ff)rec+=merge(edge[ind].ff);
					ban1[ind]=1;st.push(ind);	
				}
			}
			ans[g[j].ss]=sz[tap(query[g[j].ss].ss.ff)];
			while(!st.empty())ban1[st.top()]=0,st.pop();
			while(rec--){ //x,y,sz[y]
				int y=history.back().ff.ss;
				sz[history.back().ff.ff]-=history.back().ss;ata[y]=y;
				history.ppb();	
			}
    	}
    	for(int j=i,a;j<=r;j++)
    		if(query[j].ff==1){
    			a=query[j].ss.ff;
    			edges.erase(mp(edge[a].ss,a));
				edge[a].ss=query[j].ss.ss;	
    			edges.insert(mp(edge[a].ss,a));
			}
    }
    for(int i=1;i<=q;i++){
    	if(query[i].ff==2)
			cout<<ans[i]<<"\n";
	} return 0;
}

Subtask #1
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 444 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 50 ms 848 KB Output is correct
4 Correct 13 ms 716 KB Output is correct
5 Correct 33 ms 716 KB Output is correct
6 Correct 29 ms 744 KB Output is correct
7 Correct 30 ms 680 KB Output is correct
8 Correct 31 ms 716 KB Output is correct
9 Correct 32 ms 648 KB Output is correct
10 Correct 31 ms 724 KB Output is correct
11 Correct 37 ms 740 KB Output is correct
12 Correct 33 ms 836 KB Output is correct
13 Correct 41 ms 872 KB Output is correct
14 Correct 39 ms 716 KB Output is correct
15 Correct 36 ms 752 KB Output is correct
16 Correct 30 ms 684 KB Output is correct
17 Correct 30 ms 664 KB Output is correct

Subtask #2
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1599 ms 107456 KB Output is correct
2 Correct 1565 ms 107624 KB Output is correct
3 Correct 1531 ms 107552 KB Output is correct
4 Correct 1642 ms 107640 KB Output is correct
5 Correct 1597 ms 107612 KB Output is correct
6 Correct 2356 ms 107272 KB Output is correct
7 Correct 2411 ms 107252 KB Output is correct
8 Correct 2331 ms 107620 KB Output is correct
9 Correct 127 ms 3488 KB Output is correct
10 Correct 1348 ms 106456 KB Output is correct
11 Correct 1327 ms 106284 KB Output is correct
12 Correct 1250 ms 107076 KB Output is correct
13 Correct 1215 ms 107388 KB Output is correct

Subtask #3
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1229 ms 56224 KB Output is correct
2 Correct 968 ms 16316 KB Output is correct
3 Correct 1346 ms 55924 KB Output is correct
4 Correct 1142 ms 56168 KB Output is correct
5 Correct 123 ms 3520 KB Output is correct
6 Correct 1320 ms 56064 KB Output is correct
7 Correct 1088 ms 56044 KB Output is correct
8 Correct 997 ms 56136 KB Output is correct
9 Correct 779 ms 56160 KB Output is correct
10 Correct 687 ms 56180 KB Output is correct
11 Correct 734 ms 56032 KB Output is correct
12 Correct 653 ms 56112 KB Output is correct

Subtask #4
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1549 ms 112284 KB Output is correct
2 Correct 122 ms 3508 KB Output is correct
3 Correct 184 ms 10136 KB Output is correct
4 Correct 119 ms 10292 KB Output is correct
5 Correct 1042 ms 110872 KB Output is correct
6 Correct 1402 ms 112660 KB Output is correct
7 Correct 1020 ms 110772 KB Output is correct
8 Correct 659 ms 107228 KB Output is correct
9 Correct 665 ms 107452 KB Output is correct
10 Correct 719 ms 107200 KB Output is correct
11 Correct 1075 ms 110024 KB Output is correct
12 Correct 976 ms 110232 KB Output is correct
13 Correct 1080 ms 109988 KB Output is correct
14 Correct 875 ms 110784 KB Output is correct
15 Correct 939 ms 110904 KB Output is correct
16 Correct 1412 ms 112252 KB Output is correct
17 Correct 1422 ms 112228 KB Output is correct
18 Correct 1440 ms 112288 KB Output is correct
19 Correct 1368 ms 112388 KB Output is correct
20 Correct 1117 ms 110528 KB Output is correct
21 Correct 1178 ms 110676 KB Output is correct
22 Correct 1436 ms 111956 KB Output is correct
23 Correct 1020 ms 109268 KB Output is correct

Subtask #5
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1599 ms 107456 KB Output is correct
2 Correct 1565 ms 107624 KB Output is correct
3 Correct 1531 ms 107552 KB Output is correct
4 Correct 1642 ms 107640 KB Output is correct
5 Correct 1597 ms 107612 KB Output is correct
6 Correct 2356 ms 107272 KB Output is correct
7 Correct 2411 ms 107252 KB Output is correct
8 Correct 2331 ms 107620 KB Output is correct
9 Correct 127 ms 3488 KB Output is correct
10 Correct 1348 ms 106456 KB Output is correct
11 Correct 1327 ms 106284 KB Output is correct
12 Correct 1250 ms 107076 KB Output is correct
13 Correct 1215 ms 107388 KB Output is correct
14 Correct 1229 ms 56224 KB Output is correct
15 Correct 968 ms 16316 KB Output is correct
16 Correct 1346 ms 55924 KB Output is correct
17 Correct 1142 ms 56168 KB Output is correct
18 Correct 123 ms 3520 KB Output is correct
19 Correct 1320 ms 56064 KB Output is correct
20 Correct 1088 ms 56044 KB Output is correct
21 Correct 997 ms 56136 KB Output is correct
22 Correct 779 ms 56160 KB Output is correct
23 Correct 687 ms 56180 KB Output is correct
24 Correct 734 ms 56032 KB Output is correct
25 Correct 653 ms 56112 KB Output is correct
26 Correct 1475 ms 107536 KB Output is correct
27 Correct 1823 ms 107312 KB Output is correct
28 Correct 1524 ms 107544 KB Output is correct
29 Correct 1140 ms 107556 KB Output is correct
30 Correct 1777 ms 107476 KB Output is correct
31 Correct 1790 ms 107232 KB Output is correct
32 Correct 1797 ms 107236 KB Output is correct
33 Correct 1470 ms 107500 KB Output is correct
34 Correct 1485 ms 107580 KB Output is correct
35 Correct 1534 ms 107644 KB Output is correct
36 Correct 1184 ms 107424 KB Output is correct
37 Correct 1161 ms 107468 KB Output is correct
38 Correct 1171 ms 107568 KB Output is correct
39 Correct 854 ms 107536 KB Output is correct
40 Correct 911 ms 107588 KB Output is correct
41 Correct 896 ms 107452 KB Output is correct
42 Correct 842 ms 107424 KB Output is correct
43 Correct 807 ms 107460 KB Output is correct
44 Correct 865 ms 107424 KB Output is correct

Subtask #6
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 444 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 50 ms 848 KB Output is correct
4 Correct 13 ms 716 KB Output is correct
5 Correct 33 ms 716 KB Output is correct
6 Correct 29 ms 744 KB Output is correct
7 Correct 30 ms 680 KB Output is correct
8 Correct 31 ms 716 KB Output is correct
9 Correct 32 ms 648 KB Output is correct
10 Correct 31 ms 724 KB Output is correct
11 Correct 37 ms 740 KB Output is correct
12 Correct 33 ms 836 KB Output is correct
13 Correct 41 ms 872 KB Output is correct
14 Correct 39 ms 716 KB Output is correct
15 Correct 36 ms 752 KB Output is correct
16 Correct 30 ms 684 KB Output is correct
17 Correct 30 ms 664 KB Output is correct
18 Correct 1599 ms 107456 KB Output is correct
19 Correct 1565 ms 107624 KB Output is correct
20 Correct 1531 ms 107552 KB Output is correct
21 Correct 1642 ms 107640 KB Output is correct
22 Correct 1597 ms 107612 KB Output is correct
23 Correct 2356 ms 107272 KB Output is correct
24 Correct 2411 ms 107252 KB Output is correct
25 Correct 2331 ms 107620 KB Output is correct
26 Correct 127 ms 3488 KB Output is correct
27 Correct 1348 ms 106456 KB Output is correct
28 Correct 1327 ms 106284 KB Output is correct
29 Correct 1250 ms 107076 KB Output is correct
30 Correct 1215 ms 107388 KB Output is correct
31 Correct 1229 ms 56224 KB Output is correct
32 Correct 968 ms 16316 KB Output is correct
33 Correct 1346 ms 55924 KB Output is correct
34 Correct 1142 ms 56168 KB Output is correct
35 Correct 123 ms 3520 KB Output is correct
36 Correct 1320 ms 56064 KB Output is correct
37 Correct 1088 ms 56044 KB Output is correct
38 Correct 997 ms 56136 KB Output is correct
39 Correct 779 ms 56160 KB Output is correct
40 Correct 687 ms 56180 KB Output is correct
41 Correct 734 ms 56032 KB Output is correct
42 Correct 653 ms 56112 KB Output is correct
43 Correct 1549 ms 112284 KB Output is correct
44 Correct 122 ms 3508 KB Output is correct
45 Correct 184 ms 10136 KB Output is correct
46 Correct 119 ms 10292 KB Output is correct
47 Correct 1042 ms 110872 KB Output is correct
48 Correct 1402 ms 112660 KB Output is correct
49 Correct 1020 ms 110772 KB Output is correct
50 Correct 659 ms 107228 KB Output is correct
51 Correct 665 ms 107452 KB Output is correct
52 Correct 719 ms 107200 KB Output is correct
53 Correct 1075 ms 110024 KB Output is correct
54 Correct 976 ms 110232 KB Output is correct
55 Correct 1080 ms 109988 KB Output is correct
56 Correct 875 ms 110784 KB Output is correct
57 Correct 939 ms 110904 KB Output is correct
58 Correct 1412 ms 112252 KB Output is correct
59 Correct 1422 ms 112228 KB Output is correct
60 Correct 1440 ms 112288 KB Output is correct
61 Correct 1368 ms 112388 KB Output is correct
62 Correct 1117 ms 110528 KB Output is correct
63 Correct 1178 ms 110676 KB Output is correct
64 Correct 1436 ms 111956 KB Output is correct
65 Correct 1020 ms 109268 KB Output is correct
66 Correct 1475 ms 107536 KB Output is correct
67 Correct 1823 ms 107312 KB Output is correct
68 Correct 1524 ms 107544 KB Output is correct
69 Correct 1140 ms 107556 KB Output is correct
70 Correct 1777 ms 107476 KB Output is correct
71 Correct 1790 ms 107232 KB Output is correct
72 Correct 1797 ms 107236 KB Output is correct
73 Correct 1470 ms 107500 KB Output is correct
74 Correct 1485 ms 107580 KB Output is correct
75 Correct 1534 ms 107644 KB Output is correct
76 Correct 1184 ms 107424 KB Output is correct
77 Correct 1161 ms 107468 KB Output is correct
78 Correct 1171 ms 107568 KB Output is correct
79 Correct 854 ms 107536 KB Output is correct
80 Correct 911 ms 107588 KB Output is correct
81 Correct 896 ms 107452 KB Output is correct
82 Correct 842 ms 107424 KB Output is correct
83 Correct 807 ms 107460 KB Output is correct
84 Correct 865 ms 107424 KB Output is correct
85 Correct 2074 ms 112576 KB Output is correct
86 Correct 241 ms 10524 KB Output is correct
87 Correct 178 ms 10412 KB Output is correct
88 Correct 1717 ms 111224 KB Output is correct
89 Correct 2178 ms 112524 KB Output is correct
90 Correct 1760 ms 110784 KB Output is correct
91 Correct 1540 ms 107332 KB Output is correct
92 Correct 1515 ms 107564 KB Output is correct
93 Correct 2246 ms 107420 KB Output is correct
94 Correct 1930 ms 110040 KB Output is correct
95 Correct 1888 ms 110200 KB Output is correct
96 Correct 2318 ms 109968 KB Output is correct
97 Correct 1300 ms 110808 KB Output is correct
98 Correct 1341 ms 110864 KB Output is correct
99 Correct 2196 ms 112296 KB Output is correct
100 Correct 2242 ms 112280 KB Output is correct
101 Correct 2248 ms 112332 KB Output is correct
102 Correct 2213 ms 112404 KB Output is correct
103 Correct 2495 ms 110752 KB Output is correct
104 Correct 2483 ms 110652 KB Output is correct
105 Correct 1640 ms 110756 KB Output is correct
106 Correct 1290 ms 110040 KB Output is correct
107 Correct 1593 ms 110656 KB Output is correct
108 Correct 2235 ms 111964 KB Output is correct
109 Correct 2021 ms 109236 KB Output is correct