#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 = 600;
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;
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 |
3 ms |
6488 KB |
Output is correct |
2 |
Correct |
2 ms |
6492 KB |
Output is correct |
3 |
Correct |
43 ms |
6708 KB |
Output is correct |
4 |
Correct |
36 ms |
6696 KB |
Output is correct |
5 |
Correct |
216 ms |
6992 KB |
Output is correct |
6 |
Correct |
72 ms |
6868 KB |
Output is correct |
7 |
Correct |
343 ms |
7652 KB |
Output is correct |
8 |
Correct |
130 ms |
7124 KB |
Output is correct |
9 |
Correct |
412 ms |
8600 KB |
Output is correct |
10 |
Correct |
101 ms |
7172 KB |
Output is correct |
11 |
Correct |
98 ms |
6996 KB |
Output is correct |
12 |
Correct |
94 ms |
6868 KB |
Output is correct |
13 |
Correct |
251 ms |
7632 KB |
Output is correct |
14 |
Correct |
122 ms |
7204 KB |
Output is correct |
15 |
Correct |
111 ms |
7124 KB |
Output is correct |
16 |
Correct |
410 ms |
7680 KB |
Output is correct |
17 |
Correct |
286 ms |
7888 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2099 ms |
9008 KB |
Output is correct |
2 |
Correct |
2129 ms |
9016 KB |
Output is correct |
3 |
Correct |
2176 ms |
8752 KB |
Output is correct |
4 |
Execution timed out |
3040 ms |
9356 KB |
Time limit exceeded |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
3064 ms |
9628 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
3028 ms |
7880 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2099 ms |
9008 KB |
Output is correct |
2 |
Correct |
2129 ms |
9016 KB |
Output is correct |
3 |
Correct |
2176 ms |
8752 KB |
Output is correct |
4 |
Execution timed out |
3040 ms |
9356 KB |
Time limit exceeded |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
6488 KB |
Output is correct |
2 |
Correct |
2 ms |
6492 KB |
Output is correct |
3 |
Correct |
43 ms |
6708 KB |
Output is correct |
4 |
Correct |
36 ms |
6696 KB |
Output is correct |
5 |
Correct |
216 ms |
6992 KB |
Output is correct |
6 |
Correct |
72 ms |
6868 KB |
Output is correct |
7 |
Correct |
343 ms |
7652 KB |
Output is correct |
8 |
Correct |
130 ms |
7124 KB |
Output is correct |
9 |
Correct |
412 ms |
8600 KB |
Output is correct |
10 |
Correct |
101 ms |
7172 KB |
Output is correct |
11 |
Correct |
98 ms |
6996 KB |
Output is correct |
12 |
Correct |
94 ms |
6868 KB |
Output is correct |
13 |
Correct |
251 ms |
7632 KB |
Output is correct |
14 |
Correct |
122 ms |
7204 KB |
Output is correct |
15 |
Correct |
111 ms |
7124 KB |
Output is correct |
16 |
Correct |
410 ms |
7680 KB |
Output is correct |
17 |
Correct |
286 ms |
7888 KB |
Output is correct |
18 |
Correct |
2099 ms |
9008 KB |
Output is correct |
19 |
Correct |
2129 ms |
9016 KB |
Output is correct |
20 |
Correct |
2176 ms |
8752 KB |
Output is correct |
21 |
Execution timed out |
3040 ms |
9356 KB |
Time limit exceeded |
22 |
Halted |
0 ms |
0 KB |
- |