# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
257771 |
2020-08-04T18:49:34 Z |
4fecta |
Bridges (APIO19_bridges) |
C++14 |
|
3000 ms |
12784 KB |
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
#define ll long long
#define ld long double
#define pii pair<int, int>
#define f first
#define s second
#define readl(_s) getline(cin, (_s));
#define boost() cin.tie(0); cin.sync_with_stdio(0)
struct edge {
int u = 0, v = 0, w = 0, i = 0, t = 0;
};
struct query {
int t = 0, u = 0, v = 0, i = 0;
};
bool cmp(edge x, edge y) {
return x.w > y.w;
}
bool cmq(query x, query y) {
return x.u > y.u;
}
const int MN = 50005, MM = 100005, SQRT = 900;
int n, m, q, par[MN], sz[MN], unst[MM], ans[MM];
edge e[MM], E[MM];
query Q[MM];
stack<pair<pii, int>> s;
int find(int x) {
return x == par[x] ? x : find(par[x]);
}
inline bool merge(int x, int y) {
x = find(x), y = find(y);
if (x == y) {s.push({{x, y}, 0}); return false;}
if (sz[x] > sz[y]) {
par[y] = par[x];
sz[x] += sz[y];
s.push({{x, y}, 1});
} else {
par[x] = par[y];
sz[y] += sz[x];
s.push({{y, x}, 1});
}
return true;
}
inline void undo() {
auto p = s.top(); s.pop();
if (!p.s) return;
par[p.f.s] = p.f.s;
sz[p.f.f] -= sz[p.f.s];
}
int main() {
boost();
cin >> n >> m;
for (int i = 1; i <= m; i++) {
cin >> e[i].u >> e[i].v >> e[i].w; e[i].i = i;
E[i] = e[i];
}
cin >> q;
for (int i = 1; i <= q; i++) {
cin >> Q[i].t >> Q[i].u >> Q[i].v; Q[i].i = i;
if (Q[i].t == 2) swap(Q[i].u, Q[i].v);
}
for (int I = 1; I <= q; I += SQRT) {
int lft = I, rit = min(q, I + SQRT - 1); //range of currently processed block
for (int i = 1; i <= m; i++) e[i] = E[i], unst[i] = 0;
sort(e + 1, e + m + 1, cmp);
vector<query> qs;
deque<edge> edges;
for (int i = 1; i <= n; i++) par[i] = i, sz[i] = 1;
while (s.size()) s.pop();
for (int i = lft; i <= rit; i++) {
if (Q[i].t == 1) {
unst[Q[i].u] = 1;
edges.push_front({E[Q[i].u].u, E[Q[i].u].v, Q[i].v, i, Q[i].u});
} else {
qs.push_back(Q[i]);
}
}
sort(qs.begin(), qs.end(), cmq);
int id = 1;
for (query cur : qs) {
while (id <= m && e[id].w >= cur.u) {
if (!unst[e[id].i]) merge(e[id].u, e[id].v);
id++;
}
int cnt = 0;
for (edge ed : edges) {
if (ed.i > cur.i || !unst[ed.t]) continue;
unst[ed.t] = 0;
if (ed.w >= cur.u) merge(ed.u, ed.v), cnt++;
}
for (edge ed : edges) {
int i = ed.t;
if (unst[i] && E[i].w >= cur.u) merge(E[i].u, E[i].v), cnt++;
}
ans[cur.i] = sz[find(cur.v)];
while (cnt--) undo();
for (edge ed : edges) unst[ed.t] = 1;
}
for (int i = lft; i <= rit; i++) {
if (Q[i].t == 1) E[Q[i].u].w = Q[i].v;
else printf("%d\n", ans[i]);
}
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
384 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Correct |
47 ms |
640 KB |
Output is correct |
4 |
Correct |
5 ms |
640 KB |
Output is correct |
5 |
Correct |
35 ms |
640 KB |
Output is correct |
6 |
Correct |
33 ms |
640 KB |
Output is correct |
7 |
Correct |
35 ms |
640 KB |
Output is correct |
8 |
Correct |
33 ms |
640 KB |
Output is correct |
9 |
Correct |
37 ms |
632 KB |
Output is correct |
10 |
Correct |
35 ms |
640 KB |
Output is correct |
11 |
Correct |
34 ms |
640 KB |
Output is correct |
12 |
Correct |
37 ms |
640 KB |
Output is correct |
13 |
Correct |
43 ms |
640 KB |
Output is correct |
14 |
Correct |
39 ms |
640 KB |
Output is correct |
15 |
Correct |
37 ms |
760 KB |
Output is correct |
16 |
Correct |
36 ms |
632 KB |
Output is correct |
17 |
Correct |
35 ms |
636 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1674 ms |
5592 KB |
Output is correct |
2 |
Correct |
1728 ms |
5752 KB |
Output is correct |
3 |
Correct |
1739 ms |
5748 KB |
Output is correct |
4 |
Correct |
1777 ms |
5624 KB |
Output is correct |
5 |
Correct |
1775 ms |
5624 KB |
Output is correct |
6 |
Correct |
2453 ms |
5948 KB |
Output is correct |
7 |
Correct |
2450 ms |
6008 KB |
Output is correct |
8 |
Correct |
2430 ms |
5880 KB |
Output is correct |
9 |
Correct |
44 ms |
2556 KB |
Output is correct |
10 |
Correct |
1384 ms |
5624 KB |
Output is correct |
11 |
Correct |
1335 ms |
5748 KB |
Output is correct |
12 |
Correct |
1647 ms |
5988 KB |
Output is correct |
13 |
Correct |
1598 ms |
5548 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1313 ms |
4856 KB |
Output is correct |
2 |
Correct |
912 ms |
3192 KB |
Output is correct |
3 |
Correct |
1499 ms |
4856 KB |
Output is correct |
4 |
Correct |
1304 ms |
4532 KB |
Output is correct |
5 |
Correct |
40 ms |
2552 KB |
Output is correct |
6 |
Correct |
1413 ms |
4740 KB |
Output is correct |
7 |
Correct |
1226 ms |
4600 KB |
Output is correct |
8 |
Correct |
1149 ms |
4628 KB |
Output is correct |
9 |
Correct |
930 ms |
4856 KB |
Output is correct |
10 |
Correct |
897 ms |
4600 KB |
Output is correct |
11 |
Correct |
998 ms |
4500 KB |
Output is correct |
12 |
Correct |
903 ms |
4472 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2468 ms |
8736 KB |
Output is correct |
2 |
Correct |
43 ms |
3960 KB |
Output is correct |
3 |
Correct |
271 ms |
8056 KB |
Output is correct |
4 |
Correct |
149 ms |
8056 KB |
Output is correct |
5 |
Correct |
1371 ms |
11000 KB |
Output is correct |
6 |
Correct |
2390 ms |
12784 KB |
Output is correct |
7 |
Correct |
1375 ms |
11148 KB |
Output is correct |
8 |
Correct |
1115 ms |
8496 KB |
Output is correct |
9 |
Correct |
1099 ms |
8440 KB |
Output is correct |
10 |
Correct |
1103 ms |
8440 KB |
Output is correct |
11 |
Correct |
1789 ms |
10564 KB |
Output is correct |
12 |
Correct |
1742 ms |
10616 KB |
Output is correct |
13 |
Correct |
1788 ms |
10632 KB |
Output is correct |
14 |
Correct |
1349 ms |
11320 KB |
Output is correct |
15 |
Correct |
1356 ms |
11132 KB |
Output is correct |
16 |
Correct |
2385 ms |
12428 KB |
Output is correct |
17 |
Correct |
2419 ms |
12584 KB |
Output is correct |
18 |
Correct |
2391 ms |
12660 KB |
Output is correct |
19 |
Correct |
2383 ms |
12784 KB |
Output is correct |
20 |
Correct |
2020 ms |
11188 KB |
Output is correct |
21 |
Correct |
1990 ms |
11168 KB |
Output is correct |
22 |
Correct |
2277 ms |
12152 KB |
Output is correct |
23 |
Correct |
1347 ms |
9884 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1674 ms |
5592 KB |
Output is correct |
2 |
Correct |
1728 ms |
5752 KB |
Output is correct |
3 |
Correct |
1739 ms |
5748 KB |
Output is correct |
4 |
Correct |
1777 ms |
5624 KB |
Output is correct |
5 |
Correct |
1775 ms |
5624 KB |
Output is correct |
6 |
Correct |
2453 ms |
5948 KB |
Output is correct |
7 |
Correct |
2450 ms |
6008 KB |
Output is correct |
8 |
Correct |
2430 ms |
5880 KB |
Output is correct |
9 |
Correct |
44 ms |
2556 KB |
Output is correct |
10 |
Correct |
1384 ms |
5624 KB |
Output is correct |
11 |
Correct |
1335 ms |
5748 KB |
Output is correct |
12 |
Correct |
1647 ms |
5988 KB |
Output is correct |
13 |
Correct |
1598 ms |
5548 KB |
Output is correct |
14 |
Correct |
1313 ms |
4856 KB |
Output is correct |
15 |
Correct |
912 ms |
3192 KB |
Output is correct |
16 |
Correct |
1499 ms |
4856 KB |
Output is correct |
17 |
Correct |
1304 ms |
4532 KB |
Output is correct |
18 |
Correct |
40 ms |
2552 KB |
Output is correct |
19 |
Correct |
1413 ms |
4740 KB |
Output is correct |
20 |
Correct |
1226 ms |
4600 KB |
Output is correct |
21 |
Correct |
1149 ms |
4628 KB |
Output is correct |
22 |
Correct |
930 ms |
4856 KB |
Output is correct |
23 |
Correct |
897 ms |
4600 KB |
Output is correct |
24 |
Correct |
998 ms |
4500 KB |
Output is correct |
25 |
Correct |
903 ms |
4472 KB |
Output is correct |
26 |
Correct |
1761 ms |
5788 KB |
Output is correct |
27 |
Correct |
2032 ms |
5768 KB |
Output is correct |
28 |
Correct |
1771 ms |
5732 KB |
Output is correct |
29 |
Correct |
1460 ms |
5604 KB |
Output is correct |
30 |
Correct |
1974 ms |
5624 KB |
Output is correct |
31 |
Correct |
1987 ms |
5880 KB |
Output is correct |
32 |
Correct |
2004 ms |
5868 KB |
Output is correct |
33 |
Correct |
1725 ms |
5880 KB |
Output is correct |
34 |
Correct |
1737 ms |
5768 KB |
Output is correct |
35 |
Correct |
1720 ms |
5656 KB |
Output is correct |
36 |
Correct |
1486 ms |
5636 KB |
Output is correct |
37 |
Correct |
1480 ms |
5752 KB |
Output is correct |
38 |
Correct |
1464 ms |
5760 KB |
Output is correct |
39 |
Correct |
1253 ms |
5816 KB |
Output is correct |
40 |
Correct |
1232 ms |
5720 KB |
Output is correct |
41 |
Correct |
1244 ms |
5624 KB |
Output is correct |
42 |
Correct |
1252 ms |
5496 KB |
Output is correct |
43 |
Correct |
1233 ms |
5752 KB |
Output is correct |
44 |
Correct |
1222 ms |
5624 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
384 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Correct |
47 ms |
640 KB |
Output is correct |
4 |
Correct |
5 ms |
640 KB |
Output is correct |
5 |
Correct |
35 ms |
640 KB |
Output is correct |
6 |
Correct |
33 ms |
640 KB |
Output is correct |
7 |
Correct |
35 ms |
640 KB |
Output is correct |
8 |
Correct |
33 ms |
640 KB |
Output is correct |
9 |
Correct |
37 ms |
632 KB |
Output is correct |
10 |
Correct |
35 ms |
640 KB |
Output is correct |
11 |
Correct |
34 ms |
640 KB |
Output is correct |
12 |
Correct |
37 ms |
640 KB |
Output is correct |
13 |
Correct |
43 ms |
640 KB |
Output is correct |
14 |
Correct |
39 ms |
640 KB |
Output is correct |
15 |
Correct |
37 ms |
760 KB |
Output is correct |
16 |
Correct |
36 ms |
632 KB |
Output is correct |
17 |
Correct |
35 ms |
636 KB |
Output is correct |
18 |
Correct |
1674 ms |
5592 KB |
Output is correct |
19 |
Correct |
1728 ms |
5752 KB |
Output is correct |
20 |
Correct |
1739 ms |
5748 KB |
Output is correct |
21 |
Correct |
1777 ms |
5624 KB |
Output is correct |
22 |
Correct |
1775 ms |
5624 KB |
Output is correct |
23 |
Correct |
2453 ms |
5948 KB |
Output is correct |
24 |
Correct |
2450 ms |
6008 KB |
Output is correct |
25 |
Correct |
2430 ms |
5880 KB |
Output is correct |
26 |
Correct |
44 ms |
2556 KB |
Output is correct |
27 |
Correct |
1384 ms |
5624 KB |
Output is correct |
28 |
Correct |
1335 ms |
5748 KB |
Output is correct |
29 |
Correct |
1647 ms |
5988 KB |
Output is correct |
30 |
Correct |
1598 ms |
5548 KB |
Output is correct |
31 |
Correct |
1313 ms |
4856 KB |
Output is correct |
32 |
Correct |
912 ms |
3192 KB |
Output is correct |
33 |
Correct |
1499 ms |
4856 KB |
Output is correct |
34 |
Correct |
1304 ms |
4532 KB |
Output is correct |
35 |
Correct |
40 ms |
2552 KB |
Output is correct |
36 |
Correct |
1413 ms |
4740 KB |
Output is correct |
37 |
Correct |
1226 ms |
4600 KB |
Output is correct |
38 |
Correct |
1149 ms |
4628 KB |
Output is correct |
39 |
Correct |
930 ms |
4856 KB |
Output is correct |
40 |
Correct |
897 ms |
4600 KB |
Output is correct |
41 |
Correct |
998 ms |
4500 KB |
Output is correct |
42 |
Correct |
903 ms |
4472 KB |
Output is correct |
43 |
Correct |
2468 ms |
8736 KB |
Output is correct |
44 |
Correct |
43 ms |
3960 KB |
Output is correct |
45 |
Correct |
271 ms |
8056 KB |
Output is correct |
46 |
Correct |
149 ms |
8056 KB |
Output is correct |
47 |
Correct |
1371 ms |
11000 KB |
Output is correct |
48 |
Correct |
2390 ms |
12784 KB |
Output is correct |
49 |
Correct |
1375 ms |
11148 KB |
Output is correct |
50 |
Correct |
1115 ms |
8496 KB |
Output is correct |
51 |
Correct |
1099 ms |
8440 KB |
Output is correct |
52 |
Correct |
1103 ms |
8440 KB |
Output is correct |
53 |
Correct |
1789 ms |
10564 KB |
Output is correct |
54 |
Correct |
1742 ms |
10616 KB |
Output is correct |
55 |
Correct |
1788 ms |
10632 KB |
Output is correct |
56 |
Correct |
1349 ms |
11320 KB |
Output is correct |
57 |
Correct |
1356 ms |
11132 KB |
Output is correct |
58 |
Correct |
2385 ms |
12428 KB |
Output is correct |
59 |
Correct |
2419 ms |
12584 KB |
Output is correct |
60 |
Correct |
2391 ms |
12660 KB |
Output is correct |
61 |
Correct |
2383 ms |
12784 KB |
Output is correct |
62 |
Correct |
2020 ms |
11188 KB |
Output is correct |
63 |
Correct |
1990 ms |
11168 KB |
Output is correct |
64 |
Correct |
2277 ms |
12152 KB |
Output is correct |
65 |
Correct |
1347 ms |
9884 KB |
Output is correct |
66 |
Correct |
1761 ms |
5788 KB |
Output is correct |
67 |
Correct |
2032 ms |
5768 KB |
Output is correct |
68 |
Correct |
1771 ms |
5732 KB |
Output is correct |
69 |
Correct |
1460 ms |
5604 KB |
Output is correct |
70 |
Correct |
1974 ms |
5624 KB |
Output is correct |
71 |
Correct |
1987 ms |
5880 KB |
Output is correct |
72 |
Correct |
2004 ms |
5868 KB |
Output is correct |
73 |
Correct |
1725 ms |
5880 KB |
Output is correct |
74 |
Correct |
1737 ms |
5768 KB |
Output is correct |
75 |
Correct |
1720 ms |
5656 KB |
Output is correct |
76 |
Correct |
1486 ms |
5636 KB |
Output is correct |
77 |
Correct |
1480 ms |
5752 KB |
Output is correct |
78 |
Correct |
1464 ms |
5760 KB |
Output is correct |
79 |
Correct |
1253 ms |
5816 KB |
Output is correct |
80 |
Correct |
1232 ms |
5720 KB |
Output is correct |
81 |
Correct |
1244 ms |
5624 KB |
Output is correct |
82 |
Correct |
1252 ms |
5496 KB |
Output is correct |
83 |
Correct |
1233 ms |
5752 KB |
Output is correct |
84 |
Correct |
1222 ms |
5624 KB |
Output is correct |
85 |
Correct |
2993 ms |
12516 KB |
Output is correct |
86 |
Correct |
311 ms |
7928 KB |
Output is correct |
87 |
Correct |
211 ms |
8092 KB |
Output is correct |
88 |
Correct |
1990 ms |
11000 KB |
Output is correct |
89 |
Correct |
2994 ms |
12680 KB |
Output is correct |
90 |
Correct |
2001 ms |
10968 KB |
Output is correct |
91 |
Correct |
1767 ms |
8568 KB |
Output is correct |
92 |
Correct |
1771 ms |
8364 KB |
Output is correct |
93 |
Correct |
2361 ms |
8540 KB |
Output is correct |
94 |
Correct |
2450 ms |
10396 KB |
Output is correct |
95 |
Correct |
2374 ms |
10620 KB |
Output is correct |
96 |
Correct |
2812 ms |
10468 KB |
Output is correct |
97 |
Correct |
1558 ms |
11176 KB |
Output is correct |
98 |
Correct |
1624 ms |
10580 KB |
Output is correct |
99 |
Execution timed out |
3034 ms |
12332 KB |
Time limit exceeded |
100 |
Halted |
0 ms |
0 KB |
- |