#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC target ("avx2")
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#pragma comment (linker, "/STACK: 16777216")
#define f first
#define s second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) ((int)(x).size())
#define pb push_back
#define mp make_pair
//#define int long long
using namespace std;
using namespace __gnu_pbds;
template <typename T> inline bool umax(T &a, const T &b) { if(a < b) { a = b; return 1; } return 0; }
template <typename T> inline bool umin(T &a, const T &b) { if(a > b) { a = b; return 1; } return 0; }
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
template <typename T> using oset = tree<T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;
const ll mod = 1e9 + 7;
const ll base = 1e6 + 5;
const ll inf = 2e18 + 1;
const int MAX = 5e4 + 5;
const int LG = 31;
random_device rd;
mt19937 gen(rd());
uniform_int_distribution<ll> dis(1, inf);
int n;
struct DSU {
vector<int> p, siz;
stack<array<int, 6>> roll;
DSU(): p(n + 1), siz(n + 1) {}
void create(int x) {
p[x] = x;
siz[x] = 1;
}
int get(int x) {
while(p[x] != x) x = p[x];
return x;
}
void unite(int x, int y, bool flag) {
x = get(x), y = get(y);
if(x != y) {
if(siz[x] < siz[y]) swap(x, y);
if(flag) roll.push({x, y, p[x], p[y], siz[x], siz[y]});
p[y] = x;
siz[x] += siz[y];
}
}
void roll_back() {
while(sz(roll)) {
auto [x, y, px, py, sx, sy] = roll.top(); roll.pop();
p[x] = px, p[y] = py, siz[x] = sx, siz[y] = sy;
}
}
};
void solve() {
int m;
cin >> n >> m;
vector<array<int, 4>> edge;
for(int i = 0; i < m; i++) {
int u, v, w;
cin >> u >> v >> w;
edge.pb({w, u, v, i});
}
const int buben = 1000;
vector<array<int, 3>> change;
auto rebuild = [&]() {
for(auto [w, idx, time] : change) {
assert(idx < m);
edge[idx][0] = w;
}
change.clear();
};
int q;
cin >> q;
for(int i = 0; i < q; i++) {
DSU dsu;
for(int j = 0; j <= n; j++) dsu.create(j);
vector<array<int, 3>> qr;
vector<int> used(m);
for(int j = i; j < min(q, i + buben); j++) {
int t;
cin >> t;
if(t == 1) {
int w, idx;
cin >> idx >> w; idx--;
change.pb({w, idx, j});
used[idx] = 1;
}
else {
int w, s;
cin >> s >> w;
qr.pb({w, s, j});
}
}
i = min(q, i + buben) - 1;
auto nedge = edge;
auto save = edge;
for(int j = 0; j < m; j++) {
if(used[j]) nedge[j][0] = 0;
}
sort(rall(nedge));
sort(rall(qr));
vector<pair<int, int>> ans;
int j = 0;
for(auto [w, v, time] : qr) {
while(j < m && nedge[j][0] >= w) {
dsu.unite(nedge[j][1], nedge[j][2], 0);
j++;
}
for(auto [wt, idx, tm] : change) {
if(tm > time) continue;
edge[idx][0] = wt;
}
for(auto [wt, idx, tm] : change) {
if(edge[idx][0] >= w) dsu.unite(edge[idx][1], edge[idx][2], 1);
}
for(auto [wt, idx, tm] : change) edge[idx][0] = save[idx][0];
ans.pb({time, dsu.siz[dsu.get(v)]});
dsu.roll_back();
}
sort(all(ans));
for(auto [idx, res] : ans) cout << res << '\n';
rebuild();
}
}
/*
3 4
1 2 5
2 3 2
3 1 4
2 3 8
2
2 1 5
1 4 1
*/
signed main() {
// freopen("skyline.in", "r", stdin); freopen("skyline.out", "w", stdout);
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int ttt = 1;
// cin >> ttt;
while(ttt--) {
solve();
}
return 0;
}
Compilation message
bridges.cpp:8: warning: ignoring '#pragma comment ' [-Wunknown-pragmas]
8 | #pragma comment (linker, "/STACK: 16777216")
|
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
33 ms |
588 KB |
Output is correct |
4 |
Correct |
5 ms |
468 KB |
Output is correct |
5 |
Correct |
36 ms |
536 KB |
Output is correct |
6 |
Correct |
27 ms |
536 KB |
Output is correct |
7 |
Correct |
32 ms |
468 KB |
Output is correct |
8 |
Correct |
43 ms |
516 KB |
Output is correct |
9 |
Correct |
37 ms |
436 KB |
Output is correct |
10 |
Correct |
40 ms |
536 KB |
Output is correct |
11 |
Correct |
41 ms |
536 KB |
Output is correct |
12 |
Correct |
46 ms |
520 KB |
Output is correct |
13 |
Correct |
45 ms |
536 KB |
Output is correct |
14 |
Correct |
43 ms |
544 KB |
Output is correct |
15 |
Correct |
45 ms |
468 KB |
Output is correct |
16 |
Correct |
39 ms |
452 KB |
Output is correct |
17 |
Correct |
40 ms |
460 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1403 ms |
5048 KB |
Output is correct |
2 |
Correct |
1430 ms |
5752 KB |
Output is correct |
3 |
Correct |
1436 ms |
5044 KB |
Output is correct |
4 |
Correct |
1449 ms |
5028 KB |
Output is correct |
5 |
Correct |
1435 ms |
5264 KB |
Output is correct |
6 |
Correct |
2025 ms |
5396 KB |
Output is correct |
7 |
Correct |
1983 ms |
5896 KB |
Output is correct |
8 |
Correct |
1987 ms |
5824 KB |
Output is correct |
9 |
Correct |
38 ms |
1868 KB |
Output is correct |
10 |
Correct |
1459 ms |
5140 KB |
Output is correct |
11 |
Correct |
1416 ms |
5068 KB |
Output is correct |
12 |
Correct |
1093 ms |
5440 KB |
Output is correct |
13 |
Correct |
1141 ms |
4896 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1121 ms |
4572 KB |
Output is correct |
2 |
Correct |
912 ms |
2628 KB |
Output is correct |
3 |
Correct |
1334 ms |
4060 KB |
Output is correct |
4 |
Correct |
1095 ms |
4048 KB |
Output is correct |
5 |
Correct |
37 ms |
1876 KB |
Output is correct |
6 |
Correct |
1286 ms |
4032 KB |
Output is correct |
7 |
Correct |
1042 ms |
4068 KB |
Output is correct |
8 |
Correct |
904 ms |
4012 KB |
Output is correct |
9 |
Correct |
669 ms |
4464 KB |
Output is correct |
10 |
Correct |
618 ms |
4260 KB |
Output is correct |
11 |
Correct |
723 ms |
3976 KB |
Output is correct |
12 |
Correct |
638 ms |
3832 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1449 ms |
8516 KB |
Output is correct |
2 |
Correct |
38 ms |
1812 KB |
Output is correct |
3 |
Correct |
169 ms |
7004 KB |
Output is correct |
4 |
Correct |
188 ms |
7068 KB |
Output is correct |
5 |
Correct |
1681 ms |
8216 KB |
Output is correct |
6 |
Correct |
1425 ms |
8696 KB |
Output is correct |
7 |
Correct |
1667 ms |
8468 KB |
Output is correct |
8 |
Correct |
690 ms |
5052 KB |
Output is correct |
9 |
Correct |
685 ms |
5088 KB |
Output is correct |
10 |
Correct |
707 ms |
5260 KB |
Output is correct |
11 |
Correct |
1087 ms |
6748 KB |
Output is correct |
12 |
Correct |
1057 ms |
6688 KB |
Output is correct |
13 |
Correct |
1107 ms |
6936 KB |
Output is correct |
14 |
Correct |
1674 ms |
8668 KB |
Output is correct |
15 |
Correct |
1651 ms |
8620 KB |
Output is correct |
16 |
Correct |
1434 ms |
8392 KB |
Output is correct |
17 |
Correct |
1488 ms |
8376 KB |
Output is correct |
18 |
Correct |
1446 ms |
8556 KB |
Output is correct |
19 |
Correct |
1440 ms |
8592 KB |
Output is correct |
20 |
Correct |
1225 ms |
7436 KB |
Output is correct |
21 |
Correct |
1207 ms |
7416 KB |
Output is correct |
22 |
Correct |
1397 ms |
8236 KB |
Output is correct |
23 |
Correct |
1378 ms |
7248 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1403 ms |
5048 KB |
Output is correct |
2 |
Correct |
1430 ms |
5752 KB |
Output is correct |
3 |
Correct |
1436 ms |
5044 KB |
Output is correct |
4 |
Correct |
1449 ms |
5028 KB |
Output is correct |
5 |
Correct |
1435 ms |
5264 KB |
Output is correct |
6 |
Correct |
2025 ms |
5396 KB |
Output is correct |
7 |
Correct |
1983 ms |
5896 KB |
Output is correct |
8 |
Correct |
1987 ms |
5824 KB |
Output is correct |
9 |
Correct |
38 ms |
1868 KB |
Output is correct |
10 |
Correct |
1459 ms |
5140 KB |
Output is correct |
11 |
Correct |
1416 ms |
5068 KB |
Output is correct |
12 |
Correct |
1093 ms |
5440 KB |
Output is correct |
13 |
Correct |
1141 ms |
4896 KB |
Output is correct |
14 |
Correct |
1121 ms |
4572 KB |
Output is correct |
15 |
Correct |
912 ms |
2628 KB |
Output is correct |
16 |
Correct |
1334 ms |
4060 KB |
Output is correct |
17 |
Correct |
1095 ms |
4048 KB |
Output is correct |
18 |
Correct |
37 ms |
1876 KB |
Output is correct |
19 |
Correct |
1286 ms |
4032 KB |
Output is correct |
20 |
Correct |
1042 ms |
4068 KB |
Output is correct |
21 |
Correct |
904 ms |
4012 KB |
Output is correct |
22 |
Correct |
669 ms |
4464 KB |
Output is correct |
23 |
Correct |
618 ms |
4260 KB |
Output is correct |
24 |
Correct |
723 ms |
3976 KB |
Output is correct |
25 |
Correct |
638 ms |
3832 KB |
Output is correct |
26 |
Correct |
1370 ms |
5216 KB |
Output is correct |
27 |
Correct |
1730 ms |
5064 KB |
Output is correct |
28 |
Correct |
1453 ms |
5132 KB |
Output is correct |
29 |
Correct |
1063 ms |
5400 KB |
Output is correct |
30 |
Correct |
1650 ms |
5260 KB |
Output is correct |
31 |
Correct |
1684 ms |
5252 KB |
Output is correct |
32 |
Correct |
1662 ms |
5108 KB |
Output is correct |
33 |
Correct |
1425 ms |
5732 KB |
Output is correct |
34 |
Correct |
1402 ms |
5112 KB |
Output is correct |
35 |
Correct |
1433 ms |
5080 KB |
Output is correct |
36 |
Correct |
1093 ms |
5064 KB |
Output is correct |
37 |
Correct |
1064 ms |
5948 KB |
Output is correct |
38 |
Correct |
1084 ms |
5108 KB |
Output is correct |
39 |
Correct |
817 ms |
5000 KB |
Output is correct |
40 |
Correct |
825 ms |
5084 KB |
Output is correct |
41 |
Correct |
814 ms |
5140 KB |
Output is correct |
42 |
Correct |
791 ms |
4852 KB |
Output is correct |
43 |
Correct |
785 ms |
4840 KB |
Output is correct |
44 |
Correct |
797 ms |
4824 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
33 ms |
588 KB |
Output is correct |
4 |
Correct |
5 ms |
468 KB |
Output is correct |
5 |
Correct |
36 ms |
536 KB |
Output is correct |
6 |
Correct |
27 ms |
536 KB |
Output is correct |
7 |
Correct |
32 ms |
468 KB |
Output is correct |
8 |
Correct |
43 ms |
516 KB |
Output is correct |
9 |
Correct |
37 ms |
436 KB |
Output is correct |
10 |
Correct |
40 ms |
536 KB |
Output is correct |
11 |
Correct |
41 ms |
536 KB |
Output is correct |
12 |
Correct |
46 ms |
520 KB |
Output is correct |
13 |
Correct |
45 ms |
536 KB |
Output is correct |
14 |
Correct |
43 ms |
544 KB |
Output is correct |
15 |
Correct |
45 ms |
468 KB |
Output is correct |
16 |
Correct |
39 ms |
452 KB |
Output is correct |
17 |
Correct |
40 ms |
460 KB |
Output is correct |
18 |
Correct |
1403 ms |
5048 KB |
Output is correct |
19 |
Correct |
1430 ms |
5752 KB |
Output is correct |
20 |
Correct |
1436 ms |
5044 KB |
Output is correct |
21 |
Correct |
1449 ms |
5028 KB |
Output is correct |
22 |
Correct |
1435 ms |
5264 KB |
Output is correct |
23 |
Correct |
2025 ms |
5396 KB |
Output is correct |
24 |
Correct |
1983 ms |
5896 KB |
Output is correct |
25 |
Correct |
1987 ms |
5824 KB |
Output is correct |
26 |
Correct |
38 ms |
1868 KB |
Output is correct |
27 |
Correct |
1459 ms |
5140 KB |
Output is correct |
28 |
Correct |
1416 ms |
5068 KB |
Output is correct |
29 |
Correct |
1093 ms |
5440 KB |
Output is correct |
30 |
Correct |
1141 ms |
4896 KB |
Output is correct |
31 |
Correct |
1121 ms |
4572 KB |
Output is correct |
32 |
Correct |
912 ms |
2628 KB |
Output is correct |
33 |
Correct |
1334 ms |
4060 KB |
Output is correct |
34 |
Correct |
1095 ms |
4048 KB |
Output is correct |
35 |
Correct |
37 ms |
1876 KB |
Output is correct |
36 |
Correct |
1286 ms |
4032 KB |
Output is correct |
37 |
Correct |
1042 ms |
4068 KB |
Output is correct |
38 |
Correct |
904 ms |
4012 KB |
Output is correct |
39 |
Correct |
669 ms |
4464 KB |
Output is correct |
40 |
Correct |
618 ms |
4260 KB |
Output is correct |
41 |
Correct |
723 ms |
3976 KB |
Output is correct |
42 |
Correct |
638 ms |
3832 KB |
Output is correct |
43 |
Correct |
1449 ms |
8516 KB |
Output is correct |
44 |
Correct |
38 ms |
1812 KB |
Output is correct |
45 |
Correct |
169 ms |
7004 KB |
Output is correct |
46 |
Correct |
188 ms |
7068 KB |
Output is correct |
47 |
Correct |
1681 ms |
8216 KB |
Output is correct |
48 |
Correct |
1425 ms |
8696 KB |
Output is correct |
49 |
Correct |
1667 ms |
8468 KB |
Output is correct |
50 |
Correct |
690 ms |
5052 KB |
Output is correct |
51 |
Correct |
685 ms |
5088 KB |
Output is correct |
52 |
Correct |
707 ms |
5260 KB |
Output is correct |
53 |
Correct |
1087 ms |
6748 KB |
Output is correct |
54 |
Correct |
1057 ms |
6688 KB |
Output is correct |
55 |
Correct |
1107 ms |
6936 KB |
Output is correct |
56 |
Correct |
1674 ms |
8668 KB |
Output is correct |
57 |
Correct |
1651 ms |
8620 KB |
Output is correct |
58 |
Correct |
1434 ms |
8392 KB |
Output is correct |
59 |
Correct |
1488 ms |
8376 KB |
Output is correct |
60 |
Correct |
1446 ms |
8556 KB |
Output is correct |
61 |
Correct |
1440 ms |
8592 KB |
Output is correct |
62 |
Correct |
1225 ms |
7436 KB |
Output is correct |
63 |
Correct |
1207 ms |
7416 KB |
Output is correct |
64 |
Correct |
1397 ms |
8236 KB |
Output is correct |
65 |
Correct |
1378 ms |
7248 KB |
Output is correct |
66 |
Correct |
1370 ms |
5216 KB |
Output is correct |
67 |
Correct |
1730 ms |
5064 KB |
Output is correct |
68 |
Correct |
1453 ms |
5132 KB |
Output is correct |
69 |
Correct |
1063 ms |
5400 KB |
Output is correct |
70 |
Correct |
1650 ms |
5260 KB |
Output is correct |
71 |
Correct |
1684 ms |
5252 KB |
Output is correct |
72 |
Correct |
1662 ms |
5108 KB |
Output is correct |
73 |
Correct |
1425 ms |
5732 KB |
Output is correct |
74 |
Correct |
1402 ms |
5112 KB |
Output is correct |
75 |
Correct |
1433 ms |
5080 KB |
Output is correct |
76 |
Correct |
1093 ms |
5064 KB |
Output is correct |
77 |
Correct |
1064 ms |
5948 KB |
Output is correct |
78 |
Correct |
1084 ms |
5108 KB |
Output is correct |
79 |
Correct |
817 ms |
5000 KB |
Output is correct |
80 |
Correct |
825 ms |
5084 KB |
Output is correct |
81 |
Correct |
814 ms |
5140 KB |
Output is correct |
82 |
Correct |
791 ms |
4852 KB |
Output is correct |
83 |
Correct |
785 ms |
4840 KB |
Output is correct |
84 |
Correct |
797 ms |
4824 KB |
Output is correct |
85 |
Correct |
1889 ms |
8100 KB |
Output is correct |
86 |
Correct |
188 ms |
6996 KB |
Output is correct |
87 |
Correct |
202 ms |
7032 KB |
Output is correct |
88 |
Correct |
2072 ms |
8200 KB |
Output is correct |
89 |
Correct |
1889 ms |
8464 KB |
Output is correct |
90 |
Correct |
2043 ms |
7976 KB |
Output is correct |
91 |
Correct |
1487 ms |
4940 KB |
Output is correct |
92 |
Correct |
1490 ms |
5228 KB |
Output is correct |
93 |
Correct |
2141 ms |
5344 KB |
Output is correct |
94 |
Correct |
1619 ms |
6620 KB |
Output is correct |
95 |
Correct |
1629 ms |
6344 KB |
Output is correct |
96 |
Correct |
1767 ms |
6716 KB |
Output is correct |
97 |
Correct |
1791 ms |
8240 KB |
Output is correct |
98 |
Correct |
1847 ms |
7392 KB |
Output is correct |
99 |
Correct |
1901 ms |
7904 KB |
Output is correct |
100 |
Correct |
1918 ms |
7944 KB |
Output is correct |
101 |
Correct |
1980 ms |
7656 KB |
Output is correct |
102 |
Correct |
1945 ms |
8148 KB |
Output is correct |
103 |
Correct |
1913 ms |
7268 KB |
Output is correct |
104 |
Correct |
1910 ms |
7000 KB |
Output is correct |
105 |
Correct |
1490 ms |
6844 KB |
Output is correct |
106 |
Correct |
1225 ms |
6396 KB |
Output is correct |
107 |
Correct |
1393 ms |
7176 KB |
Output is correct |
108 |
Correct |
1857 ms |
7744 KB |
Output is correct |
109 |
Correct |
1847 ms |
6784 KB |
Output is correct |