#include<bits/stdc++.h>
using namespace std;
#define app push_back
const int N = 1e5 + 7, K = 600;
struct Edge {
int u, v, c;
};
struct Quer {
int t, i, c;
bool operator < (Quer p) {
return c > p.c;
}
};
struct Seg {
int l, r, i, c;
bool operator < (Seg p) {
return c > p.c;
}
};
int n, m, q;
int par[N], cnt[N];
void init() {
for (int i = 1; i <= n; ++i) {
par[i] = i; cnt[i] = 1;
}
}
int root(int u) {
if (u == par[u]) return u;
else return par[u] = root(par[u]);
}
void merge(int u, int v) {
u = root(u); v = root(v);
if (u == v) return;
if (cnt[v] < cnt[u]) swap(u, v);
par[u] = v; cnt[v] += cnt[u];
}
Edge ed[N];
Quer d[N];
int lf[N], w[N];
vector <Seg> v;
int ans[N];
bool upd[N];
vector <int> g[N];
bool comp(int i, int j) {
return d[i].c > d[j].c;
}
bool used[N];
vector <int> vis;
int dfs(int u) {
int ans = cnt[u];
used[u] = 1;
vis.app(u);
for (int v : g[u]) {
if (!used[v]) {
ans += dfs(v);
}
}
return ans;
}
void solve(int L, int R) {
memset(upd, 0, sizeof upd);
vector <int> q;
for (int i = L; i <= R; ++i) {
if (d[i].t == 1) {
upd[d[i].i] = 1;
}
else {
q.app(i);
}
}
sort(q.begin(), q.end(), comp);
int ptr = 0;
vector <Seg> t;
init();
for (int i : q) {
while (ptr < v.size() && v[ptr].c >= d[i].c) {
if (R < v[ptr].l || v[ptr].r < L) {
}
else if (v[ptr].l <= L && R <= v[ptr].r) {
int e = v[ptr].i;
merge(ed[e].u, ed[e].v);
}
else {
t.app(v[ptr]);
}
++ptr;
}
for (auto s : t) {
if (s.l <= i && i <= s.r) {
int u = root(ed[s.i].u), v = root(ed[s.i].v);
g[u].app(v); g[v].app(u);
}
}
ans[i] = dfs(root(d[i].i));
for (int e : vis) used[e] = 0;
vis.clear();
for (auto s : t) {
if (s.l <= i && i <= s.r) {
int u = root(ed[s.i].u), v = root(ed[s.i].v);
g[u].clear(); g[v].clear();
}
}
}
}
signed main() {
#ifdef HOME
freopen("input.txt", "r", stdin);
#else
ios_base::sync_with_stdio(0); cin.tie(0);
#endif
cin >> n >> m;
for (int i = 0; i < m; ++i) {
cin >> ed[i].u >> ed[i].v >> ed[i].c;
w[i] = ed[i].c;
}
cin >> q;
for (int i = 0; i < q; ++i) {
cin >> d[i].t >> d[i].i >> d[i].c;
if (d[i].t == 1) {
--d[i].i;
v.app({lf[d[i].i], i - 1, d[i].i, w[d[i].i]});
lf[d[i].i] = i;
w[d[i].i] = d[i].c;
}
}
for (int i = 0; i < m; ++i) {
v.app({lf[i], q - 1, i, w[i]});
}
sort(v.begin(), v.end());
for (int a = 0; ; ++a) {
int L = a * K;
int R = min(L + K - 1, q - 1);
if (R < L) break;
solve(L, R);
}
for (int i = 0; i < q; ++i) {
if (d[i].t == 2) cout << ans[i] << '\n';
}
}
Compilation message
bridges.cpp: In function 'void solve(int, int)':
bridges.cpp:76:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (ptr < v.size() && v[ptr].c >= d[i].c) {
~~~~^~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
2808 KB |
Output is correct |
2 |
Correct |
5 ms |
2808 KB |
Output is correct |
3 |
Correct |
47 ms |
3448 KB |
Output is correct |
4 |
Correct |
9 ms |
3064 KB |
Output is correct |
5 |
Correct |
33 ms |
3320 KB |
Output is correct |
6 |
Correct |
26 ms |
3320 KB |
Output is correct |
7 |
Correct |
31 ms |
3320 KB |
Output is correct |
8 |
Correct |
29 ms |
3320 KB |
Output is correct |
9 |
Correct |
39 ms |
3252 KB |
Output is correct |
10 |
Correct |
29 ms |
3320 KB |
Output is correct |
11 |
Correct |
28 ms |
3320 KB |
Output is correct |
12 |
Correct |
34 ms |
3320 KB |
Output is correct |
13 |
Correct |
38 ms |
3324 KB |
Output is correct |
14 |
Correct |
34 ms |
3364 KB |
Output is correct |
15 |
Correct |
34 ms |
3448 KB |
Output is correct |
16 |
Correct |
31 ms |
3320 KB |
Output is correct |
17 |
Correct |
30 ms |
3320 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1485 ms |
9636 KB |
Output is correct |
2 |
Correct |
1443 ms |
9648 KB |
Output is correct |
3 |
Correct |
1416 ms |
9704 KB |
Output is correct |
4 |
Correct |
1386 ms |
9732 KB |
Output is correct |
5 |
Correct |
1393 ms |
9688 KB |
Output is correct |
6 |
Correct |
2405 ms |
8812 KB |
Output is correct |
7 |
Correct |
2215 ms |
8968 KB |
Output is correct |
8 |
Correct |
2132 ms |
8988 KB |
Output is correct |
9 |
Correct |
50 ms |
5368 KB |
Output is correct |
10 |
Correct |
1586 ms |
9556 KB |
Output is correct |
11 |
Correct |
1461 ms |
9704 KB |
Output is correct |
12 |
Correct |
930 ms |
8300 KB |
Output is correct |
13 |
Correct |
1314 ms |
9960 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1248 ms |
8752 KB |
Output is correct |
2 |
Correct |
1108 ms |
6972 KB |
Output is correct |
3 |
Correct |
1563 ms |
8788 KB |
Output is correct |
4 |
Correct |
1249 ms |
8644 KB |
Output is correct |
5 |
Correct |
51 ms |
5368 KB |
Output is correct |
6 |
Correct |
1428 ms |
8616 KB |
Output is correct |
7 |
Correct |
1119 ms |
8792 KB |
Output is correct |
8 |
Correct |
919 ms |
8808 KB |
Output is correct |
9 |
Correct |
630 ms |
7500 KB |
Output is correct |
10 |
Correct |
545 ms |
7660 KB |
Output is correct |
11 |
Correct |
955 ms |
9064 KB |
Output is correct |
12 |
Correct |
798 ms |
9184 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1022 ms |
9320 KB |
Output is correct |
2 |
Correct |
50 ms |
5368 KB |
Output is correct |
3 |
Correct |
110 ms |
7404 KB |
Output is correct |
4 |
Correct |
68 ms |
7016 KB |
Output is correct |
5 |
Correct |
797 ms |
9676 KB |
Output is correct |
6 |
Correct |
1038 ms |
9504 KB |
Output is correct |
7 |
Correct |
825 ms |
9424 KB |
Output is correct |
8 |
Correct |
557 ms |
7772 KB |
Output is correct |
9 |
Correct |
546 ms |
7540 KB |
Output is correct |
10 |
Correct |
560 ms |
7796 KB |
Output is correct |
11 |
Correct |
970 ms |
8460 KB |
Output is correct |
12 |
Correct |
909 ms |
8436 KB |
Output is correct |
13 |
Correct |
943 ms |
8712 KB |
Output is correct |
14 |
Correct |
687 ms |
9484 KB |
Output is correct |
15 |
Correct |
737 ms |
9324 KB |
Output is correct |
16 |
Correct |
1168 ms |
9448 KB |
Output is correct |
17 |
Correct |
1136 ms |
9348 KB |
Output is correct |
18 |
Correct |
1098 ms |
9364 KB |
Output is correct |
19 |
Correct |
1136 ms |
9516 KB |
Output is correct |
20 |
Correct |
1051 ms |
8940 KB |
Output is correct |
21 |
Correct |
1074 ms |
8904 KB |
Output is correct |
22 |
Correct |
1095 ms |
9436 KB |
Output is correct |
23 |
Correct |
931 ms |
8920 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1485 ms |
9636 KB |
Output is correct |
2 |
Correct |
1443 ms |
9648 KB |
Output is correct |
3 |
Correct |
1416 ms |
9704 KB |
Output is correct |
4 |
Correct |
1386 ms |
9732 KB |
Output is correct |
5 |
Correct |
1393 ms |
9688 KB |
Output is correct |
6 |
Correct |
2405 ms |
8812 KB |
Output is correct |
7 |
Correct |
2215 ms |
8968 KB |
Output is correct |
8 |
Correct |
2132 ms |
8988 KB |
Output is correct |
9 |
Correct |
50 ms |
5368 KB |
Output is correct |
10 |
Correct |
1586 ms |
9556 KB |
Output is correct |
11 |
Correct |
1461 ms |
9704 KB |
Output is correct |
12 |
Correct |
930 ms |
8300 KB |
Output is correct |
13 |
Correct |
1314 ms |
9960 KB |
Output is correct |
14 |
Correct |
1248 ms |
8752 KB |
Output is correct |
15 |
Correct |
1108 ms |
6972 KB |
Output is correct |
16 |
Correct |
1563 ms |
8788 KB |
Output is correct |
17 |
Correct |
1249 ms |
8644 KB |
Output is correct |
18 |
Correct |
51 ms |
5368 KB |
Output is correct |
19 |
Correct |
1428 ms |
8616 KB |
Output is correct |
20 |
Correct |
1119 ms |
8792 KB |
Output is correct |
21 |
Correct |
919 ms |
8808 KB |
Output is correct |
22 |
Correct |
630 ms |
7500 KB |
Output is correct |
23 |
Correct |
545 ms |
7660 KB |
Output is correct |
24 |
Correct |
955 ms |
9064 KB |
Output is correct |
25 |
Correct |
798 ms |
9184 KB |
Output is correct |
26 |
Correct |
1581 ms |
9720 KB |
Output is correct |
27 |
Correct |
1963 ms |
9784 KB |
Output is correct |
28 |
Correct |
1561 ms |
9668 KB |
Output is correct |
29 |
Correct |
1020 ms |
9576 KB |
Output is correct |
30 |
Correct |
1879 ms |
9540 KB |
Output is correct |
31 |
Correct |
1983 ms |
9780 KB |
Output is correct |
32 |
Correct |
1925 ms |
9848 KB |
Output is correct |
33 |
Correct |
1571 ms |
9704 KB |
Output is correct |
34 |
Correct |
1568 ms |
9744 KB |
Output is correct |
35 |
Correct |
1598 ms |
9712 KB |
Output is correct |
36 |
Correct |
1109 ms |
9672 KB |
Output is correct |
37 |
Correct |
1090 ms |
9576 KB |
Output is correct |
38 |
Correct |
1098 ms |
9656 KB |
Output is correct |
39 |
Correct |
713 ms |
8432 KB |
Output is correct |
40 |
Correct |
698 ms |
8496 KB |
Output is correct |
41 |
Correct |
709 ms |
8252 KB |
Output is correct |
42 |
Correct |
926 ms |
10408 KB |
Output is correct |
43 |
Correct |
916 ms |
10336 KB |
Output is correct |
44 |
Correct |
921 ms |
10408 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
2808 KB |
Output is correct |
2 |
Correct |
5 ms |
2808 KB |
Output is correct |
3 |
Correct |
47 ms |
3448 KB |
Output is correct |
4 |
Correct |
9 ms |
3064 KB |
Output is correct |
5 |
Correct |
33 ms |
3320 KB |
Output is correct |
6 |
Correct |
26 ms |
3320 KB |
Output is correct |
7 |
Correct |
31 ms |
3320 KB |
Output is correct |
8 |
Correct |
29 ms |
3320 KB |
Output is correct |
9 |
Correct |
39 ms |
3252 KB |
Output is correct |
10 |
Correct |
29 ms |
3320 KB |
Output is correct |
11 |
Correct |
28 ms |
3320 KB |
Output is correct |
12 |
Correct |
34 ms |
3320 KB |
Output is correct |
13 |
Correct |
38 ms |
3324 KB |
Output is correct |
14 |
Correct |
34 ms |
3364 KB |
Output is correct |
15 |
Correct |
34 ms |
3448 KB |
Output is correct |
16 |
Correct |
31 ms |
3320 KB |
Output is correct |
17 |
Correct |
30 ms |
3320 KB |
Output is correct |
18 |
Correct |
1485 ms |
9636 KB |
Output is correct |
19 |
Correct |
1443 ms |
9648 KB |
Output is correct |
20 |
Correct |
1416 ms |
9704 KB |
Output is correct |
21 |
Correct |
1386 ms |
9732 KB |
Output is correct |
22 |
Correct |
1393 ms |
9688 KB |
Output is correct |
23 |
Correct |
2405 ms |
8812 KB |
Output is correct |
24 |
Correct |
2215 ms |
8968 KB |
Output is correct |
25 |
Correct |
2132 ms |
8988 KB |
Output is correct |
26 |
Correct |
50 ms |
5368 KB |
Output is correct |
27 |
Correct |
1586 ms |
9556 KB |
Output is correct |
28 |
Correct |
1461 ms |
9704 KB |
Output is correct |
29 |
Correct |
930 ms |
8300 KB |
Output is correct |
30 |
Correct |
1314 ms |
9960 KB |
Output is correct |
31 |
Correct |
1248 ms |
8752 KB |
Output is correct |
32 |
Correct |
1108 ms |
6972 KB |
Output is correct |
33 |
Correct |
1563 ms |
8788 KB |
Output is correct |
34 |
Correct |
1249 ms |
8644 KB |
Output is correct |
35 |
Correct |
51 ms |
5368 KB |
Output is correct |
36 |
Correct |
1428 ms |
8616 KB |
Output is correct |
37 |
Correct |
1119 ms |
8792 KB |
Output is correct |
38 |
Correct |
919 ms |
8808 KB |
Output is correct |
39 |
Correct |
630 ms |
7500 KB |
Output is correct |
40 |
Correct |
545 ms |
7660 KB |
Output is correct |
41 |
Correct |
955 ms |
9064 KB |
Output is correct |
42 |
Correct |
798 ms |
9184 KB |
Output is correct |
43 |
Correct |
1022 ms |
9320 KB |
Output is correct |
44 |
Correct |
50 ms |
5368 KB |
Output is correct |
45 |
Correct |
110 ms |
7404 KB |
Output is correct |
46 |
Correct |
68 ms |
7016 KB |
Output is correct |
47 |
Correct |
797 ms |
9676 KB |
Output is correct |
48 |
Correct |
1038 ms |
9504 KB |
Output is correct |
49 |
Correct |
825 ms |
9424 KB |
Output is correct |
50 |
Correct |
557 ms |
7772 KB |
Output is correct |
51 |
Correct |
546 ms |
7540 KB |
Output is correct |
52 |
Correct |
560 ms |
7796 KB |
Output is correct |
53 |
Correct |
970 ms |
8460 KB |
Output is correct |
54 |
Correct |
909 ms |
8436 KB |
Output is correct |
55 |
Correct |
943 ms |
8712 KB |
Output is correct |
56 |
Correct |
687 ms |
9484 KB |
Output is correct |
57 |
Correct |
737 ms |
9324 KB |
Output is correct |
58 |
Correct |
1168 ms |
9448 KB |
Output is correct |
59 |
Correct |
1136 ms |
9348 KB |
Output is correct |
60 |
Correct |
1098 ms |
9364 KB |
Output is correct |
61 |
Correct |
1136 ms |
9516 KB |
Output is correct |
62 |
Correct |
1051 ms |
8940 KB |
Output is correct |
63 |
Correct |
1074 ms |
8904 KB |
Output is correct |
64 |
Correct |
1095 ms |
9436 KB |
Output is correct |
65 |
Correct |
931 ms |
8920 KB |
Output is correct |
66 |
Correct |
1581 ms |
9720 KB |
Output is correct |
67 |
Correct |
1963 ms |
9784 KB |
Output is correct |
68 |
Correct |
1561 ms |
9668 KB |
Output is correct |
69 |
Correct |
1020 ms |
9576 KB |
Output is correct |
70 |
Correct |
1879 ms |
9540 KB |
Output is correct |
71 |
Correct |
1983 ms |
9780 KB |
Output is correct |
72 |
Correct |
1925 ms |
9848 KB |
Output is correct |
73 |
Correct |
1571 ms |
9704 KB |
Output is correct |
74 |
Correct |
1568 ms |
9744 KB |
Output is correct |
75 |
Correct |
1598 ms |
9712 KB |
Output is correct |
76 |
Correct |
1109 ms |
9672 KB |
Output is correct |
77 |
Correct |
1090 ms |
9576 KB |
Output is correct |
78 |
Correct |
1098 ms |
9656 KB |
Output is correct |
79 |
Correct |
713 ms |
8432 KB |
Output is correct |
80 |
Correct |
698 ms |
8496 KB |
Output is correct |
81 |
Correct |
709 ms |
8252 KB |
Output is correct |
82 |
Correct |
926 ms |
10408 KB |
Output is correct |
83 |
Correct |
916 ms |
10336 KB |
Output is correct |
84 |
Correct |
921 ms |
10408 KB |
Output is correct |
85 |
Correct |
1916 ms |
11336 KB |
Output is correct |
86 |
Correct |
161 ms |
7276 KB |
Output is correct |
87 |
Correct |
158 ms |
7688 KB |
Output is correct |
88 |
Correct |
1741 ms |
11048 KB |
Output is correct |
89 |
Correct |
1923 ms |
11064 KB |
Output is correct |
90 |
Correct |
1787 ms |
10744 KB |
Output is correct |
91 |
Correct |
1570 ms |
9704 KB |
Output is correct |
92 |
Correct |
1522 ms |
9668 KB |
Output is correct |
93 |
Correct |
2209 ms |
9156 KB |
Output is correct |
94 |
Correct |
1820 ms |
10616 KB |
Output is correct |
95 |
Correct |
1848 ms |
10516 KB |
Output is correct |
96 |
Correct |
2298 ms |
9752 KB |
Output is correct |
97 |
Correct |
1036 ms |
9724 KB |
Output is correct |
98 |
Correct |
1368 ms |
11620 KB |
Output is correct |
99 |
Correct |
2047 ms |
11300 KB |
Output is correct |
100 |
Correct |
2024 ms |
11368 KB |
Output is correct |
101 |
Correct |
2072 ms |
10900 KB |
Output is correct |
102 |
Correct |
2035 ms |
11056 KB |
Output is correct |
103 |
Correct |
2403 ms |
10348 KB |
Output is correct |
104 |
Correct |
2370 ms |
10344 KB |
Output is correct |
105 |
Correct |
1732 ms |
10552 KB |
Output is correct |
106 |
Correct |
1417 ms |
10616 KB |
Output is correct |
107 |
Correct |
1369 ms |
9192 KB |
Output is correct |
108 |
Correct |
2293 ms |
10480 KB |
Output is correct |
109 |
Correct |
2133 ms |
9484 KB |
Output is correct |