#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define ss(x) (int) x.size()
#define pb push_back
#define ll long long
#define cat(x) cerr << #x << " = " << x << endl
#define FOR(i, n) for(int i = 0; i < n; ++i)
using namespace std;
const int nax = 1e5 + 111;
const int M = 400;
int n, m, q;
struct edge {
int a, b, c;
};
edge e[nax];
struct gao {
int l, r, a, b, c;
gao () {}
gao (int l, int r, int a, int b, int c) : l(l), r(r), a(a), b(b), c(c) {}
};
vector <gao> v;
int p[nax];
int t[nax][3];
int ans[nax];
struct uf {
int p[nax];
int ile[nax];
void init() {
for(int i = 1; i <= n; ++i) {
p[i] = i;
ile[i] = 1;
}
}
int find(int x) {
if(x == p[x])
return x;
return p[x] = find(p[x]);
}
void unia(int x, int y) {
x = find(x);
y = find(y);
if(x != y) {
p[x] = y;
ile[y] += ile[x];
}
}
} ja;
struct qu {
int v, w, id;
};
vector <gao> big;
vector <gao> small;
vector <qu> qq;
vector <int> graf[nax];
vector <int> nodes;
bool odw[nax];
void dfs(int u) {
nodes.pb(u);
odw[u] = 1;
for(auto it : graf[u])
if(!odw[it])
dfs(it);
}
void add(int a, int b) {
graf[a].pb(b);
graf[b].pb(a);
}
void del(int a, int b) {
graf[a].pop_back();
graf[b].pop_back();
}
void solve(int L, int R) {
ja.init();
qq.clear();
small.clear();
for(auto it : v)
if(!(it.r < L || R < it.l) && !(it.l <= L && R <= it.r))
small.pb(it);
for(int i = L; i <= R; ++i)
if(t[i][0] == 2)
qq.pb({t[i][1], t[i][2], i});
sort(qq.begin(), qq.end(), [](qu x, qu y) {
return x.w < y.w;
});
int j = ss(big) - 1;
for(int i = ss(qq) - 1; 0 <= i; --i) {
qu on = qq[i];
while(0 <= j && on.w <= big[j].c) {
if(big[j].l <= L && R <= big[j].r)
ja.unia(ja.find(big[j].a), ja.find(big[j].b));
j--;
}
for(auto it : small)
if(it.l <= on.id && on.id <= it.r && on.w <= it.c)
add(ja.find(it.a), ja.find(it.b));
nodes.clear();
dfs(ja.find(on.v));
for(auto it : nodes) {
odw[it] = 0;
ans[on.id] += ja.ile[it];
}
for(auto it : small)
if(it.l <= on.id && on.id <= it.r && on.w <= it.c)
del(ja.find(it.a), ja.find(it.b));
}
}
int main() {
scanf("%d %d", &n, &m);
for(int i = 1; i <= m; ++i) {
scanf("%d %d %d", &e[i].a, &e[i].b, &e[i].c);
}
scanf("%d", &q);
for(int i = 1; i <= q; ++i) {
scanf("%d %d %d", &t[i][0], &t[i][1], &t[i][2]);
if(t[i][0] == 1) {
v.pb(gao(p[t[i][1]], i - 1, e[t[i][1]].a, e[t[i][1]].b, e[t[i][1]].c));
p[t[i][1]] = i;
e[t[i][1]].c = t[i][2];
}
}
for(int i = 1; i <= m; ++i)
v.pb(gao(p[i], q, e[i].a, e[i].b, e[i].c));
big = v;
sort(big.begin(), big.end(), [](gao x, gao y) {
return x.c < y.c;
});
for(int i = 1; i <= q; i += M)
solve(i, min(q, i + M - 1));
for(int i = 1; i <= q; ++i)
if(t[i][0] == 2)
printf("%d\n", ans[i]);
return 0;
}
Compilation message
bridges.cpp: In function 'int main()':
bridges.cpp:136: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:138:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d", &e[i].a, &e[i].b, &e[i].c);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:140:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &q);
~~~~~^~~~~~~~~~
bridges.cpp:142:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d", &t[i][0], &t[i][1], &t[i][2]);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
2680 KB |
Output is correct |
2 |
Correct |
4 ms |
2680 KB |
Output is correct |
3 |
Correct |
37 ms |
3420 KB |
Output is correct |
4 |
Correct |
8 ms |
3064 KB |
Output is correct |
5 |
Correct |
27 ms |
3288 KB |
Output is correct |
6 |
Correct |
24 ms |
3288 KB |
Output is correct |
7 |
Correct |
27 ms |
3288 KB |
Output is correct |
8 |
Correct |
26 ms |
3288 KB |
Output is correct |
9 |
Correct |
30 ms |
3160 KB |
Output is correct |
10 |
Correct |
26 ms |
3192 KB |
Output is correct |
11 |
Correct |
25 ms |
3288 KB |
Output is correct |
12 |
Correct |
26 ms |
3416 KB |
Output is correct |
13 |
Correct |
32 ms |
3192 KB |
Output is correct |
14 |
Correct |
30 ms |
3276 KB |
Output is correct |
15 |
Correct |
29 ms |
3288 KB |
Output is correct |
16 |
Correct |
26 ms |
3192 KB |
Output is correct |
17 |
Correct |
26 ms |
3160 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1230 ms |
11208 KB |
Output is correct |
2 |
Correct |
1210 ms |
10932 KB |
Output is correct |
3 |
Correct |
1176 ms |
11068 KB |
Output is correct |
4 |
Correct |
1170 ms |
10932 KB |
Output is correct |
5 |
Correct |
1158 ms |
11084 KB |
Output is correct |
6 |
Correct |
1490 ms |
10912 KB |
Output is correct |
7 |
Correct |
1407 ms |
10968 KB |
Output is correct |
8 |
Correct |
1353 ms |
11036 KB |
Output is correct |
9 |
Correct |
51 ms |
4728 KB |
Output is correct |
10 |
Correct |
1199 ms |
11060 KB |
Output is correct |
11 |
Correct |
1171 ms |
11104 KB |
Output is correct |
12 |
Correct |
722 ms |
8984 KB |
Output is correct |
13 |
Correct |
1146 ms |
12640 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1174 ms |
11944 KB |
Output is correct |
2 |
Correct |
796 ms |
9692 KB |
Output is correct |
3 |
Correct |
1376 ms |
14116 KB |
Output is correct |
4 |
Correct |
1260 ms |
16820 KB |
Output is correct |
5 |
Correct |
51 ms |
4600 KB |
Output is correct |
6 |
Correct |
1359 ms |
15224 KB |
Output is correct |
7 |
Correct |
1203 ms |
15076 KB |
Output is correct |
8 |
Correct |
1107 ms |
13104 KB |
Output is correct |
9 |
Correct |
757 ms |
9124 KB |
Output is correct |
10 |
Correct |
725 ms |
8856 KB |
Output is correct |
11 |
Correct |
1126 ms |
16256 KB |
Output is correct |
12 |
Correct |
1033 ms |
14180 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1680 ms |
10692 KB |
Output is correct |
2 |
Correct |
50 ms |
4728 KB |
Output is correct |
3 |
Correct |
82 ms |
8420 KB |
Output is correct |
4 |
Correct |
71 ms |
8392 KB |
Output is correct |
5 |
Correct |
1640 ms |
10644 KB |
Output is correct |
6 |
Correct |
1653 ms |
10728 KB |
Output is correct |
7 |
Correct |
1680 ms |
10816 KB |
Output is correct |
8 |
Correct |
598 ms |
7916 KB |
Output is correct |
9 |
Correct |
598 ms |
7852 KB |
Output is correct |
10 |
Correct |
596 ms |
8196 KB |
Output is correct |
11 |
Correct |
1027 ms |
9440 KB |
Output is correct |
12 |
Correct |
1012 ms |
9264 KB |
Output is correct |
13 |
Correct |
1031 ms |
9424 KB |
Output is correct |
14 |
Correct |
1690 ms |
10840 KB |
Output is correct |
15 |
Correct |
1665 ms |
10876 KB |
Output is correct |
16 |
Correct |
1794 ms |
10768 KB |
Output is correct |
17 |
Correct |
1768 ms |
10780 KB |
Output is correct |
18 |
Correct |
1672 ms |
10644 KB |
Output is correct |
19 |
Correct |
1636 ms |
10696 KB |
Output is correct |
20 |
Correct |
1197 ms |
9988 KB |
Output is correct |
21 |
Correct |
1237 ms |
9996 KB |
Output is correct |
22 |
Correct |
1698 ms |
10788 KB |
Output is correct |
23 |
Correct |
1219 ms |
9960 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1230 ms |
11208 KB |
Output is correct |
2 |
Correct |
1210 ms |
10932 KB |
Output is correct |
3 |
Correct |
1176 ms |
11068 KB |
Output is correct |
4 |
Correct |
1170 ms |
10932 KB |
Output is correct |
5 |
Correct |
1158 ms |
11084 KB |
Output is correct |
6 |
Correct |
1490 ms |
10912 KB |
Output is correct |
7 |
Correct |
1407 ms |
10968 KB |
Output is correct |
8 |
Correct |
1353 ms |
11036 KB |
Output is correct |
9 |
Correct |
51 ms |
4728 KB |
Output is correct |
10 |
Correct |
1199 ms |
11060 KB |
Output is correct |
11 |
Correct |
1171 ms |
11104 KB |
Output is correct |
12 |
Correct |
722 ms |
8984 KB |
Output is correct |
13 |
Correct |
1146 ms |
12640 KB |
Output is correct |
14 |
Correct |
1174 ms |
11944 KB |
Output is correct |
15 |
Correct |
796 ms |
9692 KB |
Output is correct |
16 |
Correct |
1376 ms |
14116 KB |
Output is correct |
17 |
Correct |
1260 ms |
16820 KB |
Output is correct |
18 |
Correct |
51 ms |
4600 KB |
Output is correct |
19 |
Correct |
1359 ms |
15224 KB |
Output is correct |
20 |
Correct |
1203 ms |
15076 KB |
Output is correct |
21 |
Correct |
1107 ms |
13104 KB |
Output is correct |
22 |
Correct |
757 ms |
9124 KB |
Output is correct |
23 |
Correct |
725 ms |
8856 KB |
Output is correct |
24 |
Correct |
1126 ms |
16256 KB |
Output is correct |
25 |
Correct |
1033 ms |
14180 KB |
Output is correct |
26 |
Correct |
1718 ms |
14276 KB |
Output is correct |
27 |
Correct |
1873 ms |
12752 KB |
Output is correct |
28 |
Correct |
1814 ms |
15452 KB |
Output is correct |
29 |
Correct |
1385 ms |
12512 KB |
Output is correct |
30 |
Correct |
1738 ms |
11232 KB |
Output is correct |
31 |
Correct |
1699 ms |
11308 KB |
Output is correct |
32 |
Correct |
1767 ms |
11204 KB |
Output is correct |
33 |
Correct |
1498 ms |
10976 KB |
Output is correct |
34 |
Correct |
1533 ms |
11308 KB |
Output is correct |
35 |
Correct |
1608 ms |
11124 KB |
Output is correct |
36 |
Correct |
1289 ms |
11164 KB |
Output is correct |
37 |
Correct |
1272 ms |
11104 KB |
Output is correct |
38 |
Correct |
1281 ms |
11108 KB |
Output is correct |
39 |
Correct |
893 ms |
8996 KB |
Output is correct |
40 |
Correct |
872 ms |
8936 KB |
Output is correct |
41 |
Correct |
866 ms |
9000 KB |
Output is correct |
42 |
Correct |
1193 ms |
12864 KB |
Output is correct |
43 |
Correct |
1197 ms |
12648 KB |
Output is correct |
44 |
Correct |
1183 ms |
12772 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
2680 KB |
Output is correct |
2 |
Correct |
4 ms |
2680 KB |
Output is correct |
3 |
Correct |
37 ms |
3420 KB |
Output is correct |
4 |
Correct |
8 ms |
3064 KB |
Output is correct |
5 |
Correct |
27 ms |
3288 KB |
Output is correct |
6 |
Correct |
24 ms |
3288 KB |
Output is correct |
7 |
Correct |
27 ms |
3288 KB |
Output is correct |
8 |
Correct |
26 ms |
3288 KB |
Output is correct |
9 |
Correct |
30 ms |
3160 KB |
Output is correct |
10 |
Correct |
26 ms |
3192 KB |
Output is correct |
11 |
Correct |
25 ms |
3288 KB |
Output is correct |
12 |
Correct |
26 ms |
3416 KB |
Output is correct |
13 |
Correct |
32 ms |
3192 KB |
Output is correct |
14 |
Correct |
30 ms |
3276 KB |
Output is correct |
15 |
Correct |
29 ms |
3288 KB |
Output is correct |
16 |
Correct |
26 ms |
3192 KB |
Output is correct |
17 |
Correct |
26 ms |
3160 KB |
Output is correct |
18 |
Correct |
1230 ms |
11208 KB |
Output is correct |
19 |
Correct |
1210 ms |
10932 KB |
Output is correct |
20 |
Correct |
1176 ms |
11068 KB |
Output is correct |
21 |
Correct |
1170 ms |
10932 KB |
Output is correct |
22 |
Correct |
1158 ms |
11084 KB |
Output is correct |
23 |
Correct |
1490 ms |
10912 KB |
Output is correct |
24 |
Correct |
1407 ms |
10968 KB |
Output is correct |
25 |
Correct |
1353 ms |
11036 KB |
Output is correct |
26 |
Correct |
51 ms |
4728 KB |
Output is correct |
27 |
Correct |
1199 ms |
11060 KB |
Output is correct |
28 |
Correct |
1171 ms |
11104 KB |
Output is correct |
29 |
Correct |
722 ms |
8984 KB |
Output is correct |
30 |
Correct |
1146 ms |
12640 KB |
Output is correct |
31 |
Correct |
1174 ms |
11944 KB |
Output is correct |
32 |
Correct |
796 ms |
9692 KB |
Output is correct |
33 |
Correct |
1376 ms |
14116 KB |
Output is correct |
34 |
Correct |
1260 ms |
16820 KB |
Output is correct |
35 |
Correct |
51 ms |
4600 KB |
Output is correct |
36 |
Correct |
1359 ms |
15224 KB |
Output is correct |
37 |
Correct |
1203 ms |
15076 KB |
Output is correct |
38 |
Correct |
1107 ms |
13104 KB |
Output is correct |
39 |
Correct |
757 ms |
9124 KB |
Output is correct |
40 |
Correct |
725 ms |
8856 KB |
Output is correct |
41 |
Correct |
1126 ms |
16256 KB |
Output is correct |
42 |
Correct |
1033 ms |
14180 KB |
Output is correct |
43 |
Correct |
1680 ms |
10692 KB |
Output is correct |
44 |
Correct |
50 ms |
4728 KB |
Output is correct |
45 |
Correct |
82 ms |
8420 KB |
Output is correct |
46 |
Correct |
71 ms |
8392 KB |
Output is correct |
47 |
Correct |
1640 ms |
10644 KB |
Output is correct |
48 |
Correct |
1653 ms |
10728 KB |
Output is correct |
49 |
Correct |
1680 ms |
10816 KB |
Output is correct |
50 |
Correct |
598 ms |
7916 KB |
Output is correct |
51 |
Correct |
598 ms |
7852 KB |
Output is correct |
52 |
Correct |
596 ms |
8196 KB |
Output is correct |
53 |
Correct |
1027 ms |
9440 KB |
Output is correct |
54 |
Correct |
1012 ms |
9264 KB |
Output is correct |
55 |
Correct |
1031 ms |
9424 KB |
Output is correct |
56 |
Correct |
1690 ms |
10840 KB |
Output is correct |
57 |
Correct |
1665 ms |
10876 KB |
Output is correct |
58 |
Correct |
1794 ms |
10768 KB |
Output is correct |
59 |
Correct |
1768 ms |
10780 KB |
Output is correct |
60 |
Correct |
1672 ms |
10644 KB |
Output is correct |
61 |
Correct |
1636 ms |
10696 KB |
Output is correct |
62 |
Correct |
1197 ms |
9988 KB |
Output is correct |
63 |
Correct |
1237 ms |
9996 KB |
Output is correct |
64 |
Correct |
1698 ms |
10788 KB |
Output is correct |
65 |
Correct |
1219 ms |
9960 KB |
Output is correct |
66 |
Correct |
1718 ms |
14276 KB |
Output is correct |
67 |
Correct |
1873 ms |
12752 KB |
Output is correct |
68 |
Correct |
1814 ms |
15452 KB |
Output is correct |
69 |
Correct |
1385 ms |
12512 KB |
Output is correct |
70 |
Correct |
1738 ms |
11232 KB |
Output is correct |
71 |
Correct |
1699 ms |
11308 KB |
Output is correct |
72 |
Correct |
1767 ms |
11204 KB |
Output is correct |
73 |
Correct |
1498 ms |
10976 KB |
Output is correct |
74 |
Correct |
1533 ms |
11308 KB |
Output is correct |
75 |
Correct |
1608 ms |
11124 KB |
Output is correct |
76 |
Correct |
1289 ms |
11164 KB |
Output is correct |
77 |
Correct |
1272 ms |
11104 KB |
Output is correct |
78 |
Correct |
1281 ms |
11108 KB |
Output is correct |
79 |
Correct |
893 ms |
8996 KB |
Output is correct |
80 |
Correct |
872 ms |
8936 KB |
Output is correct |
81 |
Correct |
866 ms |
9000 KB |
Output is correct |
82 |
Correct |
1193 ms |
12864 KB |
Output is correct |
83 |
Correct |
1197 ms |
12648 KB |
Output is correct |
84 |
Correct |
1183 ms |
12772 KB |
Output is correct |
85 |
Correct |
2585 ms |
22172 KB |
Output is correct |
86 |
Correct |
114 ms |
10648 KB |
Output is correct |
87 |
Correct |
110 ms |
10652 KB |
Output is correct |
88 |
Correct |
2314 ms |
15872 KB |
Output is correct |
89 |
Correct |
2487 ms |
26088 KB |
Output is correct |
90 |
Correct |
2316 ms |
15180 KB |
Output is correct |
91 |
Correct |
1413 ms |
13500 KB |
Output is correct |
92 |
Correct |
1384 ms |
13816 KB |
Output is correct |
93 |
Correct |
1582 ms |
12856 KB |
Output is correct |
94 |
Correct |
1816 ms |
15732 KB |
Output is correct |
95 |
Correct |
1810 ms |
16068 KB |
Output is correct |
96 |
Correct |
1791 ms |
14688 KB |
Output is correct |
97 |
Correct |
1822 ms |
13308 KB |
Output is correct |
98 |
Correct |
2310 ms |
16752 KB |
Output is correct |
99 |
Correct |
2598 ms |
25144 KB |
Output is correct |
100 |
Correct |
2556 ms |
25608 KB |
Output is correct |
101 |
Correct |
2543 ms |
22880 KB |
Output is correct |
102 |
Correct |
2523 ms |
22876 KB |
Output is correct |
103 |
Correct |
2007 ms |
15020 KB |
Output is correct |
104 |
Correct |
1912 ms |
15048 KB |
Output is correct |
105 |
Correct |
1935 ms |
16500 KB |
Output is correct |
106 |
Correct |
1723 ms |
16220 KB |
Output is correct |
107 |
Correct |
1457 ms |
13624 KB |
Output is correct |
108 |
Correct |
2554 ms |
21052 KB |
Output is correct |
109 |
Correct |
2009 ms |
13668 KB |
Output is correct |