# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
187346 | 2020-01-12T19:35:17 Z | MiricaMatei | Bridges (APIO19_bridges) | C++14 | 2904 ms | 10216 KB |
#include <bits/stdc++.h> using namespace std; const int MAXN = 50005; const int MAXM = 100005; const int MAXQ = 100005; const int INF = 1000000000; struct Edge { int u, v, c; bool operator < (const Edge& other) const { return c > other.c; } }e[MAXM], sg[MAXM]; struct Query { int t, a, b, ind; bool operator < (const Query& other) const { return b > other.b; } } qr[MAXQ], bk[MAXQ]; struct DSU { int n; int t[MAXN], h[MAXN], sz[MAXN]; int top = 0; int stkx[MAXN], stky[MAXN]; void init(int _n) { n = _n; for (int i = 1; i <= n; ++i) t[i] = i, h[i] = 1, sz[i] = 1; top = 0; } int f(int x) { if (t[x] == x) return x; return f(t[x]); } int u(int x, int y) { x = f(x); y = f(y); if (x == y) return 0; if (h[y] > h[x]) swap(x, y); t[y] = x; sz[x] += sz[y]; if (h[x] == h[y]) h[x]++; top++; stkx[top] = x; stky[top] = y; return 1; } void undo() { int x = stkx[top]; int y = stky[top]; top--; if (h[x] == h[y] + 1) h[x]--; t[y] = y; sz[x] -= sz[y]; } int query(int x) { return sz[f(x)]; } }dsu; bool vis[MAXM]; bool vis1[MAXM]; int ans[MAXM]; int main() { int n, m, q; scanf("%d%d", &n, &m); for (int i = 1; i <= m; ++i) scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].c); scanf("%d", &q); for (int i = 1; i <= q; ++i) { scanf("%d%d%d", &qr[i].t, &qr[i].a, &qr[i].b); qr[i].ind = i; } int BUCK_SIZE = 700; for (int b = 1; (b - 1) * BUCK_SIZE + 1 <= q; ++b) { dsu.init(n); for (int i = 1; i <= m; ++i) vis[i] = 0; int l = (b - 1) * BUCK_SIZE + 1; int r = min(q, l + BUCK_SIZE - 1); int s = 0; for (int i = l; i <= r; ++i) { if (qr[i].t == 1) vis[qr[i].a] = 1; bk[++s] = qr[i]; } int k = 0; for (int i = 1; i <= m; ++i) if (!vis[i]) sg[++k] = e[i]; sort(sg + 1, sg + k + 1); sort(bk + 1, bk + s + 1); for (int i = 1, j = 1; j <= s;) { while (j <= s && bk[j].t == 1) j++; if (j > s) continue; if (i <= k && (j > s || sg[i].c >= bk[j].b)) { dsu.u(sg[i].u, sg[i].v); i++; } else { int undoCount = 0; for (int p = bk[j].ind - 1; p >= l; --p) if (qr[p].t == 1 && !vis1[qr[p].a]) { vis1[qr[p].a] = 1; if (qr[p].b >= bk[j].b) undoCount += dsu.u(e[qr[p].a].u, e[qr[p].a].v); } for (int p = bk[j].ind + 1; p <= r; ++p) if (qr[p].t == 1 && !vis1[qr[p].a]) { vis1[qr[p].a] = 1; if (e[qr[p].a].c >= bk[j].b) undoCount += dsu.u(e[qr[p].a].u, e[qr[p].a].v); } ans[bk[j].ind] = dsu.query(bk[j].a); for (int p = l; p <= r; ++p) if (qr[p].t == 1) vis1[qr[p].a] = 0; while (undoCount--) dsu.undo(); j++; } } for (int i = l; i <= r; ++i) if (qr[i].t == 1) e[qr[i].a].c = qr[i].b; } for (int i = 1; i <= q; ++i) if (ans[i]) printf("%d\n", ans[i]); return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | Output is correct |
2 | Correct | 2 ms | 376 KB | Output is correct |
3 | Correct | 74 ms | 760 KB | Output is correct |
4 | Correct | 17 ms | 760 KB | Output is correct |
5 | Correct | 51 ms | 764 KB | Output is correct |
6 | Correct | 46 ms | 760 KB | Output is correct |
7 | Correct | 48 ms | 632 KB | Output is correct |
8 | Correct | 48 ms | 760 KB | Output is correct |
9 | Correct | 44 ms | 632 KB | Output is correct |
10 | Correct | 49 ms | 764 KB | Output is correct |
11 | Correct | 48 ms | 888 KB | Output is correct |
12 | Correct | 50 ms | 888 KB | Output is correct |
13 | Correct | 56 ms | 760 KB | Output is correct |
14 | Correct | 54 ms | 760 KB | Output is correct |
15 | Correct | 53 ms | 760 KB | Output is correct |
16 | Correct | 46 ms | 752 KB | Output is correct |
17 | Correct | 47 ms | 760 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1785 ms | 7480 KB | Output is correct |
2 | Correct | 1830 ms | 7512 KB | Output is correct |
3 | Correct | 1845 ms | 7524 KB | Output is correct |
4 | Correct | 1961 ms | 7732 KB | Output is correct |
5 | Correct | 1991 ms | 7620 KB | Output is correct |
6 | Correct | 2625 ms | 7384 KB | Output is correct |
7 | Correct | 2604 ms | 7536 KB | Output is correct |
8 | Correct | 2631 ms | 7544 KB | Output is correct |
9 | Correct | 155 ms | 3844 KB | Output is correct |
10 | Correct | 1461 ms | 6592 KB | Output is correct |
11 | Correct | 1373 ms | 6492 KB | Output is correct |
12 | Correct | 1536 ms | 7576 KB | Output is correct |
13 | Correct | 1642 ms | 7332 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1452 ms | 6412 KB | Output is correct |
2 | Correct | 1517 ms | 4728 KB | Output is correct |
3 | Correct | 2193 ms | 6380 KB | Output is correct |
4 | Correct | 2245 ms | 6352 KB | Output is correct |
5 | Correct | 159 ms | 3960 KB | Output is correct |
6 | Correct | 1842 ms | 6412 KB | Output is correct |
7 | Correct | 1529 ms | 6324 KB | Output is correct |
8 | Correct | 1307 ms | 6360 KB | Output is correct |
9 | Correct | 1031 ms | 6452 KB | Output is correct |
10 | Correct | 924 ms | 6496 KB | Output is correct |
11 | Correct | 1004 ms | 6392 KB | Output is correct |
12 | Correct | 879 ms | 6136 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2225 ms | 10216 KB | Output is correct |
2 | Correct | 160 ms | 3832 KB | Output is correct |
3 | Correct | 243 ms | 5060 KB | Output is correct |
4 | Correct | 129 ms | 4984 KB | Output is correct |
5 | Correct | 1380 ms | 8608 KB | Output is correct |
6 | Correct | 2176 ms | 8864 KB | Output is correct |
7 | Correct | 1342 ms | 8672 KB | Output is correct |
8 | Correct | 1176 ms | 7260 KB | Output is correct |
9 | Correct | 1179 ms | 7180 KB | Output is correct |
10 | Correct | 1176 ms | 7556 KB | Output is correct |
11 | Correct | 1740 ms | 7948 KB | Output is correct |
12 | Correct | 1715 ms | 7848 KB | Output is correct |
13 | Correct | 1768 ms | 7940 KB | Output is correct |
14 | Correct | 1302 ms | 8776 KB | Output is correct |
15 | Correct | 1354 ms | 8796 KB | Output is correct |
16 | Correct | 2235 ms | 8740 KB | Output is correct |
17 | Correct | 2255 ms | 8572 KB | Output is correct |
18 | Correct | 2235 ms | 8612 KB | Output is correct |
19 | Correct | 2237 ms | 8568 KB | Output is correct |
20 | Correct | 1926 ms | 8392 KB | Output is correct |
21 | Correct | 1957 ms | 8348 KB | Output is correct |
22 | Correct | 2137 ms | 8636 KB | Output is correct |
23 | Correct | 1363 ms | 7888 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1785 ms | 7480 KB | Output is correct |
2 | Correct | 1830 ms | 7512 KB | Output is correct |
3 | Correct | 1845 ms | 7524 KB | Output is correct |
4 | Correct | 1961 ms | 7732 KB | Output is correct |
5 | Correct | 1991 ms | 7620 KB | Output is correct |
6 | Correct | 2625 ms | 7384 KB | Output is correct |
7 | Correct | 2604 ms | 7536 KB | Output is correct |
8 | Correct | 2631 ms | 7544 KB | Output is correct |
9 | Correct | 155 ms | 3844 KB | Output is correct |
10 | Correct | 1461 ms | 6592 KB | Output is correct |
11 | Correct | 1373 ms | 6492 KB | Output is correct |
12 | Correct | 1536 ms | 7576 KB | Output is correct |
13 | Correct | 1642 ms | 7332 KB | Output is correct |
14 | Correct | 1452 ms | 6412 KB | Output is correct |
15 | Correct | 1517 ms | 4728 KB | Output is correct |
16 | Correct | 2193 ms | 6380 KB | Output is correct |
17 | Correct | 2245 ms | 6352 KB | Output is correct |
18 | Correct | 159 ms | 3960 KB | Output is correct |
19 | Correct | 1842 ms | 6412 KB | Output is correct |
20 | Correct | 1529 ms | 6324 KB | Output is correct |
21 | Correct | 1307 ms | 6360 KB | Output is correct |
22 | Correct | 1031 ms | 6452 KB | Output is correct |
23 | Correct | 924 ms | 6496 KB | Output is correct |
24 | Correct | 1004 ms | 6392 KB | Output is correct |
25 | Correct | 879 ms | 6136 KB | Output is correct |
26 | Correct | 1891 ms | 7688 KB | Output is correct |
27 | Correct | 2501 ms | 7356 KB | Output is correct |
28 | Correct | 2172 ms | 7336 KB | Output is correct |
29 | Correct | 1681 ms | 7616 KB | Output is correct |
30 | Correct | 2384 ms | 7124 KB | Output is correct |
31 | Correct | 2474 ms | 7268 KB | Output is correct |
32 | Correct | 2451 ms | 7192 KB | Output is correct |
33 | Correct | 2045 ms | 7664 KB | Output is correct |
34 | Correct | 2072 ms | 7504 KB | Output is correct |
35 | Correct | 2099 ms | 7544 KB | Output is correct |
36 | Correct | 1671 ms | 7544 KB | Output is correct |
37 | Correct | 1686 ms | 7436 KB | Output is correct |
38 | Correct | 1674 ms | 7508 KB | Output is correct |
39 | Correct | 1345 ms | 7672 KB | Output is correct |
40 | Correct | 1347 ms | 7672 KB | Output is correct |
41 | Correct | 1350 ms | 7576 KB | Output is correct |
42 | Correct | 1187 ms | 7520 KB | Output is correct |
43 | Correct | 1207 ms | 7400 KB | Output is correct |
44 | Correct | 1190 ms | 7364 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | Output is correct |
2 | Correct | 2 ms | 376 KB | Output is correct |
3 | Correct | 74 ms | 760 KB | Output is correct |
4 | Correct | 17 ms | 760 KB | Output is correct |
5 | Correct | 51 ms | 764 KB | Output is correct |
6 | Correct | 46 ms | 760 KB | Output is correct |
7 | Correct | 48 ms | 632 KB | Output is correct |
8 | Correct | 48 ms | 760 KB | Output is correct |
9 | Correct | 44 ms | 632 KB | Output is correct |
10 | Correct | 49 ms | 764 KB | Output is correct |
11 | Correct | 48 ms | 888 KB | Output is correct |
12 | Correct | 50 ms | 888 KB | Output is correct |
13 | Correct | 56 ms | 760 KB | Output is correct |
14 | Correct | 54 ms | 760 KB | Output is correct |
15 | Correct | 53 ms | 760 KB | Output is correct |
16 | Correct | 46 ms | 752 KB | Output is correct |
17 | Correct | 47 ms | 760 KB | Output is correct |
18 | Correct | 1785 ms | 7480 KB | Output is correct |
19 | Correct | 1830 ms | 7512 KB | Output is correct |
20 | Correct | 1845 ms | 7524 KB | Output is correct |
21 | Correct | 1961 ms | 7732 KB | Output is correct |
22 | Correct | 1991 ms | 7620 KB | Output is correct |
23 | Correct | 2625 ms | 7384 KB | Output is correct |
24 | Correct | 2604 ms | 7536 KB | Output is correct |
25 | Correct | 2631 ms | 7544 KB | Output is correct |
26 | Correct | 155 ms | 3844 KB | Output is correct |
27 | Correct | 1461 ms | 6592 KB | Output is correct |
28 | Correct | 1373 ms | 6492 KB | Output is correct |
29 | Correct | 1536 ms | 7576 KB | Output is correct |
30 | Correct | 1642 ms | 7332 KB | Output is correct |
31 | Correct | 1452 ms | 6412 KB | Output is correct |
32 | Correct | 1517 ms | 4728 KB | Output is correct |
33 | Correct | 2193 ms | 6380 KB | Output is correct |
34 | Correct | 2245 ms | 6352 KB | Output is correct |
35 | Correct | 159 ms | 3960 KB | Output is correct |
36 | Correct | 1842 ms | 6412 KB | Output is correct |
37 | Correct | 1529 ms | 6324 KB | Output is correct |
38 | Correct | 1307 ms | 6360 KB | Output is correct |
39 | Correct | 1031 ms | 6452 KB | Output is correct |
40 | Correct | 924 ms | 6496 KB | Output is correct |
41 | Correct | 1004 ms | 6392 KB | Output is correct |
42 | Correct | 879 ms | 6136 KB | Output is correct |
43 | Correct | 2225 ms | 10216 KB | Output is correct |
44 | Correct | 160 ms | 3832 KB | Output is correct |
45 | Correct | 243 ms | 5060 KB | Output is correct |
46 | Correct | 129 ms | 4984 KB | Output is correct |
47 | Correct | 1380 ms | 8608 KB | Output is correct |
48 | Correct | 2176 ms | 8864 KB | Output is correct |
49 | Correct | 1342 ms | 8672 KB | Output is correct |
50 | Correct | 1176 ms | 7260 KB | Output is correct |
51 | Correct | 1179 ms | 7180 KB | Output is correct |
52 | Correct | 1176 ms | 7556 KB | Output is correct |
53 | Correct | 1740 ms | 7948 KB | Output is correct |
54 | Correct | 1715 ms | 7848 KB | Output is correct |
55 | Correct | 1768 ms | 7940 KB | Output is correct |
56 | Correct | 1302 ms | 8776 KB | Output is correct |
57 | Correct | 1354 ms | 8796 KB | Output is correct |
58 | Correct | 2235 ms | 8740 KB | Output is correct |
59 | Correct | 2255 ms | 8572 KB | Output is correct |
60 | Correct | 2235 ms | 8612 KB | Output is correct |
61 | Correct | 2237 ms | 8568 KB | Output is correct |
62 | Correct | 1926 ms | 8392 KB | Output is correct |
63 | Correct | 1957 ms | 8348 KB | Output is correct |
64 | Correct | 2137 ms | 8636 KB | Output is correct |
65 | Correct | 1363 ms | 7888 KB | Output is correct |
66 | Correct | 1891 ms | 7688 KB | Output is correct |
67 | Correct | 2501 ms | 7356 KB | Output is correct |
68 | Correct | 2172 ms | 7336 KB | Output is correct |
69 | Correct | 1681 ms | 7616 KB | Output is correct |
70 | Correct | 2384 ms | 7124 KB | Output is correct |
71 | Correct | 2474 ms | 7268 KB | Output is correct |
72 | Correct | 2451 ms | 7192 KB | Output is correct |
73 | Correct | 2045 ms | 7664 KB | Output is correct |
74 | Correct | 2072 ms | 7504 KB | Output is correct |
75 | Correct | 2099 ms | 7544 KB | Output is correct |
76 | Correct | 1671 ms | 7544 KB | Output is correct |
77 | Correct | 1686 ms | 7436 KB | Output is correct |
78 | Correct | 1674 ms | 7508 KB | Output is correct |
79 | Correct | 1345 ms | 7672 KB | Output is correct |
80 | Correct | 1347 ms | 7672 KB | Output is correct |
81 | Correct | 1350 ms | 7576 KB | Output is correct |
82 | Correct | 1187 ms | 7520 KB | Output is correct |
83 | Correct | 1207 ms | 7400 KB | Output is correct |
84 | Correct | 1190 ms | 7364 KB | Output is correct |
85 | Correct | 2775 ms | 9124 KB | Output is correct |
86 | Correct | 261 ms | 5112 KB | Output is correct |
87 | Correct | 154 ms | 5120 KB | Output is correct |
88 | Correct | 1754 ms | 8476 KB | Output is correct |
89 | Correct | 2767 ms | 9864 KB | Output is correct |
90 | Correct | 1766 ms | 8480 KB | Output is correct |
91 | Correct | 2104 ms | 7464 KB | Output is correct |
92 | Correct | 2097 ms | 7672 KB | Output is correct |
93 | Correct | 2730 ms | 7424 KB | Output is correct |
94 | Correct | 2463 ms | 8540 KB | Output is correct |
95 | Correct | 2447 ms | 8948 KB | Output is correct |
96 | Correct | 2372 ms | 8704 KB | Output is correct |
97 | Correct | 1506 ms | 8696 KB | Output is correct |
98 | Correct | 1418 ms | 8232 KB | Output is correct |
99 | Correct | 2892 ms | 9984 KB | Output is correct |
100 | Correct | 2821 ms | 9952 KB | Output is correct |
101 | Correct | 2904 ms | 9908 KB | Output is correct |
102 | Correct | 2904 ms | 10092 KB | Output is correct |
103 | Correct | 2478 ms | 9104 KB | Output is correct |
104 | Correct | 2472 ms | 9204 KB | Output is correct |
105 | Correct | 2045 ms | 8856 KB | Output is correct |
106 | Correct | 1766 ms | 8568 KB | Output is correct |
107 | Correct | 2101 ms | 9292 KB | Output is correct |
108 | Correct | 2619 ms | 9772 KB | Output is correct |
109 | Correct | 1770 ms | 7880 KB | Output is correct |