# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
242085 | 2020-06-26T17:39:15 Z | mhy908 | Bridges (APIO19_bridges) | C++14 | 2355 ms | 9332 KB |
#include <bits/stdc++.h> #define eb emplace_back #define mp make_pair #define F first #define S second #define all(x) x.begin(), x.end() using namespace std; typedef pair<int, int> pii; int n, m, q, sq; pair<pii, int> ed[100010]; pair<int, pii> qu[100010]; pii stk[100010]; int par[50010], sz[50010], re, ans[100010]; inline void init(){for(int i=1; i<=50000; i++)par[i]=i, sz[i]=1; re=0;} int findpar(int num){return num==par[num]?num:findpar(par[num]);} inline void mergepar(int a, int b){ a=findpar(a); b=findpar(b); if(a==b)return; if(sz[a]<sz[b])swap(a, b); sz[a]+=sz[b]; par[b]=a; stk[++re]=mp(a, b); } inline void rollback(){ int a=stk[re].F, b=stk[re].S; re--; par[b]=b; sz[a]-=sz[b]; } bool ch[100010]; vector<pii> noch, query; vector<int> ych; inline void do_query(int s, int e){ noch.clear(); query.clear(); ych.clear(); memset(ch, 0, sizeof ch); init(); for(int i=s; i<=e; i++){ if(qu[i].F==2)query.eb(qu[i].S.S, i); else ch[qu[i].S.F]=true; } for(int i=1; i<=m; i++){ if(!ch[i])noch.eb(ed[i].S, i); else ych.eb(i); } sort(all(query), greater<pii>()); sort(all(noch), greater<pii>()); int pv=0; for(auto i:query){ for(; pv<noch.size(); pv++){ if(noch[pv].F<i.F)break; mergepar(ed[noch[pv].S].F.F, ed[noch[pv].S].F.S); } int tmp=re; for(int j=i.S; j>=s; j--){ if(qu[j].F==1&&ch[qu[j].S.F]){ ch[qu[j].S.F]=false; if(qu[j].S.S>=i.F)mergepar(ed[qu[j].S.F].F.F, ed[qu[j].S.F].F.S); } } for(auto j:ych){ if(ch[j]&&ed[j].S>=i.F)mergepar(ed[j].F.F, ed[j].F.S); ch[j]=true; } ans[i.S]=sz[findpar(qu[i.S].S.F)]; while(re>tmp)rollback(); } for(int i=s; i<=e; i++){ if(qu[i].F==1)ed[qu[i].S.F].S=qu[i].S.S; } } int main(){ scanf("%d %d", &n, &m); for(int i=1; i<=m; i++)scanf("%d %d %d", &ed[i].F.F, &ed[i].F.S, &ed[i].S); scanf("%d", &q); for(int i=1; i<=q; i++)scanf("%d %d %d", &qu[i].F, &qu[i].S.F, &qu[i].S.S); sq=800; for(int st=1; st<=q; st+=sq){ int fin=min(q, st+sq-1); do_query(st, fin); } for(int i=1; i<=q; i++){ if(qu[i].F==2)printf("%d\n", ans[i]); } }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 768 KB | Output is correct |
2 | Correct | 5 ms | 768 KB | Output is correct |
3 | Correct | 35 ms | 1024 KB | Output is correct |
4 | Correct | 14 ms | 1024 KB | Output is correct |
5 | Correct | 28 ms | 1024 KB | Output is correct |
6 | Correct | 24 ms | 1024 KB | Output is correct |
7 | Correct | 24 ms | 1024 KB | Output is correct |
8 | Correct | 26 ms | 1160 KB | Output is correct |
9 | Correct | 23 ms | 1024 KB | Output is correct |
10 | Correct | 25 ms | 1024 KB | Output is correct |
11 | Correct | 26 ms | 1024 KB | Output is correct |
12 | Correct | 26 ms | 1024 KB | Output is correct |
13 | Correct | 32 ms | 1024 KB | Output is correct |
14 | Correct | 31 ms | 1024 KB | Output is correct |
15 | Correct | 28 ms | 1024 KB | Output is correct |
16 | Correct | 24 ms | 1024 KB | Output is correct |
17 | Correct | 24 ms | 1024 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1363 ms | 4120 KB | Output is correct |
2 | Correct | 1360 ms | 4316 KB | Output is correct |
3 | Correct | 1385 ms | 4216 KB | Output is correct |
4 | Correct | 1413 ms | 4172 KB | Output is correct |
5 | Correct | 1386 ms | 4312 KB | Output is correct |
6 | Correct | 1828 ms | 4336 KB | Output is correct |
7 | Correct | 1827 ms | 4468 KB | Output is correct |
8 | Correct | 1857 ms | 4464 KB | Output is correct |
9 | Correct | 99 ms | 2692 KB | Output is correct |
10 | Correct | 1193 ms | 4352 KB | Output is correct |
11 | Correct | 1230 ms | 4336 KB | Output is correct |
12 | Correct | 1272 ms | 4592 KB | Output is correct |
13 | Correct | 1219 ms | 4204 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1054 ms | 3576 KB | Output is correct |
2 | Correct | 666 ms | 3020 KB | Output is correct |
3 | Correct | 1136 ms | 3828 KB | Output is correct |
4 | Correct | 1020 ms | 3828 KB | Output is correct |
5 | Correct | 92 ms | 2680 KB | Output is correct |
6 | Correct | 1101 ms | 3852 KB | Output is correct |
7 | Correct | 955 ms | 3700 KB | Output is correct |
8 | Correct | 902 ms | 3704 KB | Output is correct |
9 | Correct | 771 ms | 4084 KB | Output is correct |
10 | Correct | 708 ms | 4084 KB | Output is correct |
11 | Correct | 730 ms | 3572 KB | Output is correct |
12 | Correct | 684 ms | 3572 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1906 ms | 5444 KB | Output is correct |
2 | Correct | 105 ms | 3960 KB | Output is correct |
3 | Correct | 201 ms | 5232 KB | Output is correct |
4 | Correct | 133 ms | 5232 KB | Output is correct |
5 | Correct | 1696 ms | 7916 KB | Output is correct |
6 | Correct | 1770 ms | 9292 KB | Output is correct |
7 | Correct | 1746 ms | 7788 KB | Output is correct |
8 | Correct | 932 ms | 7000 KB | Output is correct |
9 | Correct | 906 ms | 7044 KB | Output is correct |
10 | Correct | 922 ms | 6896 KB | Output is correct |
11 | Correct | 1368 ms | 7948 KB | Output is correct |
12 | Correct | 1366 ms | 8168 KB | Output is correct |
13 | Correct | 1394 ms | 8040 KB | Output is correct |
14 | Correct | 1481 ms | 8228 KB | Output is correct |
15 | Correct | 1629 ms | 7788 KB | Output is correct |
16 | Correct | 1799 ms | 9196 KB | Output is correct |
17 | Correct | 1854 ms | 9108 KB | Output is correct |
18 | Correct | 1844 ms | 9224 KB | Output is correct |
19 | Correct | 1836 ms | 9332 KB | Output is correct |
20 | Correct | 1554 ms | 8304 KB | Output is correct |
21 | Correct | 1519 ms | 8300 KB | Output is correct |
22 | Correct | 1748 ms | 9092 KB | Output is correct |
23 | Correct | 1662 ms | 7508 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1363 ms | 4120 KB | Output is correct |
2 | Correct | 1360 ms | 4316 KB | Output is correct |
3 | Correct | 1385 ms | 4216 KB | Output is correct |
4 | Correct | 1413 ms | 4172 KB | Output is correct |
5 | Correct | 1386 ms | 4312 KB | Output is correct |
6 | Correct | 1828 ms | 4336 KB | Output is correct |
7 | Correct | 1827 ms | 4468 KB | Output is correct |
8 | Correct | 1857 ms | 4464 KB | Output is correct |
9 | Correct | 99 ms | 2692 KB | Output is correct |
10 | Correct | 1193 ms | 4352 KB | Output is correct |
11 | Correct | 1230 ms | 4336 KB | Output is correct |
12 | Correct | 1272 ms | 4592 KB | Output is correct |
13 | Correct | 1219 ms | 4204 KB | Output is correct |
14 | Correct | 1054 ms | 3576 KB | Output is correct |
15 | Correct | 666 ms | 3020 KB | Output is correct |
16 | Correct | 1136 ms | 3828 KB | Output is correct |
17 | Correct | 1020 ms | 3828 KB | Output is correct |
18 | Correct | 92 ms | 2680 KB | Output is correct |
19 | Correct | 1101 ms | 3852 KB | Output is correct |
20 | Correct | 955 ms | 3700 KB | Output is correct |
21 | Correct | 902 ms | 3704 KB | Output is correct |
22 | Correct | 771 ms | 4084 KB | Output is correct |
23 | Correct | 708 ms | 4084 KB | Output is correct |
24 | Correct | 730 ms | 3572 KB | Output is correct |
25 | Correct | 684 ms | 3572 KB | Output is correct |
26 | Correct | 1358 ms | 4372 KB | Output is correct |
27 | Correct | 1623 ms | 4336 KB | Output is correct |
28 | Correct | 1468 ms | 4332 KB | Output is correct |
29 | Correct | 1222 ms | 4508 KB | Output is correct |
30 | Correct | 1613 ms | 4464 KB | Output is correct |
31 | Correct | 1676 ms | 4460 KB | Output is correct |
32 | Correct | 1669 ms | 4464 KB | Output is correct |
33 | Correct | 1475 ms | 4372 KB | Output is correct |
34 | Correct | 1457 ms | 4336 KB | Output is correct |
35 | Correct | 1465 ms | 4100 KB | Output is correct |
36 | Correct | 1226 ms | 4292 KB | Output is correct |
37 | Correct | 1217 ms | 4336 KB | Output is correct |
38 | Correct | 1230 ms | 4208 KB | Output is correct |
39 | Correct | 1052 ms | 4464 KB | Output is correct |
40 | Correct | 1038 ms | 4460 KB | Output is correct |
41 | Correct | 1045 ms | 4208 KB | Output is correct |
42 | Correct | 1000 ms | 4080 KB | Output is correct |
43 | Correct | 986 ms | 4208 KB | Output is correct |
44 | Correct | 981 ms | 4208 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 768 KB | Output is correct |
2 | Correct | 5 ms | 768 KB | Output is correct |
3 | Correct | 35 ms | 1024 KB | Output is correct |
4 | Correct | 14 ms | 1024 KB | Output is correct |
5 | Correct | 28 ms | 1024 KB | Output is correct |
6 | Correct | 24 ms | 1024 KB | Output is correct |
7 | Correct | 24 ms | 1024 KB | Output is correct |
8 | Correct | 26 ms | 1160 KB | Output is correct |
9 | Correct | 23 ms | 1024 KB | Output is correct |
10 | Correct | 25 ms | 1024 KB | Output is correct |
11 | Correct | 26 ms | 1024 KB | Output is correct |
12 | Correct | 26 ms | 1024 KB | Output is correct |
13 | Correct | 32 ms | 1024 KB | Output is correct |
14 | Correct | 31 ms | 1024 KB | Output is correct |
15 | Correct | 28 ms | 1024 KB | Output is correct |
16 | Correct | 24 ms | 1024 KB | Output is correct |
17 | Correct | 24 ms | 1024 KB | Output is correct |
18 | Correct | 1363 ms | 4120 KB | Output is correct |
19 | Correct | 1360 ms | 4316 KB | Output is correct |
20 | Correct | 1385 ms | 4216 KB | Output is correct |
21 | Correct | 1413 ms | 4172 KB | Output is correct |
22 | Correct | 1386 ms | 4312 KB | Output is correct |
23 | Correct | 1828 ms | 4336 KB | Output is correct |
24 | Correct | 1827 ms | 4468 KB | Output is correct |
25 | Correct | 1857 ms | 4464 KB | Output is correct |
26 | Correct | 99 ms | 2692 KB | Output is correct |
27 | Correct | 1193 ms | 4352 KB | Output is correct |
28 | Correct | 1230 ms | 4336 KB | Output is correct |
29 | Correct | 1272 ms | 4592 KB | Output is correct |
30 | Correct | 1219 ms | 4204 KB | Output is correct |
31 | Correct | 1054 ms | 3576 KB | Output is correct |
32 | Correct | 666 ms | 3020 KB | Output is correct |
33 | Correct | 1136 ms | 3828 KB | Output is correct |
34 | Correct | 1020 ms | 3828 KB | Output is correct |
35 | Correct | 92 ms | 2680 KB | Output is correct |
36 | Correct | 1101 ms | 3852 KB | Output is correct |
37 | Correct | 955 ms | 3700 KB | Output is correct |
38 | Correct | 902 ms | 3704 KB | Output is correct |
39 | Correct | 771 ms | 4084 KB | Output is correct |
40 | Correct | 708 ms | 4084 KB | Output is correct |
41 | Correct | 730 ms | 3572 KB | Output is correct |
42 | Correct | 684 ms | 3572 KB | Output is correct |
43 | Correct | 1906 ms | 5444 KB | Output is correct |
44 | Correct | 105 ms | 3960 KB | Output is correct |
45 | Correct | 201 ms | 5232 KB | Output is correct |
46 | Correct | 133 ms | 5232 KB | Output is correct |
47 | Correct | 1696 ms | 7916 KB | Output is correct |
48 | Correct | 1770 ms | 9292 KB | Output is correct |
49 | Correct | 1746 ms | 7788 KB | Output is correct |
50 | Correct | 932 ms | 7000 KB | Output is correct |
51 | Correct | 906 ms | 7044 KB | Output is correct |
52 | Correct | 922 ms | 6896 KB | Output is correct |
53 | Correct | 1368 ms | 7948 KB | Output is correct |
54 | Correct | 1366 ms | 8168 KB | Output is correct |
55 | Correct | 1394 ms | 8040 KB | Output is correct |
56 | Correct | 1481 ms | 8228 KB | Output is correct |
57 | Correct | 1629 ms | 7788 KB | Output is correct |
58 | Correct | 1799 ms | 9196 KB | Output is correct |
59 | Correct | 1854 ms | 9108 KB | Output is correct |
60 | Correct | 1844 ms | 9224 KB | Output is correct |
61 | Correct | 1836 ms | 9332 KB | Output is correct |
62 | Correct | 1554 ms | 8304 KB | Output is correct |
63 | Correct | 1519 ms | 8300 KB | Output is correct |
64 | Correct | 1748 ms | 9092 KB | Output is correct |
65 | Correct | 1662 ms | 7508 KB | Output is correct |
66 | Correct | 1358 ms | 4372 KB | Output is correct |
67 | Correct | 1623 ms | 4336 KB | Output is correct |
68 | Correct | 1468 ms | 4332 KB | Output is correct |
69 | Correct | 1222 ms | 4508 KB | Output is correct |
70 | Correct | 1613 ms | 4464 KB | Output is correct |
71 | Correct | 1676 ms | 4460 KB | Output is correct |
72 | Correct | 1669 ms | 4464 KB | Output is correct |
73 | Correct | 1475 ms | 4372 KB | Output is correct |
74 | Correct | 1457 ms | 4336 KB | Output is correct |
75 | Correct | 1465 ms | 4100 KB | Output is correct |
76 | Correct | 1226 ms | 4292 KB | Output is correct |
77 | Correct | 1217 ms | 4336 KB | Output is correct |
78 | Correct | 1230 ms | 4208 KB | Output is correct |
79 | Correct | 1052 ms | 4464 KB | Output is correct |
80 | Correct | 1038 ms | 4460 KB | Output is correct |
81 | Correct | 1045 ms | 4208 KB | Output is correct |
82 | Correct | 1000 ms | 4080 KB | Output is correct |
83 | Correct | 986 ms | 4208 KB | Output is correct |
84 | Correct | 981 ms | 4208 KB | Output is correct |
85 | Correct | 2244 ms | 8948 KB | Output is correct |
86 | Correct | 238 ms | 5104 KB | Output is correct |
87 | Correct | 148 ms | 5232 KB | Output is correct |
88 | Correct | 2066 ms | 7564 KB | Output is correct |
89 | Correct | 2212 ms | 9120 KB | Output is correct |
90 | Correct | 2066 ms | 7660 KB | Output is correct |
91 | Correct | 1530 ms | 6896 KB | Output is correct |
92 | Correct | 1543 ms | 6976 KB | Output is correct |
93 | Correct | 1974 ms | 6996 KB | Output is correct |
94 | Correct | 1902 ms | 7892 KB | Output is correct |
95 | Correct | 1874 ms | 7996 KB | Output is correct |
96 | Correct | 2001 ms | 7920 KB | Output is correct |
97 | Correct | 1849 ms | 7912 KB | Output is correct |
98 | Correct | 1898 ms | 7272 KB | Output is correct |
99 | Correct | 2355 ms | 8924 KB | Output is correct |
100 | Correct | 2239 ms | 9068 KB | Output is correct |
101 | Correct | 2300 ms | 9024 KB | Output is correct |
102 | Correct | 2278 ms | 9140 KB | Output is correct |
103 | Correct | 2173 ms | 8212 KB | Output is correct |
104 | Correct | 2193 ms | 8564 KB | Output is correct |
105 | Correct | 1747 ms | 7936 KB | Output is correct |
106 | Correct | 1514 ms | 7912 KB | Output is correct |
107 | Correct | 1748 ms | 8684 KB | Output is correct |
108 | Correct | 2191 ms | 8936 KB | Output is correct |
109 | Correct | 2012 ms | 6944 KB | Output is correct |