#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;
const int N = 1e5 + 5;
const int oo = 1e18 + 7, mod = 1e9 + 7;
int n, m, q;
const int S = 605;
vector<pair<int, ii>> queries[N];
vector<iii> edges;
int answer[N];
int sz[N], rt[N];
int root(int x){
return (x == rt[x] ? x : root(rt[x]));
}
stack<ii> stk;
int cnt = 0;
bool merge(int x, int y){
x = root(x), y = root(y);
if(x == y) return 0;
if(sz[x] < sz[y]) swap(x, y);
stk.push({x, sz[x]});
stk.push({y, sz[y]});
cnt += 2;
sz[x] += sz[y];
rt[y] = x;
return 1;
}
int lst[N];
void process(){
cin >> n >> m;
edges.pb({{-1, -1}, -1});
for(int i = 1; i <= m; i++){
int x, y, w;
cin >> x >> y >> w;
edges.pb({{x, y}, -w});
}
cin >> q;
for(int i = 1; i <= q; i++){
int type, a, b;
cin >> type >> a >> b;
queries[i / S + 1].pb({type, {a, -b}});
}
set<ii> ok;
for(int i = 1; i <= m; i++) ok.insert({edges[i].se, i});
int cnt_que = 0;
for(int i = 1; i <= 500; i++){
if(!queries[i].size()) break;
vector<iii> ask;
int cnt2 = cnt_que;
for(auto it : queries[i]){// erase the edges that are related to this block
cnt_que++;
if(it.fi == 1){
ok.erase({edges[it.se.fi].se, it.se.fi});
//edges[it.se.fi].se = it.se.fi;
}
else{
// {weight, node, ind}
ask.pb({{it.se.se, it.se.fi}, cnt_que});
}
}
for(int j = 1; j <= n; j++){
sz[j] = 1, rt[j] = j;
}
while(!stk.empty()) stk.pop();
cnt = 0;
sort(ask.begin(), ask.end());
//for(auto it : ok) cout << "OK " << it.fi << " " << it.se << "\n";
set<ii>::iterator it2 = ok.begin();
for(auto it : ask){
// cout << "ASK " << it.fi.fi << " " << it.fi.se << " " << it.se << "\n";
for(; it2 != ok.end(); it2++){
if((*it2).fi > it.fi.fi) break;
merge(edges[(*it2).se].fi.fi, edges[(*it2).se].fi.se);
}
cnt = 0;
int cnt3 = cnt2;
for(auto it2 : queries[i]) if(it2.fi == 1) lst[it2.se.fi] = edges[it2.se.fi].se;
for(auto it2 : queries[i]){
cnt3++;
if(cnt3 == it.se) break;
//if(it.fi == 2 && it.se)
if(it2.fi == 1) lst[it2.se.fi] = it2.se.se;
}
for(auto it2 : queries[i]) if(it2.fi == 1 && lst[it2.se.fi] <= it.fi.fi) merge(edges[it2.se.fi].fi.fi, edges[it2.se.fi].fi.se);
answer[it.se] = sz[root(it.fi.se)];
for(int i = 1; i <= cnt; i++){
assert(!stk.empty());
int u = stk.top().fi, s = stk.top().se;
rt[u] = u;
sz[u] = s;
stk.pop();
}
}
// at the end of the block, update everything
for(auto it : queries[i]) if(it.fi == 1) edges[it.se.fi].se = it.se.se;
for(auto it : queries[i]) if(it.fi == 1) ok.insert({edges[it.se.fi].se, it.se.fi});
}
for(int i = 1; i <= q; i++) if(answer[i]) cout << answer[i] << "\n";
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
process();
}
Compilation message
bridges.cpp:15:21: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
15 | const int oo = 1e18 + 7, mod = 1e9 + 7;
| ~~~~~^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2644 KB |
Output is correct |
2 |
Correct |
2 ms |
2644 KB |
Output is correct |
3 |
Correct |
34 ms |
2980 KB |
Output is correct |
4 |
Correct |
17 ms |
2932 KB |
Output is correct |
5 |
Correct |
37 ms |
2860 KB |
Output is correct |
6 |
Correct |
30 ms |
2844 KB |
Output is correct |
7 |
Correct |
35 ms |
2852 KB |
Output is correct |
8 |
Correct |
38 ms |
2868 KB |
Output is correct |
9 |
Correct |
38 ms |
2772 KB |
Output is correct |
10 |
Correct |
38 ms |
2856 KB |
Output is correct |
11 |
Correct |
40 ms |
2860 KB |
Output is correct |
12 |
Correct |
44 ms |
2772 KB |
Output is correct |
13 |
Correct |
43 ms |
2916 KB |
Output is correct |
14 |
Correct |
43 ms |
2900 KB |
Output is correct |
15 |
Correct |
45 ms |
2900 KB |
Output is correct |
16 |
Correct |
44 ms |
2856 KB |
Output is correct |
17 |
Correct |
41 ms |
2856 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1420 ms |
9188 KB |
Output is correct |
2 |
Correct |
1491 ms |
9460 KB |
Output is correct |
3 |
Correct |
1357 ms |
9508 KB |
Output is correct |
4 |
Correct |
1404 ms |
9352 KB |
Output is correct |
5 |
Correct |
1510 ms |
9272 KB |
Output is correct |
6 |
Correct |
1816 ms |
9748 KB |
Output is correct |
7 |
Correct |
1864 ms |
9676 KB |
Output is correct |
8 |
Correct |
1840 ms |
9348 KB |
Output is correct |
9 |
Correct |
153 ms |
4964 KB |
Output is correct |
10 |
Correct |
1145 ms |
9360 KB |
Output is correct |
11 |
Correct |
1252 ms |
9288 KB |
Output is correct |
12 |
Correct |
1343 ms |
9676 KB |
Output is correct |
13 |
Correct |
1308 ms |
9528 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1159 ms |
7896 KB |
Output is correct |
2 |
Correct |
807 ms |
5752 KB |
Output is correct |
3 |
Correct |
1197 ms |
7944 KB |
Output is correct |
4 |
Correct |
1193 ms |
7828 KB |
Output is correct |
5 |
Correct |
148 ms |
5024 KB |
Output is correct |
6 |
Correct |
1210 ms |
7876 KB |
Output is correct |
7 |
Correct |
1034 ms |
7952 KB |
Output is correct |
8 |
Correct |
879 ms |
7872 KB |
Output is correct |
9 |
Correct |
837 ms |
8132 KB |
Output is correct |
10 |
Correct |
795 ms |
8072 KB |
Output is correct |
11 |
Correct |
800 ms |
7788 KB |
Output is correct |
12 |
Correct |
744 ms |
7740 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2219 ms |
12536 KB |
Output is correct |
2 |
Correct |
152 ms |
4968 KB |
Output is correct |
3 |
Correct |
180 ms |
8828 KB |
Output is correct |
4 |
Correct |
113 ms |
8760 KB |
Output is correct |
5 |
Correct |
1406 ms |
12308 KB |
Output is correct |
6 |
Correct |
2193 ms |
12340 KB |
Output is correct |
7 |
Correct |
1371 ms |
12428 KB |
Output is correct |
8 |
Correct |
866 ms |
9212 KB |
Output is correct |
9 |
Correct |
906 ms |
9200 KB |
Output is correct |
10 |
Correct |
883 ms |
9424 KB |
Output is correct |
11 |
Correct |
1286 ms |
10660 KB |
Output is correct |
12 |
Correct |
1317 ms |
10768 KB |
Output is correct |
13 |
Correct |
1438 ms |
10928 KB |
Output is correct |
14 |
Correct |
1085 ms |
12504 KB |
Output is correct |
15 |
Correct |
1180 ms |
12380 KB |
Output is correct |
16 |
Correct |
2118 ms |
12452 KB |
Output is correct |
17 |
Correct |
2088 ms |
12328 KB |
Output is correct |
18 |
Correct |
2060 ms |
12388 KB |
Output is correct |
19 |
Correct |
2135 ms |
12396 KB |
Output is correct |
20 |
Correct |
1586 ms |
11480 KB |
Output is correct |
21 |
Correct |
1604 ms |
11528 KB |
Output is correct |
22 |
Correct |
1824 ms |
12224 KB |
Output is correct |
23 |
Correct |
1284 ms |
11204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1420 ms |
9188 KB |
Output is correct |
2 |
Correct |
1491 ms |
9460 KB |
Output is correct |
3 |
Correct |
1357 ms |
9508 KB |
Output is correct |
4 |
Correct |
1404 ms |
9352 KB |
Output is correct |
5 |
Correct |
1510 ms |
9272 KB |
Output is correct |
6 |
Correct |
1816 ms |
9748 KB |
Output is correct |
7 |
Correct |
1864 ms |
9676 KB |
Output is correct |
8 |
Correct |
1840 ms |
9348 KB |
Output is correct |
9 |
Correct |
153 ms |
4964 KB |
Output is correct |
10 |
Correct |
1145 ms |
9360 KB |
Output is correct |
11 |
Correct |
1252 ms |
9288 KB |
Output is correct |
12 |
Correct |
1343 ms |
9676 KB |
Output is correct |
13 |
Correct |
1308 ms |
9528 KB |
Output is correct |
14 |
Correct |
1159 ms |
7896 KB |
Output is correct |
15 |
Correct |
807 ms |
5752 KB |
Output is correct |
16 |
Correct |
1197 ms |
7944 KB |
Output is correct |
17 |
Correct |
1193 ms |
7828 KB |
Output is correct |
18 |
Correct |
148 ms |
5024 KB |
Output is correct |
19 |
Correct |
1210 ms |
7876 KB |
Output is correct |
20 |
Correct |
1034 ms |
7952 KB |
Output is correct |
21 |
Correct |
879 ms |
7872 KB |
Output is correct |
22 |
Correct |
837 ms |
8132 KB |
Output is correct |
23 |
Correct |
795 ms |
8072 KB |
Output is correct |
24 |
Correct |
800 ms |
7788 KB |
Output is correct |
25 |
Correct |
744 ms |
7740 KB |
Output is correct |
26 |
Correct |
1428 ms |
9392 KB |
Output is correct |
27 |
Correct |
1990 ms |
9448 KB |
Output is correct |
28 |
Correct |
1771 ms |
9324 KB |
Output is correct |
29 |
Correct |
1530 ms |
9460 KB |
Output is correct |
30 |
Correct |
1565 ms |
9300 KB |
Output is correct |
31 |
Correct |
1577 ms |
9336 KB |
Output is correct |
32 |
Correct |
1632 ms |
9320 KB |
Output is correct |
33 |
Correct |
1474 ms |
9244 KB |
Output is correct |
34 |
Correct |
1376 ms |
9284 KB |
Output is correct |
35 |
Correct |
1448 ms |
9388 KB |
Output is correct |
36 |
Correct |
1170 ms |
9308 KB |
Output is correct |
37 |
Correct |
1440 ms |
9248 KB |
Output is correct |
38 |
Correct |
1233 ms |
9232 KB |
Output is correct |
39 |
Correct |
1179 ms |
9448 KB |
Output is correct |
40 |
Correct |
1010 ms |
9328 KB |
Output is correct |
41 |
Correct |
1106 ms |
9288 KB |
Output is correct |
42 |
Correct |
994 ms |
9412 KB |
Output is correct |
43 |
Correct |
987 ms |
9360 KB |
Output is correct |
44 |
Correct |
994 ms |
9400 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2644 KB |
Output is correct |
2 |
Correct |
2 ms |
2644 KB |
Output is correct |
3 |
Correct |
34 ms |
2980 KB |
Output is correct |
4 |
Correct |
17 ms |
2932 KB |
Output is correct |
5 |
Correct |
37 ms |
2860 KB |
Output is correct |
6 |
Correct |
30 ms |
2844 KB |
Output is correct |
7 |
Correct |
35 ms |
2852 KB |
Output is correct |
8 |
Correct |
38 ms |
2868 KB |
Output is correct |
9 |
Correct |
38 ms |
2772 KB |
Output is correct |
10 |
Correct |
38 ms |
2856 KB |
Output is correct |
11 |
Correct |
40 ms |
2860 KB |
Output is correct |
12 |
Correct |
44 ms |
2772 KB |
Output is correct |
13 |
Correct |
43 ms |
2916 KB |
Output is correct |
14 |
Correct |
43 ms |
2900 KB |
Output is correct |
15 |
Correct |
45 ms |
2900 KB |
Output is correct |
16 |
Correct |
44 ms |
2856 KB |
Output is correct |
17 |
Correct |
41 ms |
2856 KB |
Output is correct |
18 |
Correct |
1420 ms |
9188 KB |
Output is correct |
19 |
Correct |
1491 ms |
9460 KB |
Output is correct |
20 |
Correct |
1357 ms |
9508 KB |
Output is correct |
21 |
Correct |
1404 ms |
9352 KB |
Output is correct |
22 |
Correct |
1510 ms |
9272 KB |
Output is correct |
23 |
Correct |
1816 ms |
9748 KB |
Output is correct |
24 |
Correct |
1864 ms |
9676 KB |
Output is correct |
25 |
Correct |
1840 ms |
9348 KB |
Output is correct |
26 |
Correct |
153 ms |
4964 KB |
Output is correct |
27 |
Correct |
1145 ms |
9360 KB |
Output is correct |
28 |
Correct |
1252 ms |
9288 KB |
Output is correct |
29 |
Correct |
1343 ms |
9676 KB |
Output is correct |
30 |
Correct |
1308 ms |
9528 KB |
Output is correct |
31 |
Correct |
1159 ms |
7896 KB |
Output is correct |
32 |
Correct |
807 ms |
5752 KB |
Output is correct |
33 |
Correct |
1197 ms |
7944 KB |
Output is correct |
34 |
Correct |
1193 ms |
7828 KB |
Output is correct |
35 |
Correct |
148 ms |
5024 KB |
Output is correct |
36 |
Correct |
1210 ms |
7876 KB |
Output is correct |
37 |
Correct |
1034 ms |
7952 KB |
Output is correct |
38 |
Correct |
879 ms |
7872 KB |
Output is correct |
39 |
Correct |
837 ms |
8132 KB |
Output is correct |
40 |
Correct |
795 ms |
8072 KB |
Output is correct |
41 |
Correct |
800 ms |
7788 KB |
Output is correct |
42 |
Correct |
744 ms |
7740 KB |
Output is correct |
43 |
Correct |
2219 ms |
12536 KB |
Output is correct |
44 |
Correct |
152 ms |
4968 KB |
Output is correct |
45 |
Correct |
180 ms |
8828 KB |
Output is correct |
46 |
Correct |
113 ms |
8760 KB |
Output is correct |
47 |
Correct |
1406 ms |
12308 KB |
Output is correct |
48 |
Correct |
2193 ms |
12340 KB |
Output is correct |
49 |
Correct |
1371 ms |
12428 KB |
Output is correct |
50 |
Correct |
866 ms |
9212 KB |
Output is correct |
51 |
Correct |
906 ms |
9200 KB |
Output is correct |
52 |
Correct |
883 ms |
9424 KB |
Output is correct |
53 |
Correct |
1286 ms |
10660 KB |
Output is correct |
54 |
Correct |
1317 ms |
10768 KB |
Output is correct |
55 |
Correct |
1438 ms |
10928 KB |
Output is correct |
56 |
Correct |
1085 ms |
12504 KB |
Output is correct |
57 |
Correct |
1180 ms |
12380 KB |
Output is correct |
58 |
Correct |
2118 ms |
12452 KB |
Output is correct |
59 |
Correct |
2088 ms |
12328 KB |
Output is correct |
60 |
Correct |
2060 ms |
12388 KB |
Output is correct |
61 |
Correct |
2135 ms |
12396 KB |
Output is correct |
62 |
Correct |
1586 ms |
11480 KB |
Output is correct |
63 |
Correct |
1604 ms |
11528 KB |
Output is correct |
64 |
Correct |
1824 ms |
12224 KB |
Output is correct |
65 |
Correct |
1284 ms |
11204 KB |
Output is correct |
66 |
Correct |
1428 ms |
9392 KB |
Output is correct |
67 |
Correct |
1990 ms |
9448 KB |
Output is correct |
68 |
Correct |
1771 ms |
9324 KB |
Output is correct |
69 |
Correct |
1530 ms |
9460 KB |
Output is correct |
70 |
Correct |
1565 ms |
9300 KB |
Output is correct |
71 |
Correct |
1577 ms |
9336 KB |
Output is correct |
72 |
Correct |
1632 ms |
9320 KB |
Output is correct |
73 |
Correct |
1474 ms |
9244 KB |
Output is correct |
74 |
Correct |
1376 ms |
9284 KB |
Output is correct |
75 |
Correct |
1448 ms |
9388 KB |
Output is correct |
76 |
Correct |
1170 ms |
9308 KB |
Output is correct |
77 |
Correct |
1440 ms |
9248 KB |
Output is correct |
78 |
Correct |
1233 ms |
9232 KB |
Output is correct |
79 |
Correct |
1179 ms |
9448 KB |
Output is correct |
80 |
Correct |
1010 ms |
9328 KB |
Output is correct |
81 |
Correct |
1106 ms |
9288 KB |
Output is correct |
82 |
Correct |
994 ms |
9412 KB |
Output is correct |
83 |
Correct |
987 ms |
9360 KB |
Output is correct |
84 |
Correct |
994 ms |
9400 KB |
Output is correct |
85 |
Correct |
2401 ms |
16404 KB |
Output is correct |
86 |
Correct |
205 ms |
11032 KB |
Output is correct |
87 |
Correct |
138 ms |
11140 KB |
Output is correct |
88 |
Correct |
1813 ms |
15252 KB |
Output is correct |
89 |
Correct |
2411 ms |
16304 KB |
Output is correct |
90 |
Correct |
1743 ms |
14664 KB |
Output is correct |
91 |
Correct |
1480 ms |
11868 KB |
Output is correct |
92 |
Correct |
1572 ms |
12052 KB |
Output is correct |
93 |
Correct |
2025 ms |
12012 KB |
Output is correct |
94 |
Correct |
1848 ms |
14116 KB |
Output is correct |
95 |
Correct |
1835 ms |
14396 KB |
Output is correct |
96 |
Correct |
1801 ms |
14160 KB |
Output is correct |
97 |
Correct |
1586 ms |
15124 KB |
Output is correct |
98 |
Correct |
1564 ms |
14540 KB |
Output is correct |
99 |
Correct |
2291 ms |
16248 KB |
Output is correct |
100 |
Correct |
2443 ms |
16308 KB |
Output is correct |
101 |
Correct |
2300 ms |
16672 KB |
Output is correct |
102 |
Correct |
2510 ms |
16264 KB |
Output is correct |
103 |
Correct |
2315 ms |
15032 KB |
Output is correct |
104 |
Correct |
2031 ms |
15024 KB |
Output is correct |
105 |
Correct |
1960 ms |
14592 KB |
Output is correct |
106 |
Correct |
1333 ms |
13864 KB |
Output is correct |
107 |
Correct |
1792 ms |
14992 KB |
Output is correct |
108 |
Correct |
2225 ms |
15904 KB |
Output is correct |
109 |
Correct |
1721 ms |
13440 KB |
Output is correct |