# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
124531 | 2019-07-03T13:28:01 Z | TadijaSebez | Bridges (APIO19_bridges) | C++11 | 2748 ms | 49156 KB |
#include <bits/stdc++.h> using namespace std; #define pb push_back const int N=100050; const int B=1050; int w[N],u[N],v[N]; bool ban[N]; int t[N],b[N],c[N]; vector<int> use[B]; struct DSU { int p[N],sz[N]; void init(){ for(int i=0;i<N;i++) p[i]=i,sz[i]=1;} void init(int n){ for(int i=1;i<=n;i++) p[i]=i,sz[i]=1;} DSU(){ init();} int Find(int u){ return u==p[u]?u:Find(p[u]);} stack<int> was; void Union(int u, int v) { u=Find(u); v=Find(v); if(u==v){ was.push(0);return;} if(sz[u]>sz[v]) { p[v]=u; sz[u]+=sz[v]; was.push(v); } else { p[u]=v; sz[v]+=sz[u]; was.push(u); } } void Undo() { int u=was.top(); was.pop(); if(u) { sz[p[u]]-=sz[u]; p[u]=u; } } int Get(int u){ return sz[Find(u)];} } DS; int ans[N]; int main() { int n,m,q; scanf("%i %i",&n,&m); for(int i=1;i<=m;i++) scanf("%i %i %i",&u[i],&v[i],&w[i]); scanf("%i",&q); for(int i=0;i<q;i++) scanf("%i %i %i",&t[i],&b[i],&c[i]); for(int l=0;l<q;l+=B) { DS.init(n); int r=min(q,l+B)-1; for(int i=1;i<=m;i++) ban[i]=0; vector<int> bn,id; for(int i=l;i<=r;i++) if(t[i]==1) ban[b[i]]=1; for(int i=1;i<=m;i++) { if(ban[i]) bn.pb(i); else id.pb(i); } sort(id.begin(),id.end(),[&](int i, int j){ return w[i]>w[j];}); for(int i=l;i<=r;i++) use[i-l].clear(); vector<int> qs; for(int i=l;i<=r;i++) { if(t[i]==1) w[b[i]]=c[i]; else { for(int j=0;j<bn.size();j++) if(w[bn[j]]>=c[i]) use[i-l].pb(bn[j]); qs.pb(i); } } sort(qs.begin(),qs.end(),[&](int i, int j){ return c[i]>c[j];}); for(int i=0,j=0;i<qs.size();i++) { while(j<id.size() && w[id[j]]>=c[qs[i]]) { DS.Union(u[id[j]],v[id[j]]); j++; } for(int k=0;k<use[qs[i]-l].size();k++) { int e=use[qs[i]-l][k]; DS.Union(u[e],v[e]); } ans[qs[i]]=DS.Get(b[qs[i]]); for(int k=0;k<use[qs[i]-l].size();k++) DS.Undo(); } } for(int i=0;i<q;i++) if(t[i]==2) printf("%i\n",ans[i]); return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 1144 KB | Output is correct |
2 | Correct | 3 ms | 1144 KB | Output is correct |
3 | Correct | 48 ms | 3576 KB | Output is correct |
4 | Correct | 7 ms | 1528 KB | Output is correct |
5 | Correct | 17 ms | 2040 KB | Output is correct |
6 | Correct | 15 ms | 1912 KB | Output is correct |
7 | Correct | 17 ms | 1912 KB | Output is correct |
8 | Correct | 18 ms | 1912 KB | Output is correct |
9 | Correct | 22 ms | 1912 KB | Output is correct |
10 | Correct | 18 ms | 2040 KB | Output is correct |
11 | Correct | 18 ms | 2040 KB | Output is correct |
12 | Correct | 20 ms | 2040 KB | Output is correct |
13 | Correct | 26 ms | 2396 KB | Output is correct |
14 | Correct | 24 ms | 2220 KB | Output is correct |
15 | Correct | 21 ms | 2040 KB | Output is correct |
16 | Correct | 19 ms | 1912 KB | Output is correct |
17 | Correct | 19 ms | 1912 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1602 ms | 27248 KB | Output is correct |
2 | Correct | 1595 ms | 27256 KB | Output is correct |
3 | Correct | 1642 ms | 27216 KB | Output is correct |
4 | Correct | 1608 ms | 27180 KB | Output is correct |
5 | Correct | 1601 ms | 27292 KB | Output is correct |
6 | Correct | 2623 ms | 28048 KB | Output is correct |
7 | Correct | 2609 ms | 28020 KB | Output is correct |
8 | Correct | 2608 ms | 28120 KB | Output is correct |
9 | Correct | 49 ms | 3192 KB | Output is correct |
10 | Correct | 1396 ms | 28148 KB | Output is correct |
11 | Correct | 1300 ms | 27968 KB | Output is correct |
12 | Correct | 1364 ms | 24748 KB | Output is correct |
13 | Correct | 1391 ms | 27596 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1371 ms | 20060 KB | Output is correct |
2 | Correct | 996 ms | 10752 KB | Output is correct |
3 | Correct | 1608 ms | 20992 KB | Output is correct |
4 | Correct | 1329 ms | 20056 KB | Output is correct |
5 | Correct | 49 ms | 3064 KB | Output is correct |
6 | Correct | 1513 ms | 20424 KB | Output is correct |
7 | Correct | 1184 ms | 19864 KB | Output is correct |
8 | Correct | 1020 ms | 19504 KB | Output is correct |
9 | Correct | 819 ms | 17308 KB | Output is correct |
10 | Correct | 739 ms | 17276 KB | Output is correct |
11 | Correct | 913 ms | 20476 KB | Output is correct |
12 | Correct | 763 ms | 20204 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1860 ms | 44456 KB | Output is correct |
2 | Correct | 49 ms | 3192 KB | Output is correct |
3 | Correct | 202 ms | 7516 KB | Output is correct |
4 | Correct | 96 ms | 7516 KB | Output is correct |
5 | Correct | 939 ms | 44596 KB | Output is correct |
6 | Correct | 1807 ms | 44460 KB | Output is correct |
7 | Correct | 949 ms | 44632 KB | Output is correct |
8 | Correct | 874 ms | 23760 KB | Output is correct |
9 | Correct | 835 ms | 23884 KB | Output is correct |
10 | Correct | 825 ms | 23900 KB | Output is correct |
11 | Correct | 1336 ms | 34188 KB | Output is correct |
12 | Correct | 1317 ms | 34132 KB | Output is correct |
13 | Correct | 1373 ms | 34360 KB | Output is correct |
14 | Correct | 852 ms | 44580 KB | Output is correct |
15 | Correct | 893 ms | 44572 KB | Output is correct |
16 | Correct | 1825 ms | 44108 KB | Output is correct |
17 | Correct | 1844 ms | 44044 KB | Output is correct |
18 | Correct | 1852 ms | 44240 KB | Output is correct |
19 | Correct | 1831 ms | 44168 KB | Output is correct |
20 | Correct | 1508 ms | 37772 KB | Output is correct |
21 | Correct | 1525 ms | 37984 KB | Output is correct |
22 | Correct | 1759 ms | 42688 KB | Output is correct |
23 | Correct | 1057 ms | 36832 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1602 ms | 27248 KB | Output is correct |
2 | Correct | 1595 ms | 27256 KB | Output is correct |
3 | Correct | 1642 ms | 27216 KB | Output is correct |
4 | Correct | 1608 ms | 27180 KB | Output is correct |
5 | Correct | 1601 ms | 27292 KB | Output is correct |
6 | Correct | 2623 ms | 28048 KB | Output is correct |
7 | Correct | 2609 ms | 28020 KB | Output is correct |
8 | Correct | 2608 ms | 28120 KB | Output is correct |
9 | Correct | 49 ms | 3192 KB | Output is correct |
10 | Correct | 1396 ms | 28148 KB | Output is correct |
11 | Correct | 1300 ms | 27968 KB | Output is correct |
12 | Correct | 1364 ms | 24748 KB | Output is correct |
13 | Correct | 1391 ms | 27596 KB | Output is correct |
14 | Correct | 1371 ms | 20060 KB | Output is correct |
15 | Correct | 996 ms | 10752 KB | Output is correct |
16 | Correct | 1608 ms | 20992 KB | Output is correct |
17 | Correct | 1329 ms | 20056 KB | Output is correct |
18 | Correct | 49 ms | 3064 KB | Output is correct |
19 | Correct | 1513 ms | 20424 KB | Output is correct |
20 | Correct | 1184 ms | 19864 KB | Output is correct |
21 | Correct | 1020 ms | 19504 KB | Output is correct |
22 | Correct | 819 ms | 17308 KB | Output is correct |
23 | Correct | 739 ms | 17276 KB | Output is correct |
24 | Correct | 913 ms | 20476 KB | Output is correct |
25 | Correct | 763 ms | 20204 KB | Output is correct |
26 | Correct | 1782 ms | 27464 KB | Output is correct |
27 | Correct | 2188 ms | 28132 KB | Output is correct |
28 | Correct | 1948 ms | 27400 KB | Output is correct |
29 | Correct | 1229 ms | 26572 KB | Output is correct |
30 | Correct | 2101 ms | 28104 KB | Output is correct |
31 | Correct | 2144 ms | 28076 KB | Output is correct |
32 | Correct | 2209 ms | 28076 KB | Output is correct |
33 | Correct | 1765 ms | 27224 KB | Output is correct |
34 | Correct | 1781 ms | 27272 KB | Output is correct |
35 | Correct | 1788 ms | 27104 KB | Output is correct |
36 | Correct | 1292 ms | 26464 KB | Output is correct |
37 | Correct | 1269 ms | 26484 KB | Output is correct |
38 | Correct | 1247 ms | 26440 KB | Output is correct |
39 | Correct | 987 ms | 24820 KB | Output is correct |
40 | Correct | 961 ms | 24972 KB | Output is correct |
41 | Correct | 971 ms | 24744 KB | Output is correct |
42 | Correct | 975 ms | 27056 KB | Output is correct |
43 | Correct | 962 ms | 27132 KB | Output is correct |
44 | Correct | 974 ms | 26948 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 1144 KB | Output is correct |
2 | Correct | 3 ms | 1144 KB | Output is correct |
3 | Correct | 48 ms | 3576 KB | Output is correct |
4 | Correct | 7 ms | 1528 KB | Output is correct |
5 | Correct | 17 ms | 2040 KB | Output is correct |
6 | Correct | 15 ms | 1912 KB | Output is correct |
7 | Correct | 17 ms | 1912 KB | Output is correct |
8 | Correct | 18 ms | 1912 KB | Output is correct |
9 | Correct | 22 ms | 1912 KB | Output is correct |
10 | Correct | 18 ms | 2040 KB | Output is correct |
11 | Correct | 18 ms | 2040 KB | Output is correct |
12 | Correct | 20 ms | 2040 KB | Output is correct |
13 | Correct | 26 ms | 2396 KB | Output is correct |
14 | Correct | 24 ms | 2220 KB | Output is correct |
15 | Correct | 21 ms | 2040 KB | Output is correct |
16 | Correct | 19 ms | 1912 KB | Output is correct |
17 | Correct | 19 ms | 1912 KB | Output is correct |
18 | Correct | 1602 ms | 27248 KB | Output is correct |
19 | Correct | 1595 ms | 27256 KB | Output is correct |
20 | Correct | 1642 ms | 27216 KB | Output is correct |
21 | Correct | 1608 ms | 27180 KB | Output is correct |
22 | Correct | 1601 ms | 27292 KB | Output is correct |
23 | Correct | 2623 ms | 28048 KB | Output is correct |
24 | Correct | 2609 ms | 28020 KB | Output is correct |
25 | Correct | 2608 ms | 28120 KB | Output is correct |
26 | Correct | 49 ms | 3192 KB | Output is correct |
27 | Correct | 1396 ms | 28148 KB | Output is correct |
28 | Correct | 1300 ms | 27968 KB | Output is correct |
29 | Correct | 1364 ms | 24748 KB | Output is correct |
30 | Correct | 1391 ms | 27596 KB | Output is correct |
31 | Correct | 1371 ms | 20060 KB | Output is correct |
32 | Correct | 996 ms | 10752 KB | Output is correct |
33 | Correct | 1608 ms | 20992 KB | Output is correct |
34 | Correct | 1329 ms | 20056 KB | Output is correct |
35 | Correct | 49 ms | 3064 KB | Output is correct |
36 | Correct | 1513 ms | 20424 KB | Output is correct |
37 | Correct | 1184 ms | 19864 KB | Output is correct |
38 | Correct | 1020 ms | 19504 KB | Output is correct |
39 | Correct | 819 ms | 17308 KB | Output is correct |
40 | Correct | 739 ms | 17276 KB | Output is correct |
41 | Correct | 913 ms | 20476 KB | Output is correct |
42 | Correct | 763 ms | 20204 KB | Output is correct |
43 | Correct | 1860 ms | 44456 KB | Output is correct |
44 | Correct | 49 ms | 3192 KB | Output is correct |
45 | Correct | 202 ms | 7516 KB | Output is correct |
46 | Correct | 96 ms | 7516 KB | Output is correct |
47 | Correct | 939 ms | 44596 KB | Output is correct |
48 | Correct | 1807 ms | 44460 KB | Output is correct |
49 | Correct | 949 ms | 44632 KB | Output is correct |
50 | Correct | 874 ms | 23760 KB | Output is correct |
51 | Correct | 835 ms | 23884 KB | Output is correct |
52 | Correct | 825 ms | 23900 KB | Output is correct |
53 | Correct | 1336 ms | 34188 KB | Output is correct |
54 | Correct | 1317 ms | 34132 KB | Output is correct |
55 | Correct | 1373 ms | 34360 KB | Output is correct |
56 | Correct | 852 ms | 44580 KB | Output is correct |
57 | Correct | 893 ms | 44572 KB | Output is correct |
58 | Correct | 1825 ms | 44108 KB | Output is correct |
59 | Correct | 1844 ms | 44044 KB | Output is correct |
60 | Correct | 1852 ms | 44240 KB | Output is correct |
61 | Correct | 1831 ms | 44168 KB | Output is correct |
62 | Correct | 1508 ms | 37772 KB | Output is correct |
63 | Correct | 1525 ms | 37984 KB | Output is correct |
64 | Correct | 1759 ms | 42688 KB | Output is correct |
65 | Correct | 1057 ms | 36832 KB | Output is correct |
66 | Correct | 1782 ms | 27464 KB | Output is correct |
67 | Correct | 2188 ms | 28132 KB | Output is correct |
68 | Correct | 1948 ms | 27400 KB | Output is correct |
69 | Correct | 1229 ms | 26572 KB | Output is correct |
70 | Correct | 2101 ms | 28104 KB | Output is correct |
71 | Correct | 2144 ms | 28076 KB | Output is correct |
72 | Correct | 2209 ms | 28076 KB | Output is correct |
73 | Correct | 1765 ms | 27224 KB | Output is correct |
74 | Correct | 1781 ms | 27272 KB | Output is correct |
75 | Correct | 1788 ms | 27104 KB | Output is correct |
76 | Correct | 1292 ms | 26464 KB | Output is correct |
77 | Correct | 1269 ms | 26484 KB | Output is correct |
78 | Correct | 1247 ms | 26440 KB | Output is correct |
79 | Correct | 987 ms | 24820 KB | Output is correct |
80 | Correct | 961 ms | 24972 KB | Output is correct |
81 | Correct | 971 ms | 24744 KB | Output is correct |
82 | Correct | 975 ms | 27056 KB | Output is correct |
83 | Correct | 962 ms | 27132 KB | Output is correct |
84 | Correct | 974 ms | 26948 KB | Output is correct |
85 | Correct | 2582 ms | 48660 KB | Output is correct |
86 | Correct | 264 ms | 10204 KB | Output is correct |
87 | Correct | 165 ms | 12000 KB | Output is correct |
88 | Correct | 1671 ms | 49156 KB | Output is correct |
89 | Correct | 2588 ms | 47916 KB | Output is correct |
90 | Correct | 1629 ms | 48664 KB | Output is correct |
91 | Correct | 1809 ms | 27408 KB | Output is correct |
92 | Correct | 1830 ms | 27532 KB | Output is correct |
93 | Correct | 2722 ms | 28004 KB | Output is correct |
94 | Correct | 2209 ms | 37736 KB | Output is correct |
95 | Correct | 2280 ms | 37552 KB | Output is correct |
96 | Correct | 2519 ms | 38540 KB | Output is correct |
97 | Correct | 1209 ms | 45516 KB | Output is correct |
98 | Correct | 1388 ms | 47964 KB | Output is correct |
99 | Correct | 2656 ms | 47652 KB | Output is correct |
100 | Correct | 2583 ms | 47456 KB | Output is correct |
101 | Correct | 2683 ms | 47572 KB | Output is correct |
102 | Correct | 2662 ms | 47432 KB | Output is correct |
103 | Correct | 2748 ms | 41784 KB | Output is correct |
104 | Correct | 2669 ms | 41668 KB | Output is correct |
105 | Correct | 2101 ms | 43736 KB | Output is correct |
106 | Correct | 1649 ms | 40200 KB | Output is correct |
107 | Correct | 1863 ms | 41332 KB | Output is correct |
108 | Correct | 2662 ms | 49092 KB | Output is correct |
109 | Correct | 1936 ms | 42520 KB | Output is correct |