# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
260456 |
2020-08-10T10:00:58 Z |
islingr |
Bridges (APIO19_bridges) |
C++17 |
|
2550 ms |
11332 KB |
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (auto i = (a); i < (b); ++i)
#define eb(x...) emplace_back(x)
#define all(x) begin(x), end(x)
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) int((x).size())
const int N = 1 << 16, M = 1 << 17, Q = M, B = 1 << 10;
int nxt[N], sz[N];
int head(int u) { return nxt[u] < 0 ? u : nxt[u] = head(nxt[u]); }
void unite(int u, int v) {
u = head(u); v = head(v);
if (u == v) return;
if (sz[u] > sz[v]) swap(u, v);
nxt[u] = v; sz[v] += sz[u];
}
int u[M], v[M], w[M], ord[M];
short t[Q]; int b[Q], c[Q], ans[Q];
bool changed[M];
vector<int> changed_edges, changed_nodes, g[N];
vector<tuple<int, int, int>> queries;
vector<pair<int, int>> weights[M];
bool vis[N];
void dfs(int u) { vis[u] = 1; for (int v : g[u]) if (!vis[v]) dfs(v); }
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
rep(e, 0, m) cin >> u[e] >> v[e] >> w[e], --u[e], --v[e], ord[e] = e;
int q; cin >> q;
rep(i, 0, q) cin >> t[i] >> b[i] >> c[i], --b[i], --t[i];
for (int l = 0, r = 0; r = min(l + B, q), l < q; l += B) {
fill(nxt, nxt + n, -1); fill(sz, sz + n, 1);
fill(changed, changed + m, false); changed_edges.clear();
queries.clear();
sort(ord, ord + m, [&](int x, int y) { return w[x] > w[y]; });
rep(i, l, r)
if (t[i]) queries.eb(c[i], b[i], i);
else changed[b[i]] = true;
rep(e, 0, m) if (changed[e]) weights[e] = {{w[e], 0}}, changed_edges.eb(e);
rep(i, l, r) if (!t[i]) weights[b[i]].eb(c[i], i);
sort(rall(queries));
int e = 0;
for (auto &[z, s, t] : queries) {
while (e < m && z <= w[ord[e]]) { if (!changed[ord[e]]) unite(u[ord[e]], v[ord[e]]); ++e; }
for (auto e : changed_edges) {
int c = 0;
while (c < sz(weights[e]) && weights[e][c].second <= t) ++c;
if (z <= weights[e][--c].first) {
int x = head(u[e]), y = head(v[e]);
g[x].eb(y); g[y].eb(x);
changed_nodes.eb(x); changed_nodes.eb(y);
}
}
dfs(s = head(s)); vis[s] = 0; ans[t] = sz[s];
for (int x : changed_nodes) {
if (vis[x]) ans[t] += sz[x];
g[x].clear(), vis[x] = 0;
}
changed_nodes.clear();
}
rep(i, l, r) if (!t[i]) w[b[i]] = c[i];
}
rep(i, 0, q) if (t[i]) cout << ans[i] << '\n';
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
4992 KB |
Output is correct |
2 |
Correct |
5 ms |
4992 KB |
Output is correct |
3 |
Correct |
92 ms |
5248 KB |
Output is correct |
4 |
Correct |
8 ms |
5120 KB |
Output is correct |
5 |
Correct |
25 ms |
5248 KB |
Output is correct |
6 |
Correct |
24 ms |
5240 KB |
Output is correct |
7 |
Correct |
28 ms |
5248 KB |
Output is correct |
8 |
Correct |
25 ms |
5248 KB |
Output is correct |
9 |
Correct |
32 ms |
5240 KB |
Output is correct |
10 |
Correct |
25 ms |
5248 KB |
Output is correct |
11 |
Correct |
25 ms |
5240 KB |
Output is correct |
12 |
Correct |
27 ms |
5248 KB |
Output is correct |
13 |
Correct |
34 ms |
5240 KB |
Output is correct |
14 |
Correct |
33 ms |
5244 KB |
Output is correct |
15 |
Correct |
28 ms |
5248 KB |
Output is correct |
16 |
Correct |
49 ms |
5240 KB |
Output is correct |
17 |
Correct |
31 ms |
5240 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1893 ms |
10332 KB |
Output is correct |
2 |
Correct |
1700 ms |
10148 KB |
Output is correct |
3 |
Correct |
1738 ms |
10064 KB |
Output is correct |
4 |
Correct |
1694 ms |
10268 KB |
Output is correct |
5 |
Correct |
1703 ms |
10104 KB |
Output is correct |
6 |
Correct |
2517 ms |
9336 KB |
Output is correct |
7 |
Correct |
2320 ms |
9336 KB |
Output is correct |
8 |
Correct |
2313 ms |
9276 KB |
Output is correct |
9 |
Correct |
49 ms |
6520 KB |
Output is correct |
10 |
Correct |
2057 ms |
10112 KB |
Output is correct |
11 |
Correct |
1779 ms |
10164 KB |
Output is correct |
12 |
Correct |
1140 ms |
8584 KB |
Output is correct |
13 |
Correct |
1212 ms |
9720 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1463 ms |
9300 KB |
Output is correct |
2 |
Correct |
1283 ms |
7416 KB |
Output is correct |
3 |
Correct |
1772 ms |
9328 KB |
Output is correct |
4 |
Correct |
1432 ms |
9104 KB |
Output is correct |
5 |
Correct |
49 ms |
6588 KB |
Output is correct |
6 |
Correct |
1636 ms |
9136 KB |
Output is correct |
7 |
Correct |
1322 ms |
9188 KB |
Output is correct |
8 |
Correct |
1097 ms |
9280 KB |
Output is correct |
9 |
Correct |
779 ms |
8436 KB |
Output is correct |
10 |
Correct |
673 ms |
8184 KB |
Output is correct |
11 |
Correct |
842 ms |
9336 KB |
Output is correct |
12 |
Correct |
747 ms |
9464 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
893 ms |
9004 KB |
Output is correct |
2 |
Correct |
49 ms |
6524 KB |
Output is correct |
3 |
Correct |
108 ms |
6904 KB |
Output is correct |
4 |
Correct |
74 ms |
6904 KB |
Output is correct |
5 |
Correct |
641 ms |
9080 KB |
Output is correct |
6 |
Correct |
822 ms |
8944 KB |
Output is correct |
7 |
Correct |
598 ms |
9052 KB |
Output is correct |
8 |
Correct |
427 ms |
7928 KB |
Output is correct |
9 |
Correct |
417 ms |
7960 KB |
Output is correct |
10 |
Correct |
418 ms |
8056 KB |
Output is correct |
11 |
Correct |
700 ms |
8412 KB |
Output is correct |
12 |
Correct |
672 ms |
8408 KB |
Output is correct |
13 |
Correct |
753 ms |
8552 KB |
Output is correct |
14 |
Correct |
601 ms |
9108 KB |
Output is correct |
15 |
Correct |
601 ms |
9260 KB |
Output is correct |
16 |
Correct |
910 ms |
8972 KB |
Output is correct |
17 |
Correct |
934 ms |
9080 KB |
Output is correct |
18 |
Correct |
935 ms |
8960 KB |
Output is correct |
19 |
Correct |
905 ms |
9016 KB |
Output is correct |
20 |
Correct |
829 ms |
8900 KB |
Output is correct |
21 |
Correct |
830 ms |
8952 KB |
Output is correct |
22 |
Correct |
862 ms |
8992 KB |
Output is correct |
23 |
Correct |
652 ms |
8824 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1893 ms |
10332 KB |
Output is correct |
2 |
Correct |
1700 ms |
10148 KB |
Output is correct |
3 |
Correct |
1738 ms |
10064 KB |
Output is correct |
4 |
Correct |
1694 ms |
10268 KB |
Output is correct |
5 |
Correct |
1703 ms |
10104 KB |
Output is correct |
6 |
Correct |
2517 ms |
9336 KB |
Output is correct |
7 |
Correct |
2320 ms |
9336 KB |
Output is correct |
8 |
Correct |
2313 ms |
9276 KB |
Output is correct |
9 |
Correct |
49 ms |
6520 KB |
Output is correct |
10 |
Correct |
2057 ms |
10112 KB |
Output is correct |
11 |
Correct |
1779 ms |
10164 KB |
Output is correct |
12 |
Correct |
1140 ms |
8584 KB |
Output is correct |
13 |
Correct |
1212 ms |
9720 KB |
Output is correct |
14 |
Correct |
1463 ms |
9300 KB |
Output is correct |
15 |
Correct |
1283 ms |
7416 KB |
Output is correct |
16 |
Correct |
1772 ms |
9328 KB |
Output is correct |
17 |
Correct |
1432 ms |
9104 KB |
Output is correct |
18 |
Correct |
49 ms |
6588 KB |
Output is correct |
19 |
Correct |
1636 ms |
9136 KB |
Output is correct |
20 |
Correct |
1322 ms |
9188 KB |
Output is correct |
21 |
Correct |
1097 ms |
9280 KB |
Output is correct |
22 |
Correct |
779 ms |
8436 KB |
Output is correct |
23 |
Correct |
673 ms |
8184 KB |
Output is correct |
24 |
Correct |
842 ms |
9336 KB |
Output is correct |
25 |
Correct |
747 ms |
9464 KB |
Output is correct |
26 |
Correct |
1854 ms |
10196 KB |
Output is correct |
27 |
Correct |
2422 ms |
10176 KB |
Output is correct |
28 |
Correct |
1894 ms |
10040 KB |
Output is correct |
29 |
Correct |
1244 ms |
10220 KB |
Output is correct |
30 |
Correct |
2226 ms |
10308 KB |
Output is correct |
31 |
Correct |
2317 ms |
10232 KB |
Output is correct |
32 |
Correct |
2306 ms |
10344 KB |
Output is correct |
33 |
Correct |
1901 ms |
10432 KB |
Output is correct |
34 |
Correct |
1923 ms |
10180 KB |
Output is correct |
35 |
Correct |
1916 ms |
10232 KB |
Output is correct |
36 |
Correct |
1283 ms |
10192 KB |
Output is correct |
37 |
Correct |
1338 ms |
10080 KB |
Output is correct |
38 |
Correct |
1346 ms |
10108 KB |
Output is correct |
39 |
Correct |
840 ms |
8720 KB |
Output is correct |
40 |
Correct |
880 ms |
8840 KB |
Output is correct |
41 |
Correct |
836 ms |
8664 KB |
Output is correct |
42 |
Correct |
881 ms |
10480 KB |
Output is correct |
43 |
Correct |
847 ms |
10616 KB |
Output is correct |
44 |
Correct |
840 ms |
10616 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
4992 KB |
Output is correct |
2 |
Correct |
5 ms |
4992 KB |
Output is correct |
3 |
Correct |
92 ms |
5248 KB |
Output is correct |
4 |
Correct |
8 ms |
5120 KB |
Output is correct |
5 |
Correct |
25 ms |
5248 KB |
Output is correct |
6 |
Correct |
24 ms |
5240 KB |
Output is correct |
7 |
Correct |
28 ms |
5248 KB |
Output is correct |
8 |
Correct |
25 ms |
5248 KB |
Output is correct |
9 |
Correct |
32 ms |
5240 KB |
Output is correct |
10 |
Correct |
25 ms |
5248 KB |
Output is correct |
11 |
Correct |
25 ms |
5240 KB |
Output is correct |
12 |
Correct |
27 ms |
5248 KB |
Output is correct |
13 |
Correct |
34 ms |
5240 KB |
Output is correct |
14 |
Correct |
33 ms |
5244 KB |
Output is correct |
15 |
Correct |
28 ms |
5248 KB |
Output is correct |
16 |
Correct |
49 ms |
5240 KB |
Output is correct |
17 |
Correct |
31 ms |
5240 KB |
Output is correct |
18 |
Correct |
1893 ms |
10332 KB |
Output is correct |
19 |
Correct |
1700 ms |
10148 KB |
Output is correct |
20 |
Correct |
1738 ms |
10064 KB |
Output is correct |
21 |
Correct |
1694 ms |
10268 KB |
Output is correct |
22 |
Correct |
1703 ms |
10104 KB |
Output is correct |
23 |
Correct |
2517 ms |
9336 KB |
Output is correct |
24 |
Correct |
2320 ms |
9336 KB |
Output is correct |
25 |
Correct |
2313 ms |
9276 KB |
Output is correct |
26 |
Correct |
49 ms |
6520 KB |
Output is correct |
27 |
Correct |
2057 ms |
10112 KB |
Output is correct |
28 |
Correct |
1779 ms |
10164 KB |
Output is correct |
29 |
Correct |
1140 ms |
8584 KB |
Output is correct |
30 |
Correct |
1212 ms |
9720 KB |
Output is correct |
31 |
Correct |
1463 ms |
9300 KB |
Output is correct |
32 |
Correct |
1283 ms |
7416 KB |
Output is correct |
33 |
Correct |
1772 ms |
9328 KB |
Output is correct |
34 |
Correct |
1432 ms |
9104 KB |
Output is correct |
35 |
Correct |
49 ms |
6588 KB |
Output is correct |
36 |
Correct |
1636 ms |
9136 KB |
Output is correct |
37 |
Correct |
1322 ms |
9188 KB |
Output is correct |
38 |
Correct |
1097 ms |
9280 KB |
Output is correct |
39 |
Correct |
779 ms |
8436 KB |
Output is correct |
40 |
Correct |
673 ms |
8184 KB |
Output is correct |
41 |
Correct |
842 ms |
9336 KB |
Output is correct |
42 |
Correct |
747 ms |
9464 KB |
Output is correct |
43 |
Correct |
893 ms |
9004 KB |
Output is correct |
44 |
Correct |
49 ms |
6524 KB |
Output is correct |
45 |
Correct |
108 ms |
6904 KB |
Output is correct |
46 |
Correct |
74 ms |
6904 KB |
Output is correct |
47 |
Correct |
641 ms |
9080 KB |
Output is correct |
48 |
Correct |
822 ms |
8944 KB |
Output is correct |
49 |
Correct |
598 ms |
9052 KB |
Output is correct |
50 |
Correct |
427 ms |
7928 KB |
Output is correct |
51 |
Correct |
417 ms |
7960 KB |
Output is correct |
52 |
Correct |
418 ms |
8056 KB |
Output is correct |
53 |
Correct |
700 ms |
8412 KB |
Output is correct |
54 |
Correct |
672 ms |
8408 KB |
Output is correct |
55 |
Correct |
753 ms |
8552 KB |
Output is correct |
56 |
Correct |
601 ms |
9108 KB |
Output is correct |
57 |
Correct |
601 ms |
9260 KB |
Output is correct |
58 |
Correct |
910 ms |
8972 KB |
Output is correct |
59 |
Correct |
934 ms |
9080 KB |
Output is correct |
60 |
Correct |
935 ms |
8960 KB |
Output is correct |
61 |
Correct |
905 ms |
9016 KB |
Output is correct |
62 |
Correct |
829 ms |
8900 KB |
Output is correct |
63 |
Correct |
830 ms |
8952 KB |
Output is correct |
64 |
Correct |
862 ms |
8992 KB |
Output is correct |
65 |
Correct |
652 ms |
8824 KB |
Output is correct |
66 |
Correct |
1854 ms |
10196 KB |
Output is correct |
67 |
Correct |
2422 ms |
10176 KB |
Output is correct |
68 |
Correct |
1894 ms |
10040 KB |
Output is correct |
69 |
Correct |
1244 ms |
10220 KB |
Output is correct |
70 |
Correct |
2226 ms |
10308 KB |
Output is correct |
71 |
Correct |
2317 ms |
10232 KB |
Output is correct |
72 |
Correct |
2306 ms |
10344 KB |
Output is correct |
73 |
Correct |
1901 ms |
10432 KB |
Output is correct |
74 |
Correct |
1923 ms |
10180 KB |
Output is correct |
75 |
Correct |
1916 ms |
10232 KB |
Output is correct |
76 |
Correct |
1283 ms |
10192 KB |
Output is correct |
77 |
Correct |
1338 ms |
10080 KB |
Output is correct |
78 |
Correct |
1346 ms |
10108 KB |
Output is correct |
79 |
Correct |
840 ms |
8720 KB |
Output is correct |
80 |
Correct |
880 ms |
8840 KB |
Output is correct |
81 |
Correct |
836 ms |
8664 KB |
Output is correct |
82 |
Correct |
881 ms |
10480 KB |
Output is correct |
83 |
Correct |
847 ms |
10616 KB |
Output is correct |
84 |
Correct |
840 ms |
10616 KB |
Output is correct |
85 |
Correct |
2485 ms |
11224 KB |
Output is correct |
86 |
Correct |
259 ms |
7160 KB |
Output is correct |
87 |
Correct |
197 ms |
7032 KB |
Output is correct |
88 |
Correct |
1948 ms |
10940 KB |
Output is correct |
89 |
Correct |
2550 ms |
11124 KB |
Output is correct |
90 |
Correct |
1914 ms |
10516 KB |
Output is correct |
91 |
Correct |
1907 ms |
10164 KB |
Output is correct |
92 |
Correct |
1997 ms |
10244 KB |
Output is correct |
93 |
Correct |
2462 ms |
9472 KB |
Output is correct |
94 |
Correct |
2132 ms |
11224 KB |
Output is correct |
95 |
Correct |
2108 ms |
10820 KB |
Output is correct |
96 |
Correct |
2439 ms |
9976 KB |
Output is correct |
97 |
Correct |
1104 ms |
9512 KB |
Output is correct |
98 |
Correct |
1316 ms |
11012 KB |
Output is correct |
99 |
Correct |
2360 ms |
11092 KB |
Output is correct |
100 |
Correct |
2331 ms |
11220 KB |
Output is correct |
101 |
Correct |
2441 ms |
11332 KB |
Output is correct |
102 |
Correct |
2468 ms |
11308 KB |
Output is correct |
103 |
Correct |
2379 ms |
9936 KB |
Output is correct |
104 |
Correct |
2335 ms |
10168 KB |
Output is correct |
105 |
Correct |
1548 ms |
10360 KB |
Output is correct |
106 |
Correct |
1180 ms |
10744 KB |
Output is correct |
107 |
Correct |
1559 ms |
9080 KB |
Output is correct |
108 |
Correct |
2448 ms |
10232 KB |
Output is correct |
109 |
Correct |
1970 ms |
9720 KB |
Output is correct |