# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
743673 | 2023-05-17T16:39:28 Z | Azther0z | Bridges (APIO19_bridges) | C++11 | 2231 ms | 32128 KB |
#include <bits/stdc++.h> using namespace std; const int MX=100000; const int BLOCK=1000; int n,m,q; int A[MX+1],B[MX+1],W[MX+1]; int op[MX+1],X[MX+1],Y[MX+1]; int dsu[MX+1],sz[MX+1],result[MX+1]; stack<int> stk; vector<vector<int>> toMerge(BLOCK+1); bitset<MX+1> changed; int find(int x) { while(x!=dsu[x]) x=dsu[x]; return x; } void merge(int x,int y) { x=find(x),y=find(y); if(x==y) return; if(sz[x]<sz[y]) swap(x,y); sz[x]+=sz[y]; dsu[y]=x; stk.push(y); } void rollback(int x) { while(stk.size()>x) { sz[dsu[stk.top()]]-=sz[stk.top()]; dsu[stk.top()]=stk.top(); stk.pop(); } } void reset() { for(int i=1;i<=n;i++) { dsu[i]=i; sz[i]=1; } changed=0; } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) scanf("%d%d%d",&A[i],&B[i],&W[i]); scanf("%d",&q); for(int i=1;i<=q;i++) scanf("%d%d%d",&op[i],&X[i],&Y[i]); for(int l=1;l<=q;l+=BLOCK) { int r=min(q+1,l+BLOCK); reset(); vector<int> calc,update,unchanged; for(int i=l;i<r;i++) { if(op[i]==1) { changed[X[i]]=true; update.push_back(i); } else { calc.push_back(i); } } for(int i=1;i<=m;i++) if(!changed[i]) unchanged.push_back(i); for(int i=l;i<r;i++) { if(op[i]==1) { W[X[i]]=Y[i]; } else { toMerge[i-l].clear(); for(auto j:update) if(W[X[j]]>=Y[i]) toMerge[i-l].push_back(X[j]); } } sort(calc.begin(),calc.end(),[&](int a,int b){return Y[a]>Y[b];}); sort(unchanged.begin(),unchanged.end(),[&](int a,int b){return W[a]>W[b];}); int idx=0; for(auto i:calc) { while(idx<unchanged.size()&&W[unchanged[idx]]>=Y[i]) { merge(A[unchanged[idx]],B[unchanged[idx]]); idx++; } int prev=stk.size(); for(auto j:toMerge[i-l]) merge(A[j],B[j]); result[i]=sz[find(X[i])]; rollback(prev); } } for(int i=1;i<=q;i++) if(op[i]==2) printf("%d\n",result[i]); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 340 KB | Output is correct |
2 | Correct | 1 ms | 340 KB | Output is correct |
3 | Correct | 36 ms | 2760 KB | Output is correct |
4 | Correct | 5 ms | 604 KB | Output is correct |
5 | Correct | 36 ms | 3028 KB | Output is correct |
6 | Correct | 28 ms | 2728 KB | Output is correct |
7 | Correct | 34 ms | 3532 KB | Output is correct |
8 | Correct | 38 ms | 2764 KB | Output is correct |
9 | Correct | 46 ms | 4288 KB | Output is correct |
10 | Correct | 42 ms | 2816 KB | Output is correct |
11 | Correct | 37 ms | 2732 KB | Output is correct |
12 | Correct | 48 ms | 2964 KB | Output is correct |
13 | Correct | 46 ms | 2836 KB | Output is correct |
14 | Correct | 41 ms | 2800 KB | Output is correct |
15 | Correct | 44 ms | 2724 KB | Output is correct |
16 | Correct | 40 ms | 3988 KB | Output is correct |
17 | Correct | 41 ms | 3392 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1358 ms | 28948 KB | Output is correct |
2 | Correct | 1324 ms | 28772 KB | Output is correct |
3 | Correct | 1321 ms | 28940 KB | Output is correct |
4 | Correct | 1369 ms | 28964 KB | Output is correct |
5 | Correct | 1376 ms | 28984 KB | Output is correct |
6 | Correct | 2074 ms | 30468 KB | Output is correct |
7 | Correct | 2149 ms | 30392 KB | Output is correct |
8 | Correct | 2231 ms | 30588 KB | Output is correct |
9 | Correct | 41 ms | 3440 KB | Output is correct |
10 | Correct | 1175 ms | 29452 KB | Output is correct |
11 | Correct | 1117 ms | 29620 KB | Output is correct |
12 | Correct | 1176 ms | 27056 KB | Output is correct |
13 | Correct | 1168 ms | 30128 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1123 ms | 21140 KB | Output is correct |
2 | Correct | 899 ms | 11156 KB | Output is correct |
3 | Correct | 1342 ms | 22552 KB | Output is correct |
4 | Correct | 1124 ms | 21284 KB | Output is correct |
5 | Correct | 40 ms | 3396 KB | Output is correct |
6 | Correct | 1248 ms | 21012 KB | Output is correct |
7 | Correct | 1006 ms | 20672 KB | Output is correct |
8 | Correct | 840 ms | 20600 KB | Output is correct |
9 | Correct | 723 ms | 19312 KB | Output is correct |
10 | Correct | 594 ms | 19256 KB | Output is correct |
11 | Correct | 717 ms | 22076 KB | Output is correct |
12 | Correct | 613 ms | 21968 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1478 ms | 28528 KB | Output is correct |
2 | Correct | 39 ms | 3356 KB | Output is correct |
3 | Correct | 156 ms | 4404 KB | Output is correct |
4 | Correct | 70 ms | 4596 KB | Output is correct |
5 | Correct | 804 ms | 27032 KB | Output is correct |
6 | Correct | 1447 ms | 28520 KB | Output is correct |
7 | Correct | 735 ms | 27168 KB | Output is correct |
8 | Correct | 728 ms | 26480 KB | Output is correct |
9 | Correct | 720 ms | 26640 KB | Output is correct |
10 | Correct | 684 ms | 26628 KB | Output is correct |
11 | Correct | 1133 ms | 27908 KB | Output is correct |
12 | Correct | 1095 ms | 28008 KB | Output is correct |
13 | Correct | 1136 ms | 27936 KB | Output is correct |
14 | Correct | 669 ms | 27208 KB | Output is correct |
15 | Correct | 687 ms | 27124 KB | Output is correct |
16 | Correct | 1450 ms | 28932 KB | Output is correct |
17 | Correct | 1471 ms | 28684 KB | Output is correct |
18 | Correct | 1453 ms | 29176 KB | Output is correct |
19 | Correct | 1412 ms | 28944 KB | Output is correct |
20 | Correct | 1163 ms | 28388 KB | Output is correct |
21 | Correct | 1180 ms | 28176 KB | Output is correct |
22 | Correct | 1358 ms | 28312 KB | Output is correct |
23 | Correct | 791 ms | 24828 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1358 ms | 28948 KB | Output is correct |
2 | Correct | 1324 ms | 28772 KB | Output is correct |
3 | Correct | 1321 ms | 28940 KB | Output is correct |
4 | Correct | 1369 ms | 28964 KB | Output is correct |
5 | Correct | 1376 ms | 28984 KB | Output is correct |
6 | Correct | 2074 ms | 30468 KB | Output is correct |
7 | Correct | 2149 ms | 30392 KB | Output is correct |
8 | Correct | 2231 ms | 30588 KB | Output is correct |
9 | Correct | 41 ms | 3440 KB | Output is correct |
10 | Correct | 1175 ms | 29452 KB | Output is correct |
11 | Correct | 1117 ms | 29620 KB | Output is correct |
12 | Correct | 1176 ms | 27056 KB | Output is correct |
13 | Correct | 1168 ms | 30128 KB | Output is correct |
14 | Correct | 1123 ms | 21140 KB | Output is correct |
15 | Correct | 899 ms | 11156 KB | Output is correct |
16 | Correct | 1342 ms | 22552 KB | Output is correct |
17 | Correct | 1124 ms | 21284 KB | Output is correct |
18 | Correct | 40 ms | 3396 KB | Output is correct |
19 | Correct | 1248 ms | 21012 KB | Output is correct |
20 | Correct | 1006 ms | 20672 KB | Output is correct |
21 | Correct | 840 ms | 20600 KB | Output is correct |
22 | Correct | 723 ms | 19312 KB | Output is correct |
23 | Correct | 594 ms | 19256 KB | Output is correct |
24 | Correct | 717 ms | 22076 KB | Output is correct |
25 | Correct | 613 ms | 21968 KB | Output is correct |
26 | Correct | 1331 ms | 29148 KB | Output is correct |
27 | Correct | 1728 ms | 30512 KB | Output is correct |
28 | Correct | 1354 ms | 28860 KB | Output is correct |
29 | Correct | 942 ms | 28404 KB | Output is correct |
30 | Correct | 1579 ms | 30460 KB | Output is correct |
31 | Correct | 1597 ms | 30428 KB | Output is correct |
32 | Correct | 1648 ms | 30420 KB | Output is correct |
33 | Correct | 1333 ms | 28848 KB | Output is correct |
34 | Correct | 1339 ms | 28788 KB | Output is correct |
35 | Correct | 1339 ms | 28968 KB | Output is correct |
36 | Correct | 974 ms | 28476 KB | Output is correct |
37 | Correct | 974 ms | 28504 KB | Output is correct |
38 | Correct | 979 ms | 28572 KB | Output is correct |
39 | Correct | 788 ms | 27256 KB | Output is correct |
40 | Correct | 765 ms | 26984 KB | Output is correct |
41 | Correct | 773 ms | 27148 KB | Output is correct |
42 | Correct | 781 ms | 29112 KB | Output is correct |
43 | Correct | 795 ms | 29008 KB | Output is correct |
44 | Correct | 787 ms | 28952 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 340 KB | Output is correct |
2 | Correct | 1 ms | 340 KB | Output is correct |
3 | Correct | 36 ms | 2760 KB | Output is correct |
4 | Correct | 5 ms | 604 KB | Output is correct |
5 | Correct | 36 ms | 3028 KB | Output is correct |
6 | Correct | 28 ms | 2728 KB | Output is correct |
7 | Correct | 34 ms | 3532 KB | Output is correct |
8 | Correct | 38 ms | 2764 KB | Output is correct |
9 | Correct | 46 ms | 4288 KB | Output is correct |
10 | Correct | 42 ms | 2816 KB | Output is correct |
11 | Correct | 37 ms | 2732 KB | Output is correct |
12 | Correct | 48 ms | 2964 KB | Output is correct |
13 | Correct | 46 ms | 2836 KB | Output is correct |
14 | Correct | 41 ms | 2800 KB | Output is correct |
15 | Correct | 44 ms | 2724 KB | Output is correct |
16 | Correct | 40 ms | 3988 KB | Output is correct |
17 | Correct | 41 ms | 3392 KB | Output is correct |
18 | Correct | 1358 ms | 28948 KB | Output is correct |
19 | Correct | 1324 ms | 28772 KB | Output is correct |
20 | Correct | 1321 ms | 28940 KB | Output is correct |
21 | Correct | 1369 ms | 28964 KB | Output is correct |
22 | Correct | 1376 ms | 28984 KB | Output is correct |
23 | Correct | 2074 ms | 30468 KB | Output is correct |
24 | Correct | 2149 ms | 30392 KB | Output is correct |
25 | Correct | 2231 ms | 30588 KB | Output is correct |
26 | Correct | 41 ms | 3440 KB | Output is correct |
27 | Correct | 1175 ms | 29452 KB | Output is correct |
28 | Correct | 1117 ms | 29620 KB | Output is correct |
29 | Correct | 1176 ms | 27056 KB | Output is correct |
30 | Correct | 1168 ms | 30128 KB | Output is correct |
31 | Correct | 1123 ms | 21140 KB | Output is correct |
32 | Correct | 899 ms | 11156 KB | Output is correct |
33 | Correct | 1342 ms | 22552 KB | Output is correct |
34 | Correct | 1124 ms | 21284 KB | Output is correct |
35 | Correct | 40 ms | 3396 KB | Output is correct |
36 | Correct | 1248 ms | 21012 KB | Output is correct |
37 | Correct | 1006 ms | 20672 KB | Output is correct |
38 | Correct | 840 ms | 20600 KB | Output is correct |
39 | Correct | 723 ms | 19312 KB | Output is correct |
40 | Correct | 594 ms | 19256 KB | Output is correct |
41 | Correct | 717 ms | 22076 KB | Output is correct |
42 | Correct | 613 ms | 21968 KB | Output is correct |
43 | Correct | 1478 ms | 28528 KB | Output is correct |
44 | Correct | 39 ms | 3356 KB | Output is correct |
45 | Correct | 156 ms | 4404 KB | Output is correct |
46 | Correct | 70 ms | 4596 KB | Output is correct |
47 | Correct | 804 ms | 27032 KB | Output is correct |
48 | Correct | 1447 ms | 28520 KB | Output is correct |
49 | Correct | 735 ms | 27168 KB | Output is correct |
50 | Correct | 728 ms | 26480 KB | Output is correct |
51 | Correct | 720 ms | 26640 KB | Output is correct |
52 | Correct | 684 ms | 26628 KB | Output is correct |
53 | Correct | 1133 ms | 27908 KB | Output is correct |
54 | Correct | 1095 ms | 28008 KB | Output is correct |
55 | Correct | 1136 ms | 27936 KB | Output is correct |
56 | Correct | 669 ms | 27208 KB | Output is correct |
57 | Correct | 687 ms | 27124 KB | Output is correct |
58 | Correct | 1450 ms | 28932 KB | Output is correct |
59 | Correct | 1471 ms | 28684 KB | Output is correct |
60 | Correct | 1453 ms | 29176 KB | Output is correct |
61 | Correct | 1412 ms | 28944 KB | Output is correct |
62 | Correct | 1163 ms | 28388 KB | Output is correct |
63 | Correct | 1180 ms | 28176 KB | Output is correct |
64 | Correct | 1358 ms | 28312 KB | Output is correct |
65 | Correct | 791 ms | 24828 KB | Output is correct |
66 | Correct | 1331 ms | 29148 KB | Output is correct |
67 | Correct | 1728 ms | 30512 KB | Output is correct |
68 | Correct | 1354 ms | 28860 KB | Output is correct |
69 | Correct | 942 ms | 28404 KB | Output is correct |
70 | Correct | 1579 ms | 30460 KB | Output is correct |
71 | Correct | 1597 ms | 30428 KB | Output is correct |
72 | Correct | 1648 ms | 30420 KB | Output is correct |
73 | Correct | 1333 ms | 28848 KB | Output is correct |
74 | Correct | 1339 ms | 28788 KB | Output is correct |
75 | Correct | 1339 ms | 28968 KB | Output is correct |
76 | Correct | 974 ms | 28476 KB | Output is correct |
77 | Correct | 974 ms | 28504 KB | Output is correct |
78 | Correct | 979 ms | 28572 KB | Output is correct |
79 | Correct | 788 ms | 27256 KB | Output is correct |
80 | Correct | 765 ms | 26984 KB | Output is correct |
81 | Correct | 773 ms | 27148 KB | Output is correct |
82 | Correct | 781 ms | 29112 KB | Output is correct |
83 | Correct | 795 ms | 29008 KB | Output is correct |
84 | Correct | 787 ms | 28952 KB | Output is correct |
85 | Correct | 1825 ms | 30940 KB | Output is correct |
86 | Correct | 183 ms | 6436 KB | Output is correct |
87 | Correct | 117 ms | 7896 KB | Output is correct |
88 | Correct | 1163 ms | 31192 KB | Output is correct |
89 | Correct | 1816 ms | 30996 KB | Output is correct |
90 | Correct | 1145 ms | 31080 KB | Output is correct |
91 | Correct | 1430 ms | 28732 KB | Output is correct |
92 | Correct | 1418 ms | 28960 KB | Output is correct |
93 | Correct | 2113 ms | 30184 KB | Output is correct |
94 | Correct | 1567 ms | 30320 KB | Output is correct |
95 | Correct | 1548 ms | 30332 KB | Output is correct |
96 | Correct | 1854 ms | 31888 KB | Output is correct |
97 | Correct | 812 ms | 27668 KB | Output is correct |
98 | Correct | 893 ms | 30904 KB | Output is correct |
99 | Correct | 1875 ms | 31336 KB | Output is correct |
100 | Correct | 1841 ms | 30876 KB | Output is correct |
101 | Correct | 1888 ms | 31156 KB | Output is correct |
102 | Correct | 1926 ms | 31276 KB | Output is correct |
103 | Correct | 2039 ms | 32064 KB | Output is correct |
104 | Correct | 2021 ms | 32128 KB | Output is correct |
105 | Correct | 1554 ms | 31892 KB | Output is correct |
106 | Correct | 1181 ms | 31756 KB | Output is correct |
107 | Correct | 1449 ms | 28696 KB | Output is correct |
108 | Correct | 1901 ms | 31200 KB | Output is correct |
109 | Correct | 1360 ms | 28856 KB | Output is correct |