//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
#define mem(a,v) memset((a), (v), sizeof (a))
#define enl printf("\n")
#define case(t) printf("Case #%d: ", (t))
#define ni(n) scanf("%d", &(n))
#define nl(n) scanf("%I64d", &(n))
#define nai(a, n) for (int i = 0; i < (n); i++) ni(a[i])
#define nal(a, n) for (int i = 0; i < (n); i++) nl(a[i])
#define pri(n) printf("%d\n", (n))
#define prl(n) printf("%I64d\n", (n))
#define pii pair<int, int>
#define pil pair<int, long long>
#define pll pair<long long, long long>
#define vii vector<pii>
#define vil vector<pil>
#define vll vector<pll>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef cc_hash_table<int,int,hash<int>> ht;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> oset;
const double pi = acos(-1);
const int MOD = 1e9 + 7;
const int INF = 1e9 + 7;
const int MAXN = 5e4 + 5;
const int BLOCK = 500;
const double eps = 1e-9;
int n, m, q, vis[MAXN];
int par[MAXN], sz[MAXN], ans[2*MAXN];
int U[2*MAXN], V[2*MAXN], W[2*MAXN], st[2*MAXN];
vector<array<int,4>> arr;
vector<array<int,3>> qry;
vi adj[MAXN];
int qryD(int x) { return par[x] == x ? x : par[x] = qryD(par[x]); }
void join(int u, int v) {
u = qryD(u), v = qryD(v);
if (u == v) return;
if (sz[u] > sz[v]) swap(u,v);
par[u] = v;
sz[v] += sz[u];
}
int cnt = 0;
void dfs(int u, int& ret) {
vis[u] = cnt;
ret += sz[u];
for (int v: adj[u])
if (vis[v] != cnt)
dfs(v, ret);
}
void solve(int lo, int hi) {
for (int i = 0; i <= n; i++) par[i] = i, sz[i] = 1;
vector<array<int,3>> cur, nx;
while (!qry.empty() && qry.back()[1] <= hi) {
cur.pb(qry.back()); qry.pop_back();
}
sort(cur.begin(),cur.end());
int ind = 0;
while (!cur.empty()) {
int w, i, s; w = cur.back()[0], i = cur.back()[1], s = cur.back()[2];
cur.pop_back();
for (; ind < arr.size() && w <= arr[ind][0]; ind++) {
if (hi < arr[ind][2] || arr[ind][3] < lo) continue;
if (arr[ind][2] <= lo && hi <= arr[ind][3])
join(U[arr[ind][1]], V[arr[ind][1]]);
else
nx.pb({arr[ind][1], arr[ind][2], arr[ind][3]});
}
cnt++;
vi tmp;
for (auto it: nx) {
if (it[1] <= i && i <= it[2]) {
adj[qryD(U[it[0]])].pb(qryD(V[it[0]]));
adj[qryD(V[it[0]])].pb(qryD(U[it[0]]));
tmp.pb(qryD(U[it[0]]));
tmp.pb(qryD(V[it[0]]));
}
}
ans[i] = 0;
dfs(qryD(s), ans[i]);
for (int j: tmp)
adj[j].clear();
}
}
int main() {
mem(ans,-1);
scanf("%d %d", &n, &m);
for (int i = 0; i < m; i++) scanf("%d %d %d", &U[i], &V[i], &W[i]);
scanf("%d", &q);
for (int i = 0; i < q; i++) {
int t, b, r; scanf("%d %d %d", &t, &b, &r);
if (t == 1) {
b--;
arr.pb({W[b], b, st[b], i});
W[b] = r, st[b] = i+1;
} else {
qry.pb({r, i, b});
}
}
for (int i = 0; i < m; i++)
arr.pb({W[i], i, st[i], q-1});
sort(arr.rbegin(), arr.rend());
reverse(qry.begin(), qry.end());
for (int i = 0; i < q; i += BLOCK) solve(i, min(q,i+BLOCK)-1);
for (int i = 0; i < q; i++)
if (~ans[i])
printf("%d\n", ans[i]);
return 0;
}
Compilation message
bridges.cpp: In function 'void solve(int, int)':
bridges.cpp:76:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (; ind < arr.size() && w <= arr[ind][0]; ind++) {
~~~~^~~~~~~~~~~~
bridges.cpp: In function 'int main()':
bridges.cpp:102:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &n, &m);
~~~~~^~~~~~~~~~~~~~~~~
bridges.cpp:103:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for (int i = 0; i < m; i++) scanf("%d %d %d", &U[i], &V[i], &W[i]);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:104:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &q);
~~~~~^~~~~~~~~~
bridges.cpp:106:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int t, b, r; scanf("%d %d %d", &t, &b, &r);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
2040 KB |
Output is correct |
2 |
Correct |
3 ms |
1912 KB |
Output is correct |
3 |
Correct |
45 ms |
2424 KB |
Output is correct |
4 |
Correct |
9 ms |
2500 KB |
Output is correct |
5 |
Correct |
30 ms |
2424 KB |
Output is correct |
6 |
Correct |
25 ms |
2300 KB |
Output is correct |
7 |
Correct |
27 ms |
2204 KB |
Output is correct |
8 |
Correct |
26 ms |
2296 KB |
Output is correct |
9 |
Correct |
36 ms |
2424 KB |
Output is correct |
10 |
Correct |
27 ms |
2428 KB |
Output is correct |
11 |
Correct |
26 ms |
2296 KB |
Output is correct |
12 |
Correct |
31 ms |
2296 KB |
Output is correct |
13 |
Correct |
34 ms |
2424 KB |
Output is correct |
14 |
Correct |
31 ms |
2424 KB |
Output is correct |
15 |
Correct |
30 ms |
2444 KB |
Output is correct |
16 |
Correct |
30 ms |
2296 KB |
Output is correct |
17 |
Correct |
29 ms |
2296 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1411 ms |
9696 KB |
Output is correct |
2 |
Correct |
1362 ms |
9384 KB |
Output is correct |
3 |
Correct |
1364 ms |
9372 KB |
Output is correct |
4 |
Correct |
1337 ms |
9892 KB |
Output is correct |
5 |
Correct |
1341 ms |
9880 KB |
Output is correct |
6 |
Correct |
1968 ms |
8608 KB |
Output is correct |
7 |
Correct |
1875 ms |
8608 KB |
Output is correct |
8 |
Correct |
1840 ms |
8636 KB |
Output is correct |
9 |
Correct |
53 ms |
4788 KB |
Output is correct |
10 |
Correct |
1186 ms |
8504 KB |
Output is correct |
11 |
Correct |
1118 ms |
8540 KB |
Output is correct |
12 |
Correct |
945 ms |
9204 KB |
Output is correct |
13 |
Correct |
1237 ms |
9828 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1167 ms |
8360 KB |
Output is correct |
2 |
Correct |
911 ms |
5816 KB |
Output is correct |
3 |
Correct |
1364 ms |
8036 KB |
Output is correct |
4 |
Correct |
1176 ms |
8424 KB |
Output is correct |
5 |
Correct |
53 ms |
4716 KB |
Output is correct |
6 |
Correct |
1262 ms |
8024 KB |
Output is correct |
7 |
Correct |
1039 ms |
8236 KB |
Output is correct |
8 |
Correct |
909 ms |
8276 KB |
Output is correct |
9 |
Correct |
664 ms |
8136 KB |
Output is correct |
10 |
Correct |
604 ms |
8040 KB |
Output is correct |
11 |
Correct |
898 ms |
8348 KB |
Output is correct |
12 |
Correct |
812 ms |
8376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1242 ms |
11700 KB |
Output is correct |
2 |
Correct |
53 ms |
4716 KB |
Output is correct |
3 |
Correct |
124 ms |
7340 KB |
Output is correct |
4 |
Correct |
76 ms |
7340 KB |
Output is correct |
5 |
Correct |
811 ms |
10256 KB |
Output is correct |
6 |
Correct |
1252 ms |
11744 KB |
Output is correct |
7 |
Correct |
820 ms |
10152 KB |
Output is correct |
8 |
Correct |
668 ms |
8936 KB |
Output is correct |
9 |
Correct |
645 ms |
9184 KB |
Output is correct |
10 |
Correct |
646 ms |
9032 KB |
Output is correct |
11 |
Correct |
1179 ms |
10344 KB |
Output is correct |
12 |
Correct |
1087 ms |
10476 KB |
Output is correct |
13 |
Correct |
1124 ms |
10336 KB |
Output is correct |
14 |
Correct |
759 ms |
10508 KB |
Output is correct |
15 |
Correct |
770 ms |
10336 KB |
Output is correct |
16 |
Correct |
1363 ms |
11576 KB |
Output is correct |
17 |
Correct |
1403 ms |
11616 KB |
Output is correct |
18 |
Correct |
1351 ms |
11752 KB |
Output is correct |
19 |
Correct |
1358 ms |
11700 KB |
Output is correct |
20 |
Correct |
1244 ms |
10752 KB |
Output is correct |
21 |
Correct |
1283 ms |
10868 KB |
Output is correct |
22 |
Correct |
1320 ms |
11436 KB |
Output is correct |
23 |
Correct |
1038 ms |
9492 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1411 ms |
9696 KB |
Output is correct |
2 |
Correct |
1362 ms |
9384 KB |
Output is correct |
3 |
Correct |
1364 ms |
9372 KB |
Output is correct |
4 |
Correct |
1337 ms |
9892 KB |
Output is correct |
5 |
Correct |
1341 ms |
9880 KB |
Output is correct |
6 |
Correct |
1968 ms |
8608 KB |
Output is correct |
7 |
Correct |
1875 ms |
8608 KB |
Output is correct |
8 |
Correct |
1840 ms |
8636 KB |
Output is correct |
9 |
Correct |
53 ms |
4788 KB |
Output is correct |
10 |
Correct |
1186 ms |
8504 KB |
Output is correct |
11 |
Correct |
1118 ms |
8540 KB |
Output is correct |
12 |
Correct |
945 ms |
9204 KB |
Output is correct |
13 |
Correct |
1237 ms |
9828 KB |
Output is correct |
14 |
Correct |
1167 ms |
8360 KB |
Output is correct |
15 |
Correct |
911 ms |
5816 KB |
Output is correct |
16 |
Correct |
1364 ms |
8036 KB |
Output is correct |
17 |
Correct |
1176 ms |
8424 KB |
Output is correct |
18 |
Correct |
53 ms |
4716 KB |
Output is correct |
19 |
Correct |
1262 ms |
8024 KB |
Output is correct |
20 |
Correct |
1039 ms |
8236 KB |
Output is correct |
21 |
Correct |
909 ms |
8276 KB |
Output is correct |
22 |
Correct |
664 ms |
8136 KB |
Output is correct |
23 |
Correct |
604 ms |
8040 KB |
Output is correct |
24 |
Correct |
898 ms |
8348 KB |
Output is correct |
25 |
Correct |
812 ms |
8376 KB |
Output is correct |
26 |
Correct |
1511 ms |
9980 KB |
Output is correct |
27 |
Correct |
1737 ms |
9556 KB |
Output is correct |
28 |
Correct |
1518 ms |
9796 KB |
Output is correct |
29 |
Correct |
1100 ms |
9748 KB |
Output is correct |
30 |
Correct |
1773 ms |
9644 KB |
Output is correct |
31 |
Correct |
1781 ms |
9684 KB |
Output is correct |
32 |
Correct |
1744 ms |
9804 KB |
Output is correct |
33 |
Correct |
1514 ms |
9804 KB |
Output is correct |
34 |
Correct |
1540 ms |
9732 KB |
Output is correct |
35 |
Correct |
1538 ms |
9876 KB |
Output is correct |
36 |
Correct |
1174 ms |
9728 KB |
Output is correct |
37 |
Correct |
1165 ms |
9776 KB |
Output is correct |
38 |
Correct |
1110 ms |
9608 KB |
Output is correct |
39 |
Correct |
807 ms |
9352 KB |
Output is correct |
40 |
Correct |
816 ms |
9256 KB |
Output is correct |
41 |
Correct |
807 ms |
9224 KB |
Output is correct |
42 |
Correct |
994 ms |
9976 KB |
Output is correct |
43 |
Correct |
1008 ms |
9864 KB |
Output is correct |
44 |
Correct |
984 ms |
9948 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
2040 KB |
Output is correct |
2 |
Correct |
3 ms |
1912 KB |
Output is correct |
3 |
Correct |
45 ms |
2424 KB |
Output is correct |
4 |
Correct |
9 ms |
2500 KB |
Output is correct |
5 |
Correct |
30 ms |
2424 KB |
Output is correct |
6 |
Correct |
25 ms |
2300 KB |
Output is correct |
7 |
Correct |
27 ms |
2204 KB |
Output is correct |
8 |
Correct |
26 ms |
2296 KB |
Output is correct |
9 |
Correct |
36 ms |
2424 KB |
Output is correct |
10 |
Correct |
27 ms |
2428 KB |
Output is correct |
11 |
Correct |
26 ms |
2296 KB |
Output is correct |
12 |
Correct |
31 ms |
2296 KB |
Output is correct |
13 |
Correct |
34 ms |
2424 KB |
Output is correct |
14 |
Correct |
31 ms |
2424 KB |
Output is correct |
15 |
Correct |
30 ms |
2444 KB |
Output is correct |
16 |
Correct |
30 ms |
2296 KB |
Output is correct |
17 |
Correct |
29 ms |
2296 KB |
Output is correct |
18 |
Correct |
1411 ms |
9696 KB |
Output is correct |
19 |
Correct |
1362 ms |
9384 KB |
Output is correct |
20 |
Correct |
1364 ms |
9372 KB |
Output is correct |
21 |
Correct |
1337 ms |
9892 KB |
Output is correct |
22 |
Correct |
1341 ms |
9880 KB |
Output is correct |
23 |
Correct |
1968 ms |
8608 KB |
Output is correct |
24 |
Correct |
1875 ms |
8608 KB |
Output is correct |
25 |
Correct |
1840 ms |
8636 KB |
Output is correct |
26 |
Correct |
53 ms |
4788 KB |
Output is correct |
27 |
Correct |
1186 ms |
8504 KB |
Output is correct |
28 |
Correct |
1118 ms |
8540 KB |
Output is correct |
29 |
Correct |
945 ms |
9204 KB |
Output is correct |
30 |
Correct |
1237 ms |
9828 KB |
Output is correct |
31 |
Correct |
1167 ms |
8360 KB |
Output is correct |
32 |
Correct |
911 ms |
5816 KB |
Output is correct |
33 |
Correct |
1364 ms |
8036 KB |
Output is correct |
34 |
Correct |
1176 ms |
8424 KB |
Output is correct |
35 |
Correct |
53 ms |
4716 KB |
Output is correct |
36 |
Correct |
1262 ms |
8024 KB |
Output is correct |
37 |
Correct |
1039 ms |
8236 KB |
Output is correct |
38 |
Correct |
909 ms |
8276 KB |
Output is correct |
39 |
Correct |
664 ms |
8136 KB |
Output is correct |
40 |
Correct |
604 ms |
8040 KB |
Output is correct |
41 |
Correct |
898 ms |
8348 KB |
Output is correct |
42 |
Correct |
812 ms |
8376 KB |
Output is correct |
43 |
Correct |
1242 ms |
11700 KB |
Output is correct |
44 |
Correct |
53 ms |
4716 KB |
Output is correct |
45 |
Correct |
124 ms |
7340 KB |
Output is correct |
46 |
Correct |
76 ms |
7340 KB |
Output is correct |
47 |
Correct |
811 ms |
10256 KB |
Output is correct |
48 |
Correct |
1252 ms |
11744 KB |
Output is correct |
49 |
Correct |
820 ms |
10152 KB |
Output is correct |
50 |
Correct |
668 ms |
8936 KB |
Output is correct |
51 |
Correct |
645 ms |
9184 KB |
Output is correct |
52 |
Correct |
646 ms |
9032 KB |
Output is correct |
53 |
Correct |
1179 ms |
10344 KB |
Output is correct |
54 |
Correct |
1087 ms |
10476 KB |
Output is correct |
55 |
Correct |
1124 ms |
10336 KB |
Output is correct |
56 |
Correct |
759 ms |
10508 KB |
Output is correct |
57 |
Correct |
770 ms |
10336 KB |
Output is correct |
58 |
Correct |
1363 ms |
11576 KB |
Output is correct |
59 |
Correct |
1403 ms |
11616 KB |
Output is correct |
60 |
Correct |
1351 ms |
11752 KB |
Output is correct |
61 |
Correct |
1358 ms |
11700 KB |
Output is correct |
62 |
Correct |
1244 ms |
10752 KB |
Output is correct |
63 |
Correct |
1283 ms |
10868 KB |
Output is correct |
64 |
Correct |
1320 ms |
11436 KB |
Output is correct |
65 |
Correct |
1038 ms |
9492 KB |
Output is correct |
66 |
Correct |
1511 ms |
9980 KB |
Output is correct |
67 |
Correct |
1737 ms |
9556 KB |
Output is correct |
68 |
Correct |
1518 ms |
9796 KB |
Output is correct |
69 |
Correct |
1100 ms |
9748 KB |
Output is correct |
70 |
Correct |
1773 ms |
9644 KB |
Output is correct |
71 |
Correct |
1781 ms |
9684 KB |
Output is correct |
72 |
Correct |
1744 ms |
9804 KB |
Output is correct |
73 |
Correct |
1514 ms |
9804 KB |
Output is correct |
74 |
Correct |
1540 ms |
9732 KB |
Output is correct |
75 |
Correct |
1538 ms |
9876 KB |
Output is correct |
76 |
Correct |
1174 ms |
9728 KB |
Output is correct |
77 |
Correct |
1165 ms |
9776 KB |
Output is correct |
78 |
Correct |
1110 ms |
9608 KB |
Output is correct |
79 |
Correct |
807 ms |
9352 KB |
Output is correct |
80 |
Correct |
816 ms |
9256 KB |
Output is correct |
81 |
Correct |
807 ms |
9224 KB |
Output is correct |
82 |
Correct |
994 ms |
9976 KB |
Output is correct |
83 |
Correct |
1008 ms |
9864 KB |
Output is correct |
84 |
Correct |
984 ms |
9948 KB |
Output is correct |
85 |
Correct |
2001 ms |
12408 KB |
Output is correct |
86 |
Correct |
170 ms |
7792 KB |
Output is correct |
87 |
Correct |
150 ms |
7660 KB |
Output is correct |
88 |
Correct |
1551 ms |
10660 KB |
Output is correct |
89 |
Correct |
1997 ms |
12224 KB |
Output is correct |
90 |
Correct |
1550 ms |
10484 KB |
Output is correct |
91 |
Correct |
1537 ms |
9812 KB |
Output is correct |
92 |
Correct |
1530 ms |
9920 KB |
Output is correct |
93 |
Correct |
1912 ms |
9020 KB |
Output is correct |
94 |
Correct |
1958 ms |
11080 KB |
Output is correct |
95 |
Correct |
1915 ms |
11236 KB |
Output is correct |
96 |
Correct |
2189 ms |
9912 KB |
Output is correct |
97 |
Correct |
1049 ms |
10404 KB |
Output is correct |
98 |
Correct |
1338 ms |
10316 KB |
Output is correct |
99 |
Correct |
2153 ms |
12128 KB |
Output is correct |
100 |
Correct |
2146 ms |
12300 KB |
Output is correct |
101 |
Correct |
2138 ms |
12252 KB |
Output is correct |
102 |
Correct |
2197 ms |
12268 KB |
Output is correct |
103 |
Correct |
2330 ms |
11368 KB |
Output is correct |
104 |
Correct |
2357 ms |
11368 KB |
Output is correct |
105 |
Correct |
1890 ms |
10884 KB |
Output is correct |
106 |
Correct |
1611 ms |
10456 KB |
Output is correct |
107 |
Correct |
1583 ms |
11084 KB |
Output is correct |
108 |
Correct |
2292 ms |
11648 KB |
Output is correct |
109 |
Correct |
1992 ms |
9092 KB |
Output is correct |