# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
969868 |
2024-04-25T17:45:28 Z |
JwFXoiz |
Bridges (APIO19_bridges) |
C++17 |
|
1997 ms |
12368 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 = 500;
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 |
2 ms |
6492 KB |
Output is correct |
3 |
Correct |
39 ms |
6596 KB |
Output is correct |
4 |
Correct |
10 ms |
6492 KB |
Output is correct |
5 |
Correct |
21 ms |
6564 KB |
Output is correct |
6 |
Correct |
20 ms |
6492 KB |
Output is correct |
7 |
Correct |
20 ms |
6584 KB |
Output is correct |
8 |
Correct |
20 ms |
6488 KB |
Output is correct |
9 |
Correct |
22 ms |
6492 KB |
Output is correct |
10 |
Correct |
21 ms |
6836 KB |
Output is correct |
11 |
Correct |
19 ms |
6492 KB |
Output is correct |
12 |
Correct |
19 ms |
6488 KB |
Output is correct |
13 |
Correct |
23 ms |
6588 KB |
Output is correct |
14 |
Correct |
22 ms |
6560 KB |
Output is correct |
15 |
Correct |
22 ms |
6492 KB |
Output is correct |
16 |
Correct |
21 ms |
6488 KB |
Output is correct |
17 |
Correct |
20 ms |
6552 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1006 ms |
8408 KB |
Output is correct |
2 |
Correct |
1105 ms |
8868 KB |
Output is correct |
3 |
Correct |
966 ms |
8536 KB |
Output is correct |
4 |
Correct |
1040 ms |
8356 KB |
Output is correct |
5 |
Correct |
1032 ms |
8412 KB |
Output is correct |
6 |
Correct |
1337 ms |
7660 KB |
Output is correct |
7 |
Correct |
1152 ms |
7592 KB |
Output is correct |
8 |
Correct |
1159 ms |
7504 KB |
Output is correct |
9 |
Correct |
117 ms |
6900 KB |
Output is correct |
10 |
Correct |
782 ms |
8504 KB |
Output is correct |
11 |
Correct |
746 ms |
8484 KB |
Output is correct |
12 |
Correct |
934 ms |
7448 KB |
Output is correct |
13 |
Correct |
810 ms |
7720 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
670 ms |
7796 KB |
Output is correct |
2 |
Correct |
424 ms |
7200 KB |
Output is correct |
3 |
Correct |
731 ms |
8268 KB |
Output is correct |
4 |
Correct |
705 ms |
7964 KB |
Output is correct |
5 |
Correct |
77 ms |
6736 KB |
Output is correct |
6 |
Correct |
682 ms |
8020 KB |
Output is correct |
7 |
Correct |
679 ms |
7760 KB |
Output is correct |
8 |
Correct |
634 ms |
7876 KB |
Output is correct |
9 |
Correct |
547 ms |
7580 KB |
Output is correct |
10 |
Correct |
531 ms |
7888 KB |
Output is correct |
11 |
Correct |
501 ms |
7768 KB |
Output is correct |
12 |
Correct |
494 ms |
8008 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
903 ms |
7564 KB |
Output is correct |
2 |
Correct |
78 ms |
6796 KB |
Output is correct |
3 |
Correct |
88 ms |
6944 KB |
Output is correct |
4 |
Correct |
65 ms |
6956 KB |
Output is correct |
5 |
Correct |
764 ms |
7764 KB |
Output is correct |
6 |
Correct |
1065 ms |
7764 KB |
Output is correct |
7 |
Correct |
824 ms |
7560 KB |
Output is correct |
8 |
Correct |
513 ms |
7456 KB |
Output is correct |
9 |
Correct |
510 ms |
7236 KB |
Output is correct |
10 |
Correct |
497 ms |
7372 KB |
Output is correct |
11 |
Correct |
823 ms |
7592 KB |
Output is correct |
12 |
Correct |
784 ms |
7460 KB |
Output is correct |
13 |
Correct |
780 ms |
7576 KB |
Output is correct |
14 |
Correct |
734 ms |
7804 KB |
Output is correct |
15 |
Correct |
711 ms |
7812 KB |
Output is correct |
16 |
Correct |
1014 ms |
7692 KB |
Output is correct |
17 |
Correct |
1014 ms |
7564 KB |
Output is correct |
18 |
Correct |
1016 ms |
7588 KB |
Output is correct |
19 |
Correct |
1028 ms |
7556 KB |
Output is correct |
20 |
Correct |
942 ms |
7748 KB |
Output is correct |
21 |
Correct |
890 ms |
7748 KB |
Output is correct |
22 |
Correct |
938 ms |
7784 KB |
Output is correct |
23 |
Correct |
759 ms |
7716 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1006 ms |
8408 KB |
Output is correct |
2 |
Correct |
1105 ms |
8868 KB |
Output is correct |
3 |
Correct |
966 ms |
8536 KB |
Output is correct |
4 |
Correct |
1040 ms |
8356 KB |
Output is correct |
5 |
Correct |
1032 ms |
8412 KB |
Output is correct |
6 |
Correct |
1337 ms |
7660 KB |
Output is correct |
7 |
Correct |
1152 ms |
7592 KB |
Output is correct |
8 |
Correct |
1159 ms |
7504 KB |
Output is correct |
9 |
Correct |
117 ms |
6900 KB |
Output is correct |
10 |
Correct |
782 ms |
8504 KB |
Output is correct |
11 |
Correct |
746 ms |
8484 KB |
Output is correct |
12 |
Correct |
934 ms |
7448 KB |
Output is correct |
13 |
Correct |
810 ms |
7720 KB |
Output is correct |
14 |
Correct |
670 ms |
7796 KB |
Output is correct |
15 |
Correct |
424 ms |
7200 KB |
Output is correct |
16 |
Correct |
731 ms |
8268 KB |
Output is correct |
17 |
Correct |
705 ms |
7964 KB |
Output is correct |
18 |
Correct |
77 ms |
6736 KB |
Output is correct |
19 |
Correct |
682 ms |
8020 KB |
Output is correct |
20 |
Correct |
679 ms |
7760 KB |
Output is correct |
21 |
Correct |
634 ms |
7876 KB |
Output is correct |
22 |
Correct |
547 ms |
7580 KB |
Output is correct |
23 |
Correct |
531 ms |
7888 KB |
Output is correct |
24 |
Correct |
501 ms |
7768 KB |
Output is correct |
25 |
Correct |
494 ms |
8008 KB |
Output is correct |
26 |
Correct |
977 ms |
8340 KB |
Output is correct |
27 |
Correct |
1165 ms |
8512 KB |
Output is correct |
28 |
Correct |
1043 ms |
8524 KB |
Output is correct |
29 |
Correct |
932 ms |
8536 KB |
Output is correct |
30 |
Correct |
1167 ms |
8496 KB |
Output is correct |
31 |
Correct |
1182 ms |
8328 KB |
Output is correct |
32 |
Correct |
1196 ms |
8744 KB |
Output is correct |
33 |
Correct |
1111 ms |
8692 KB |
Output is correct |
34 |
Correct |
1000 ms |
8544 KB |
Output is correct |
35 |
Correct |
1028 ms |
8480 KB |
Output is correct |
36 |
Correct |
960 ms |
8272 KB |
Output is correct |
37 |
Correct |
963 ms |
8416 KB |
Output is correct |
38 |
Correct |
913 ms |
8456 KB |
Output is correct |
39 |
Correct |
813 ms |
7672 KB |
Output is correct |
40 |
Correct |
856 ms |
7764 KB |
Output is correct |
41 |
Correct |
844 ms |
7732 KB |
Output is correct |
42 |
Correct |
722 ms |
8664 KB |
Output is correct |
43 |
Correct |
735 ms |
8432 KB |
Output is correct |
44 |
Correct |
714 ms |
8732 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
6492 KB |
Output is correct |
2 |
Correct |
2 ms |
6492 KB |
Output is correct |
3 |
Correct |
39 ms |
6596 KB |
Output is correct |
4 |
Correct |
10 ms |
6492 KB |
Output is correct |
5 |
Correct |
21 ms |
6564 KB |
Output is correct |
6 |
Correct |
20 ms |
6492 KB |
Output is correct |
7 |
Correct |
20 ms |
6584 KB |
Output is correct |
8 |
Correct |
20 ms |
6488 KB |
Output is correct |
9 |
Correct |
22 ms |
6492 KB |
Output is correct |
10 |
Correct |
21 ms |
6836 KB |
Output is correct |
11 |
Correct |
19 ms |
6492 KB |
Output is correct |
12 |
Correct |
19 ms |
6488 KB |
Output is correct |
13 |
Correct |
23 ms |
6588 KB |
Output is correct |
14 |
Correct |
22 ms |
6560 KB |
Output is correct |
15 |
Correct |
22 ms |
6492 KB |
Output is correct |
16 |
Correct |
21 ms |
6488 KB |
Output is correct |
17 |
Correct |
20 ms |
6552 KB |
Output is correct |
18 |
Correct |
1006 ms |
8408 KB |
Output is correct |
19 |
Correct |
1105 ms |
8868 KB |
Output is correct |
20 |
Correct |
966 ms |
8536 KB |
Output is correct |
21 |
Correct |
1040 ms |
8356 KB |
Output is correct |
22 |
Correct |
1032 ms |
8412 KB |
Output is correct |
23 |
Correct |
1337 ms |
7660 KB |
Output is correct |
24 |
Correct |
1152 ms |
7592 KB |
Output is correct |
25 |
Correct |
1159 ms |
7504 KB |
Output is correct |
26 |
Correct |
117 ms |
6900 KB |
Output is correct |
27 |
Correct |
782 ms |
8504 KB |
Output is correct |
28 |
Correct |
746 ms |
8484 KB |
Output is correct |
29 |
Correct |
934 ms |
7448 KB |
Output is correct |
30 |
Correct |
810 ms |
7720 KB |
Output is correct |
31 |
Correct |
670 ms |
7796 KB |
Output is correct |
32 |
Correct |
424 ms |
7200 KB |
Output is correct |
33 |
Correct |
731 ms |
8268 KB |
Output is correct |
34 |
Correct |
705 ms |
7964 KB |
Output is correct |
35 |
Correct |
77 ms |
6736 KB |
Output is correct |
36 |
Correct |
682 ms |
8020 KB |
Output is correct |
37 |
Correct |
679 ms |
7760 KB |
Output is correct |
38 |
Correct |
634 ms |
7876 KB |
Output is correct |
39 |
Correct |
547 ms |
7580 KB |
Output is correct |
40 |
Correct |
531 ms |
7888 KB |
Output is correct |
41 |
Correct |
501 ms |
7768 KB |
Output is correct |
42 |
Correct |
494 ms |
8008 KB |
Output is correct |
43 |
Correct |
903 ms |
7564 KB |
Output is correct |
44 |
Correct |
78 ms |
6796 KB |
Output is correct |
45 |
Correct |
88 ms |
6944 KB |
Output is correct |
46 |
Correct |
65 ms |
6956 KB |
Output is correct |
47 |
Correct |
764 ms |
7764 KB |
Output is correct |
48 |
Correct |
1065 ms |
7764 KB |
Output is correct |
49 |
Correct |
824 ms |
7560 KB |
Output is correct |
50 |
Correct |
513 ms |
7456 KB |
Output is correct |
51 |
Correct |
510 ms |
7236 KB |
Output is correct |
52 |
Correct |
497 ms |
7372 KB |
Output is correct |
53 |
Correct |
823 ms |
7592 KB |
Output is correct |
54 |
Correct |
784 ms |
7460 KB |
Output is correct |
55 |
Correct |
780 ms |
7576 KB |
Output is correct |
56 |
Correct |
734 ms |
7804 KB |
Output is correct |
57 |
Correct |
711 ms |
7812 KB |
Output is correct |
58 |
Correct |
1014 ms |
7692 KB |
Output is correct |
59 |
Correct |
1014 ms |
7564 KB |
Output is correct |
60 |
Correct |
1016 ms |
7588 KB |
Output is correct |
61 |
Correct |
1028 ms |
7556 KB |
Output is correct |
62 |
Correct |
942 ms |
7748 KB |
Output is correct |
63 |
Correct |
890 ms |
7748 KB |
Output is correct |
64 |
Correct |
938 ms |
7784 KB |
Output is correct |
65 |
Correct |
759 ms |
7716 KB |
Output is correct |
66 |
Correct |
977 ms |
8340 KB |
Output is correct |
67 |
Correct |
1165 ms |
8512 KB |
Output is correct |
68 |
Correct |
1043 ms |
8524 KB |
Output is correct |
69 |
Correct |
932 ms |
8536 KB |
Output is correct |
70 |
Correct |
1167 ms |
8496 KB |
Output is correct |
71 |
Correct |
1182 ms |
8328 KB |
Output is correct |
72 |
Correct |
1196 ms |
8744 KB |
Output is correct |
73 |
Correct |
1111 ms |
8692 KB |
Output is correct |
74 |
Correct |
1000 ms |
8544 KB |
Output is correct |
75 |
Correct |
1028 ms |
8480 KB |
Output is correct |
76 |
Correct |
960 ms |
8272 KB |
Output is correct |
77 |
Correct |
963 ms |
8416 KB |
Output is correct |
78 |
Correct |
913 ms |
8456 KB |
Output is correct |
79 |
Correct |
813 ms |
7672 KB |
Output is correct |
80 |
Correct |
856 ms |
7764 KB |
Output is correct |
81 |
Correct |
844 ms |
7732 KB |
Output is correct |
82 |
Correct |
722 ms |
8664 KB |
Output is correct |
83 |
Correct |
735 ms |
8432 KB |
Output is correct |
84 |
Correct |
714 ms |
8732 KB |
Output is correct |
85 |
Correct |
1805 ms |
8396 KB |
Output is correct |
86 |
Correct |
168 ms |
8796 KB |
Output is correct |
87 |
Correct |
86 ms |
8792 KB |
Output is correct |
88 |
Correct |
1063 ms |
10888 KB |
Output is correct |
89 |
Correct |
1929 ms |
12232 KB |
Output is correct |
90 |
Correct |
1028 ms |
10580 KB |
Output is correct |
91 |
Correct |
974 ms |
11136 KB |
Output is correct |
92 |
Correct |
988 ms |
11248 KB |
Output is correct |
93 |
Correct |
1069 ms |
10764 KB |
Output is correct |
94 |
Correct |
1503 ms |
11824 KB |
Output is correct |
95 |
Correct |
1576 ms |
11844 KB |
Output is correct |
96 |
Correct |
1556 ms |
10908 KB |
Output is correct |
97 |
Correct |
945 ms |
10024 KB |
Output is correct |
98 |
Correct |
885 ms |
10544 KB |
Output is correct |
99 |
Correct |
1997 ms |
12108 KB |
Output is correct |
100 |
Correct |
1874 ms |
12260 KB |
Output is correct |
101 |
Correct |
1907 ms |
12368 KB |
Output is correct |
102 |
Correct |
1903 ms |
12304 KB |
Output is correct |
103 |
Correct |
1658 ms |
11092 KB |
Output is correct |
104 |
Correct |
1688 ms |
10900 KB |
Output is correct |
105 |
Correct |
1369 ms |
10944 KB |
Output is correct |
106 |
Correct |
1188 ms |
11440 KB |
Output is correct |
107 |
Correct |
1445 ms |
10872 KB |
Output is correct |
108 |
Correct |
1734 ms |
11508 KB |
Output is correct |
109 |
Correct |
1060 ms |
9708 KB |
Output is correct |