# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
969864 |
2024-04-25T17:41:02 Z |
JwFXoiz |
Bridges (APIO19_bridges) |
C++17 |
|
3000 ms |
12004 KB |
#include <bits/stdc++.h>
using namespace std;
#define inf 0x3F3F3F3F
struct DSU
{
int n;
vector<int> e;
void init(int N)
{
n = N;
e.assign(n + 1, -1);
}
int get(int x)
{
if (e[x] < 0) return x;
return e[x] = get(e[x]);
}
void unite(int x, int y)
{
x = get(x), y = get(y);
if (x == y) return;
if (e[x] > e[y]) swap(x, y);
e[x] += e[y];
e[y] = x;
}
};
const int MXN = 1e5 + 5;
const int B = 230;
int n, m, Q;
vector<int> adj[MXN];
array<int, 3> e[MXN];
array<int, 3> q[MXN];
DSU dsu;
int inq[MXN], renw[MXN], used[MXN], ans[MXN];
int res;
vector<int> node, o, oe;
void dfs(int a)
{
node.push_back(a);
res += -dsu.e[dsu.get(a)];
used[a] = 1;
for (int v : adj[a])
{
if (!used[v]) dfs(v);
}
}
signed main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
for (int i = 0; i < m; i++) for (int j = 0; j < 3; j++) cin >> e[i][j];
cin >> Q;
for (int i = 0; i < Q; i++)
{
for (int j = 0; j < 3; j++) cin >> q[i][j];
q[i][1]--;
}
oe.assign(m, 0);
iota(oe.begin(), oe.end(), 0);
for (int l = 0; l < Q; l += B)
{
dsu.init(n);
o.clear();
int r = min(Q, l + B);
for (int i = l; i < r; i++) if (q[i][0] == 1) inq[q[i][1]] = 1;
for (int i = l; i < r; i++) if (q[i][0] == 2) o.push_back(i);
sort(oe.begin(), oe.end(), [&](int a, int b)
{
return e[a][2] > e[b][2];
});
sort(o.begin(), o.end(), [&](int a, int b)
{
return q[a][2] > q[b][2];
});
int j = 0;
for (int x : o)
{
while (j < m && e[oe[j]][2] >= q[x][2])
{
if (!inq[oe[j]]) dsu.unite(e[oe[j]][0], e[oe[j]][1]);
j++;
}
for (int i = x - 1; i >= l; i--)
{
if (q[i][0] == 1 && !renw[q[i][1]])
{
renw[q[i][1]] = 1;
if (q[i][2] >= q[x][2]) adj[dsu.get(e[q[i][1]][0])].push_back(dsu.get(e[q[i][1]][1])), adj[dsu.get(e[q[i][1]][1])].push_back(dsu.get(e[q[i][1]][0]));
}
}
for (int i = x + 1; i < r; i++)
{
if (q[i][0] == 1 && !renw[q[i][1]])
{
renw[q[i][1]] = 1;
if (e[q[i][1]][2] >= q[x][2]) adj[dsu.get(e[q[i][1]][0])].push_back(dsu.get(e[q[i][1]][1])), adj[dsu.get(e[q[i][1]][1])].push_back(dsu.get(e[q[i][1]][0]));
}
}
res = 0;
dfs(dsu.get(q[x][1] + 1));
for (int x : node) used[x] = 0;
node.clear();
ans[x] = res;
for (int i = l; i < r; i++)
{
if (q[i][0] == 1)
{
renw[q[i][1]] = 0;
adj[dsu.get(e[q[i][1]][0])].clear(), adj[dsu.get(e[q[i][1]][1])].clear();
}
}
}
for (int i = l; i < r; i++)
{
if (q[i][0] == 1) e[q[i][1]][2] = q[i][2], inq[q[i][1]] = 0;
}
}
for (int i = 0; i < Q; i++) if (q[i][0] == 2) cout << ans[i] << ' ';
cout << '\n';
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
6492 KB |
Output is correct |
2 |
Correct |
3 ms |
6492 KB |
Output is correct |
3 |
Correct |
17 ms |
6492 KB |
Output is correct |
4 |
Correct |
7 ms |
6492 KB |
Output is correct |
5 |
Correct |
14 ms |
6488 KB |
Output is correct |
6 |
Correct |
13 ms |
6596 KB |
Output is correct |
7 |
Correct |
15 ms |
6488 KB |
Output is correct |
8 |
Correct |
15 ms |
6488 KB |
Output is correct |
9 |
Correct |
15 ms |
6492 KB |
Output is correct |
10 |
Correct |
15 ms |
6492 KB |
Output is correct |
11 |
Correct |
14 ms |
6492 KB |
Output is correct |
12 |
Correct |
14 ms |
6492 KB |
Output is correct |
13 |
Correct |
20 ms |
6492 KB |
Output is correct |
14 |
Correct |
17 ms |
6492 KB |
Output is correct |
15 |
Correct |
15 ms |
6492 KB |
Output is correct |
16 |
Correct |
14 ms |
6488 KB |
Output is correct |
17 |
Correct |
14 ms |
6492 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1686 ms |
8556 KB |
Output is correct |
2 |
Correct |
1643 ms |
8480 KB |
Output is correct |
3 |
Correct |
1706 ms |
8672 KB |
Output is correct |
4 |
Correct |
1642 ms |
8820 KB |
Output is correct |
5 |
Correct |
1666 ms |
11392 KB |
Output is correct |
6 |
Correct |
1767 ms |
10120 KB |
Output is correct |
7 |
Correct |
1778 ms |
10384 KB |
Output is correct |
8 |
Correct |
1687 ms |
10348 KB |
Output is correct |
9 |
Correct |
51 ms |
8060 KB |
Output is correct |
10 |
Correct |
956 ms |
10296 KB |
Output is correct |
11 |
Correct |
943 ms |
10808 KB |
Output is correct |
12 |
Correct |
1425 ms |
10164 KB |
Output is correct |
13 |
Correct |
1575 ms |
10116 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1022 ms |
7996 KB |
Output is correct |
2 |
Correct |
353 ms |
8564 KB |
Output is correct |
3 |
Correct |
1052 ms |
10292 KB |
Output is correct |
4 |
Correct |
1046 ms |
10300 KB |
Output is correct |
5 |
Correct |
51 ms |
8020 KB |
Output is correct |
6 |
Correct |
1004 ms |
10084 KB |
Output is correct |
7 |
Correct |
1067 ms |
10104 KB |
Output is correct |
8 |
Correct |
1036 ms |
10296 KB |
Output is correct |
9 |
Correct |
869 ms |
9988 KB |
Output is correct |
10 |
Correct |
894 ms |
9712 KB |
Output is correct |
11 |
Correct |
956 ms |
10196 KB |
Output is correct |
12 |
Correct |
973 ms |
10248 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1998 ms |
7564 KB |
Output is correct |
2 |
Correct |
55 ms |
8016 KB |
Output is correct |
3 |
Correct |
152 ms |
8788 KB |
Output is correct |
4 |
Correct |
121 ms |
8916 KB |
Output is correct |
5 |
Correct |
1515 ms |
9860 KB |
Output is correct |
6 |
Correct |
1861 ms |
11600 KB |
Output is correct |
7 |
Correct |
1593 ms |
9848 KB |
Output is correct |
8 |
Correct |
955 ms |
9956 KB |
Output is correct |
9 |
Correct |
921 ms |
10108 KB |
Output is correct |
10 |
Correct |
936 ms |
9888 KB |
Output is correct |
11 |
Correct |
1607 ms |
10596 KB |
Output is correct |
12 |
Correct |
1523 ms |
10580 KB |
Output is correct |
13 |
Correct |
1616 ms |
10580 KB |
Output is correct |
14 |
Correct |
1451 ms |
10096 KB |
Output is correct |
15 |
Correct |
1437 ms |
10352 KB |
Output is correct |
16 |
Correct |
2025 ms |
11556 KB |
Output is correct |
17 |
Correct |
2025 ms |
11372 KB |
Output is correct |
18 |
Correct |
1966 ms |
11640 KB |
Output is correct |
19 |
Correct |
2019 ms |
11384 KB |
Output is correct |
20 |
Correct |
1825 ms |
10764 KB |
Output is correct |
21 |
Correct |
1827 ms |
10872 KB |
Output is correct |
22 |
Correct |
1952 ms |
11360 KB |
Output is correct |
23 |
Correct |
1503 ms |
9788 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1686 ms |
8556 KB |
Output is correct |
2 |
Correct |
1643 ms |
8480 KB |
Output is correct |
3 |
Correct |
1706 ms |
8672 KB |
Output is correct |
4 |
Correct |
1642 ms |
8820 KB |
Output is correct |
5 |
Correct |
1666 ms |
11392 KB |
Output is correct |
6 |
Correct |
1767 ms |
10120 KB |
Output is correct |
7 |
Correct |
1778 ms |
10384 KB |
Output is correct |
8 |
Correct |
1687 ms |
10348 KB |
Output is correct |
9 |
Correct |
51 ms |
8060 KB |
Output is correct |
10 |
Correct |
956 ms |
10296 KB |
Output is correct |
11 |
Correct |
943 ms |
10808 KB |
Output is correct |
12 |
Correct |
1425 ms |
10164 KB |
Output is correct |
13 |
Correct |
1575 ms |
10116 KB |
Output is correct |
14 |
Correct |
1022 ms |
7996 KB |
Output is correct |
15 |
Correct |
353 ms |
8564 KB |
Output is correct |
16 |
Correct |
1052 ms |
10292 KB |
Output is correct |
17 |
Correct |
1046 ms |
10300 KB |
Output is correct |
18 |
Correct |
51 ms |
8020 KB |
Output is correct |
19 |
Correct |
1004 ms |
10084 KB |
Output is correct |
20 |
Correct |
1067 ms |
10104 KB |
Output is correct |
21 |
Correct |
1036 ms |
10296 KB |
Output is correct |
22 |
Correct |
869 ms |
9988 KB |
Output is correct |
23 |
Correct |
894 ms |
9712 KB |
Output is correct |
24 |
Correct |
956 ms |
10196 KB |
Output is correct |
25 |
Correct |
973 ms |
10248 KB |
Output is correct |
26 |
Correct |
1700 ms |
11244 KB |
Output is correct |
27 |
Correct |
1727 ms |
11092 KB |
Output is correct |
28 |
Correct |
1744 ms |
11464 KB |
Output is correct |
29 |
Correct |
1696 ms |
11192 KB |
Output is correct |
30 |
Correct |
1731 ms |
11076 KB |
Output is correct |
31 |
Correct |
1818 ms |
10992 KB |
Output is correct |
32 |
Correct |
1872 ms |
11424 KB |
Output is correct |
33 |
Correct |
1739 ms |
11160 KB |
Output is correct |
34 |
Correct |
1702 ms |
11252 KB |
Output is correct |
35 |
Correct |
1716 ms |
11384 KB |
Output is correct |
36 |
Correct |
1658 ms |
11132 KB |
Output is correct |
37 |
Correct |
1617 ms |
11104 KB |
Output is correct |
38 |
Correct |
1663 ms |
11248 KB |
Output is correct |
39 |
Correct |
1494 ms |
10520 KB |
Output is correct |
40 |
Correct |
1562 ms |
10632 KB |
Output is correct |
41 |
Correct |
1517 ms |
10456 KB |
Output is correct |
42 |
Correct |
1479 ms |
11308 KB |
Output is correct |
43 |
Correct |
1454 ms |
11244 KB |
Output is correct |
44 |
Correct |
1585 ms |
11604 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
6492 KB |
Output is correct |
2 |
Correct |
3 ms |
6492 KB |
Output is correct |
3 |
Correct |
17 ms |
6492 KB |
Output is correct |
4 |
Correct |
7 ms |
6492 KB |
Output is correct |
5 |
Correct |
14 ms |
6488 KB |
Output is correct |
6 |
Correct |
13 ms |
6596 KB |
Output is correct |
7 |
Correct |
15 ms |
6488 KB |
Output is correct |
8 |
Correct |
15 ms |
6488 KB |
Output is correct |
9 |
Correct |
15 ms |
6492 KB |
Output is correct |
10 |
Correct |
15 ms |
6492 KB |
Output is correct |
11 |
Correct |
14 ms |
6492 KB |
Output is correct |
12 |
Correct |
14 ms |
6492 KB |
Output is correct |
13 |
Correct |
20 ms |
6492 KB |
Output is correct |
14 |
Correct |
17 ms |
6492 KB |
Output is correct |
15 |
Correct |
15 ms |
6492 KB |
Output is correct |
16 |
Correct |
14 ms |
6488 KB |
Output is correct |
17 |
Correct |
14 ms |
6492 KB |
Output is correct |
18 |
Correct |
1686 ms |
8556 KB |
Output is correct |
19 |
Correct |
1643 ms |
8480 KB |
Output is correct |
20 |
Correct |
1706 ms |
8672 KB |
Output is correct |
21 |
Correct |
1642 ms |
8820 KB |
Output is correct |
22 |
Correct |
1666 ms |
11392 KB |
Output is correct |
23 |
Correct |
1767 ms |
10120 KB |
Output is correct |
24 |
Correct |
1778 ms |
10384 KB |
Output is correct |
25 |
Correct |
1687 ms |
10348 KB |
Output is correct |
26 |
Correct |
51 ms |
8060 KB |
Output is correct |
27 |
Correct |
956 ms |
10296 KB |
Output is correct |
28 |
Correct |
943 ms |
10808 KB |
Output is correct |
29 |
Correct |
1425 ms |
10164 KB |
Output is correct |
30 |
Correct |
1575 ms |
10116 KB |
Output is correct |
31 |
Correct |
1022 ms |
7996 KB |
Output is correct |
32 |
Correct |
353 ms |
8564 KB |
Output is correct |
33 |
Correct |
1052 ms |
10292 KB |
Output is correct |
34 |
Correct |
1046 ms |
10300 KB |
Output is correct |
35 |
Correct |
51 ms |
8020 KB |
Output is correct |
36 |
Correct |
1004 ms |
10084 KB |
Output is correct |
37 |
Correct |
1067 ms |
10104 KB |
Output is correct |
38 |
Correct |
1036 ms |
10296 KB |
Output is correct |
39 |
Correct |
869 ms |
9988 KB |
Output is correct |
40 |
Correct |
894 ms |
9712 KB |
Output is correct |
41 |
Correct |
956 ms |
10196 KB |
Output is correct |
42 |
Correct |
973 ms |
10248 KB |
Output is correct |
43 |
Correct |
1998 ms |
7564 KB |
Output is correct |
44 |
Correct |
55 ms |
8016 KB |
Output is correct |
45 |
Correct |
152 ms |
8788 KB |
Output is correct |
46 |
Correct |
121 ms |
8916 KB |
Output is correct |
47 |
Correct |
1515 ms |
9860 KB |
Output is correct |
48 |
Correct |
1861 ms |
11600 KB |
Output is correct |
49 |
Correct |
1593 ms |
9848 KB |
Output is correct |
50 |
Correct |
955 ms |
9956 KB |
Output is correct |
51 |
Correct |
921 ms |
10108 KB |
Output is correct |
52 |
Correct |
936 ms |
9888 KB |
Output is correct |
53 |
Correct |
1607 ms |
10596 KB |
Output is correct |
54 |
Correct |
1523 ms |
10580 KB |
Output is correct |
55 |
Correct |
1616 ms |
10580 KB |
Output is correct |
56 |
Correct |
1451 ms |
10096 KB |
Output is correct |
57 |
Correct |
1437 ms |
10352 KB |
Output is correct |
58 |
Correct |
2025 ms |
11556 KB |
Output is correct |
59 |
Correct |
2025 ms |
11372 KB |
Output is correct |
60 |
Correct |
1966 ms |
11640 KB |
Output is correct |
61 |
Correct |
2019 ms |
11384 KB |
Output is correct |
62 |
Correct |
1825 ms |
10764 KB |
Output is correct |
63 |
Correct |
1827 ms |
10872 KB |
Output is correct |
64 |
Correct |
1952 ms |
11360 KB |
Output is correct |
65 |
Correct |
1503 ms |
9788 KB |
Output is correct |
66 |
Correct |
1700 ms |
11244 KB |
Output is correct |
67 |
Correct |
1727 ms |
11092 KB |
Output is correct |
68 |
Correct |
1744 ms |
11464 KB |
Output is correct |
69 |
Correct |
1696 ms |
11192 KB |
Output is correct |
70 |
Correct |
1731 ms |
11076 KB |
Output is correct |
71 |
Correct |
1818 ms |
10992 KB |
Output is correct |
72 |
Correct |
1872 ms |
11424 KB |
Output is correct |
73 |
Correct |
1739 ms |
11160 KB |
Output is correct |
74 |
Correct |
1702 ms |
11252 KB |
Output is correct |
75 |
Correct |
1716 ms |
11384 KB |
Output is correct |
76 |
Correct |
1658 ms |
11132 KB |
Output is correct |
77 |
Correct |
1617 ms |
11104 KB |
Output is correct |
78 |
Correct |
1663 ms |
11248 KB |
Output is correct |
79 |
Correct |
1494 ms |
10520 KB |
Output is correct |
80 |
Correct |
1562 ms |
10632 KB |
Output is correct |
81 |
Correct |
1517 ms |
10456 KB |
Output is correct |
82 |
Correct |
1479 ms |
11308 KB |
Output is correct |
83 |
Correct |
1454 ms |
11244 KB |
Output is correct |
84 |
Correct |
1585 ms |
11604 KB |
Output is correct |
85 |
Execution timed out |
3075 ms |
12004 KB |
Time limit exceeded |
86 |
Halted |
0 ms |
0 KB |
- |