# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
253747 | 2020-07-28T15:39:29 Z | Saboon | Bridges (APIO19_bridges) | C++14 | 2920 ms | 11960 KB |
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 1e5 + 20; const int SQ = 600; int E1[maxn], E2[maxn], W[maxn], Wtmp[maxn], Q1[maxn], Q2[maxn], Qtype[maxn]; bool modify[maxn], visited[maxn]; vector<int> g[maxn]; int par[maxn], ans[maxn]; void dfsoff(int v){ visited[v] = 0; for (auto u : g[v]) if (visited[u]) dfsoff(u); } int dfs(int v){ int ret = -par[v]; visited[v] = 1; for (auto u : g[v]) if (!visited[u]) ret += dfs(u); return ret; } int get_par(int v){ return par[v] < 0 ? v : par[v] = get_par(par[v]); } void merge(int v, int u){ if ((v = get_par(v)) == (u = get_par(u))) return; if (par[v] > par[u]) swap(v, u); par[v] += par[u]; par[u] = v; } int main(){ int n, m; scanf("%d%d", &n, &m); vector<int> Edge; for (int i = 1; i <= m; i++){ scanf("%d%d%d", &E1[i], &E2[i], &W[i]); Edge.push_back(i); } int q; scanf("%d", &q); for (int i = 0; i < q; i++) scanf("%d%d%d", &Qtype[i], &Q1[i], &Q2[i]); for (int i = 0; i < q; i += SQ){ memset(par, -1, sizeof par); int l = i, r = min(i+SQ,q); vector<int> a, b; for (int j = l; j < r; j++){ if (Qtype[j] == 1) modify[Q1[j]] = 1, b.push_back(Q1[j]); if (Qtype[j] == 2) a.push_back(j); } sort(b.begin(), b.end()); b.resize(unique(b.begin(),b.end())-b.begin()); sort(a.begin(), a.end(), [](int x, int y){return Q2[x] > Q2[y];}); sort(Edge.begin(), Edge.end(), [](int x, int y){return W[x] > W[y];}); int ptr = 0; for (int x = l; x < r; x++) if (Qtype[x] == 1) Wtmp[Q1[x]] = W[Q1[x]]; for (auto j : a){ while (ptr < m and W[Edge[ptr]] >= Q2[j]){ if (!modify[Edge[ptr]]) merge(E1[Edge[ptr]], E2[Edge[ptr]]); ptr ++; } for (int x = l; x < j; x++) if (Qtype[x] == 1) W[Q1[x]] = Q2[x]; for (auto x : b){ if (W[x] >= Q2[j]){ g[get_par(E1[x])].push_back(get_par(E2[x])); g[get_par(E2[x])].push_back(get_par(E1[x])); } } ans[j] = dfs(get_par(Q1[j])); dfsoff(get_par(Q1[j])); for (auto x : b) if (W[x] >= Q2[j]) g[get_par(E1[x])].pop_back(), g[get_par(E2[x])].pop_back(); for (int x = l; x < j; x++) if (Qtype[x] == 1) W[Q1[x]] = Wtmp[Q1[x]]; } for (int j = l; j < r; j++) if (Qtype[j] == 1) modify[Q1[j]] = 0, W[Q1[j]] = Q2[j]; } for (int i = 0; i < q; i++) if (Qtype[i] == 2) printf("%d\n", ans[i]); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 3072 KB | Output is correct |
2 | Correct | 2 ms | 3072 KB | Output is correct |
3 | Correct | 51 ms | 3328 KB | Output is correct |
4 | Correct | 14 ms | 3200 KB | Output is correct |
5 | Correct | 27 ms | 3328 KB | Output is correct |
6 | Correct | 26 ms | 3320 KB | Output is correct |
7 | Correct | 27 ms | 3320 KB | Output is correct |
8 | Correct | 26 ms | 3320 KB | Output is correct |
9 | Correct | 34 ms | 3320 KB | Output is correct |
10 | Correct | 25 ms | 3328 KB | Output is correct |
11 | Correct | 24 ms | 3320 KB | Output is correct |
12 | Correct | 27 ms | 3328 KB | Output is correct |
13 | Correct | 34 ms | 3324 KB | Output is correct |
14 | Correct | 33 ms | 3320 KB | Output is correct |
15 | Correct | 33 ms | 3320 KB | Output is correct |
16 | Correct | 29 ms | 3328 KB | Output is correct |
17 | Correct | 29 ms | 3328 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1565 ms | 7136 KB | Output is correct |
2 | Correct | 1515 ms | 7156 KB | Output is correct |
3 | Correct | 1544 ms | 7156 KB | Output is correct |
4 | Correct | 1470 ms | 7156 KB | Output is correct |
5 | Correct | 1491 ms | 7156 KB | Output is correct |
6 | Correct | 2265 ms | 6332 KB | Output is correct |
7 | Correct | 2118 ms | 6588 KB | Output is correct |
8 | Correct | 1994 ms | 6456 KB | Output is correct |
9 | Correct | 114 ms | 4856 KB | Output is correct |
10 | Correct | 1563 ms | 7408 KB | Output is correct |
11 | Correct | 1417 ms | 7352 KB | Output is correct |
12 | Correct | 1366 ms | 6540 KB | Output is correct |
13 | Correct | 1221 ms | 6356 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1177 ms | 6648 KB | Output is correct |
2 | Correct | 929 ms | 5296 KB | Output is correct |
3 | Correct | 1395 ms | 6648 KB | Output is correct |
4 | Correct | 1205 ms | 6604 KB | Output is correct |
5 | Correct | 133 ms | 4856 KB | Output is correct |
6 | Correct | 1302 ms | 6492 KB | Output is correct |
7 | Correct | 1099 ms | 6592 KB | Output is correct |
8 | Correct | 979 ms | 6584 KB | Output is correct |
9 | Correct | 876 ms | 6264 KB | Output is correct |
10 | Correct | 803 ms | 6088 KB | Output is correct |
11 | Correct | 767 ms | 6520 KB | Output is correct |
12 | Correct | 686 ms | 6520 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1234 ms | 6824 KB | Output is correct |
2 | Correct | 116 ms | 4856 KB | Output is correct |
3 | Correct | 144 ms | 4972 KB | Output is correct |
4 | Correct | 90 ms | 5116 KB | Output is correct |
5 | Correct | 903 ms | 6896 KB | Output is correct |
6 | Correct | 1236 ms | 6768 KB | Output is correct |
7 | Correct | 890 ms | 6896 KB | Output is correct |
8 | Correct | 667 ms | 6008 KB | Output is correct |
9 | Correct | 647 ms | 5840 KB | Output is correct |
10 | Correct | 651 ms | 6132 KB | Output is correct |
11 | Correct | 1063 ms | 6384 KB | Output is correct |
12 | Correct | 1061 ms | 6328 KB | Output is correct |
13 | Correct | 1069 ms | 6644 KB | Output is correct |
14 | Correct | 860 ms | 7108 KB | Output is correct |
15 | Correct | 854 ms | 6896 KB | Output is correct |
16 | Correct | 1313 ms | 6808 KB | Output is correct |
17 | Correct | 1348 ms | 6896 KB | Output is correct |
18 | Correct | 1330 ms | 6896 KB | Output is correct |
19 | Correct | 1329 ms | 7024 KB | Output is correct |
20 | Correct | 1234 ms | 6648 KB | Output is correct |
21 | Correct | 1212 ms | 6740 KB | Output is correct |
22 | Correct | 1312 ms | 6924 KB | Output is correct |
23 | Correct | 973 ms | 6764 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1565 ms | 7136 KB | Output is correct |
2 | Correct | 1515 ms | 7156 KB | Output is correct |
3 | Correct | 1544 ms | 7156 KB | Output is correct |
4 | Correct | 1470 ms | 7156 KB | Output is correct |
5 | Correct | 1491 ms | 7156 KB | Output is correct |
6 | Correct | 2265 ms | 6332 KB | Output is correct |
7 | Correct | 2118 ms | 6588 KB | Output is correct |
8 | Correct | 1994 ms | 6456 KB | Output is correct |
9 | Correct | 114 ms | 4856 KB | Output is correct |
10 | Correct | 1563 ms | 7408 KB | Output is correct |
11 | Correct | 1417 ms | 7352 KB | Output is correct |
12 | Correct | 1366 ms | 6540 KB | Output is correct |
13 | Correct | 1221 ms | 6356 KB | Output is correct |
14 | Correct | 1177 ms | 6648 KB | Output is correct |
15 | Correct | 929 ms | 5296 KB | Output is correct |
16 | Correct | 1395 ms | 6648 KB | Output is correct |
17 | Correct | 1205 ms | 6604 KB | Output is correct |
18 | Correct | 133 ms | 4856 KB | Output is correct |
19 | Correct | 1302 ms | 6492 KB | Output is correct |
20 | Correct | 1099 ms | 6592 KB | Output is correct |
21 | Correct | 979 ms | 6584 KB | Output is correct |
22 | Correct | 876 ms | 6264 KB | Output is correct |
23 | Correct | 803 ms | 6088 KB | Output is correct |
24 | Correct | 767 ms | 6520 KB | Output is correct |
25 | Correct | 686 ms | 6520 KB | Output is correct |
26 | Correct | 1545 ms | 7284 KB | Output is correct |
27 | Correct | 2001 ms | 7188 KB | Output is correct |
28 | Correct | 1682 ms | 7452 KB | Output is correct |
29 | Correct | 1250 ms | 7156 KB | Output is correct |
30 | Correct | 1942 ms | 7156 KB | Output is correct |
31 | Correct | 1985 ms | 7156 KB | Output is correct |
32 | Correct | 2003 ms | 7284 KB | Output is correct |
33 | Correct | 1685 ms | 7140 KB | Output is correct |
34 | Correct | 1676 ms | 7156 KB | Output is correct |
35 | Correct | 1692 ms | 7280 KB | Output is correct |
36 | Correct | 1326 ms | 7156 KB | Output is correct |
37 | Correct | 1342 ms | 7040 KB | Output is correct |
38 | Correct | 1284 ms | 7040 KB | Output is correct |
39 | Correct | 1173 ms | 6516 KB | Output is correct |
40 | Correct | 1117 ms | 6516 KB | Output is correct |
41 | Correct | 1146 ms | 6732 KB | Output is correct |
42 | Correct | 956 ms | 7340 KB | Output is correct |
43 | Correct | 993 ms | 7156 KB | Output is correct |
44 | Correct | 969 ms | 7284 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 3072 KB | Output is correct |
2 | Correct | 2 ms | 3072 KB | Output is correct |
3 | Correct | 51 ms | 3328 KB | Output is correct |
4 | Correct | 14 ms | 3200 KB | Output is correct |
5 | Correct | 27 ms | 3328 KB | Output is correct |
6 | Correct | 26 ms | 3320 KB | Output is correct |
7 | Correct | 27 ms | 3320 KB | Output is correct |
8 | Correct | 26 ms | 3320 KB | Output is correct |
9 | Correct | 34 ms | 3320 KB | Output is correct |
10 | Correct | 25 ms | 3328 KB | Output is correct |
11 | Correct | 24 ms | 3320 KB | Output is correct |
12 | Correct | 27 ms | 3328 KB | Output is correct |
13 | Correct | 34 ms | 3324 KB | Output is correct |
14 | Correct | 33 ms | 3320 KB | Output is correct |
15 | Correct | 33 ms | 3320 KB | Output is correct |
16 | Correct | 29 ms | 3328 KB | Output is correct |
17 | Correct | 29 ms | 3328 KB | Output is correct |
18 | Correct | 1565 ms | 7136 KB | Output is correct |
19 | Correct | 1515 ms | 7156 KB | Output is correct |
20 | Correct | 1544 ms | 7156 KB | Output is correct |
21 | Correct | 1470 ms | 7156 KB | Output is correct |
22 | Correct | 1491 ms | 7156 KB | Output is correct |
23 | Correct | 2265 ms | 6332 KB | Output is correct |
24 | Correct | 2118 ms | 6588 KB | Output is correct |
25 | Correct | 1994 ms | 6456 KB | Output is correct |
26 | Correct | 114 ms | 4856 KB | Output is correct |
27 | Correct | 1563 ms | 7408 KB | Output is correct |
28 | Correct | 1417 ms | 7352 KB | Output is correct |
29 | Correct | 1366 ms | 6540 KB | Output is correct |
30 | Correct | 1221 ms | 6356 KB | Output is correct |
31 | Correct | 1177 ms | 6648 KB | Output is correct |
32 | Correct | 929 ms | 5296 KB | Output is correct |
33 | Correct | 1395 ms | 6648 KB | Output is correct |
34 | Correct | 1205 ms | 6604 KB | Output is correct |
35 | Correct | 133 ms | 4856 KB | Output is correct |
36 | Correct | 1302 ms | 6492 KB | Output is correct |
37 | Correct | 1099 ms | 6592 KB | Output is correct |
38 | Correct | 979 ms | 6584 KB | Output is correct |
39 | Correct | 876 ms | 6264 KB | Output is correct |
40 | Correct | 803 ms | 6088 KB | Output is correct |
41 | Correct | 767 ms | 6520 KB | Output is correct |
42 | Correct | 686 ms | 6520 KB | Output is correct |
43 | Correct | 1234 ms | 6824 KB | Output is correct |
44 | Correct | 116 ms | 4856 KB | Output is correct |
45 | Correct | 144 ms | 4972 KB | Output is correct |
46 | Correct | 90 ms | 5116 KB | Output is correct |
47 | Correct | 903 ms | 6896 KB | Output is correct |
48 | Correct | 1236 ms | 6768 KB | Output is correct |
49 | Correct | 890 ms | 6896 KB | Output is correct |
50 | Correct | 667 ms | 6008 KB | Output is correct |
51 | Correct | 647 ms | 5840 KB | Output is correct |
52 | Correct | 651 ms | 6132 KB | Output is correct |
53 | Correct | 1063 ms | 6384 KB | Output is correct |
54 | Correct | 1061 ms | 6328 KB | Output is correct |
55 | Correct | 1069 ms | 6644 KB | Output is correct |
56 | Correct | 860 ms | 7108 KB | Output is correct |
57 | Correct | 854 ms | 6896 KB | Output is correct |
58 | Correct | 1313 ms | 6808 KB | Output is correct |
59 | Correct | 1348 ms | 6896 KB | Output is correct |
60 | Correct | 1330 ms | 6896 KB | Output is correct |
61 | Correct | 1329 ms | 7024 KB | Output is correct |
62 | Correct | 1234 ms | 6648 KB | Output is correct |
63 | Correct | 1212 ms | 6740 KB | Output is correct |
64 | Correct | 1312 ms | 6924 KB | Output is correct |
65 | Correct | 973 ms | 6764 KB | Output is correct |
66 | Correct | 1545 ms | 7284 KB | Output is correct |
67 | Correct | 2001 ms | 7188 KB | Output is correct |
68 | Correct | 1682 ms | 7452 KB | Output is correct |
69 | Correct | 1250 ms | 7156 KB | Output is correct |
70 | Correct | 1942 ms | 7156 KB | Output is correct |
71 | Correct | 1985 ms | 7156 KB | Output is correct |
72 | Correct | 2003 ms | 7284 KB | Output is correct |
73 | Correct | 1685 ms | 7140 KB | Output is correct |
74 | Correct | 1676 ms | 7156 KB | Output is correct |
75 | Correct | 1692 ms | 7280 KB | Output is correct |
76 | Correct | 1326 ms | 7156 KB | Output is correct |
77 | Correct | 1342 ms | 7040 KB | Output is correct |
78 | Correct | 1284 ms | 7040 KB | Output is correct |
79 | Correct | 1173 ms | 6516 KB | Output is correct |
80 | Correct | 1117 ms | 6516 KB | Output is correct |
81 | Correct | 1146 ms | 6732 KB | Output is correct |
82 | Correct | 956 ms | 7340 KB | Output is correct |
83 | Correct | 993 ms | 7156 KB | Output is correct |
84 | Correct | 969 ms | 7284 KB | Output is correct |
85 | Correct | 2824 ms | 8376 KB | Output is correct |
86 | Correct | 256 ms | 7280 KB | Output is correct |
87 | Correct | 174 ms | 7536 KB | Output is correct |
88 | Correct | 1732 ms | 10352 KB | Output is correct |
89 | Correct | 2680 ms | 11960 KB | Output is correct |
90 | Correct | 1866 ms | 9836 KB | Output is correct |
91 | Correct | 1806 ms | 9948 KB | Output is correct |
92 | Correct | 1707 ms | 10020 KB | Output is correct |
93 | Correct | 2094 ms | 9208 KB | Output is correct |
94 | Correct | 2314 ms | 11100 KB | Output is correct |
95 | Correct | 2336 ms | 11248 KB | Output is correct |
96 | Correct | 2574 ms | 10096 KB | Output is correct |
97 | Correct | 1223 ms | 9452 KB | Output is correct |
98 | Correct | 1302 ms | 10132 KB | Output is correct |
99 | Correct | 2920 ms | 11824 KB | Output is correct |
100 | Correct | 2786 ms | 11888 KB | Output is correct |
101 | Correct | 2845 ms | 11908 KB | Output is correct |
102 | Correct | 2846 ms | 11948 KB | Output is correct |
103 | Correct | 2638 ms | 10156 KB | Output is correct |
104 | Correct | 2692 ms | 10072 KB | Output is correct |
105 | Correct | 1973 ms | 10360 KB | Output is correct |
106 | Correct | 1641 ms | 10412 KB | Output is correct |
107 | Correct | 2092 ms | 10260 KB | Output is correct |
108 | Correct | 2815 ms | 10696 KB | Output is correct |
109 | Correct | 1971 ms | 8680 KB | Output is correct |