#include<bits/stdc++.h>
using namespace std;
//#pragma GCC optimize("O3")
//#pragma GCC optimize("unroll-loops")
#define ll long long
#define vt vector
#define pb push_back
#define fi first
#define se second
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
typedef unsigned long long ull;
#include<fstream>
ifstream fin("ss.inp");
ofstream fout("ss.out");
#define pii pair<int, int>
#define pll pair<ll, ll>
const ll mod = 1e9 + 7, mod2 = 1e9 + 9;
const int mxn = 5e4, mxq = 1e5, sq = 800, mxm = 1e5;
int n, m, q;
struct DSU{
vt<pii>past_sz, past_p;
int p[mxn + 1], sz[mxn + 1];
void init(){
memset(p, -1, sizeof(p));
past_sz.clear(); past_p.clear();
}
int fp(int a){
if(p[a] < 0)return(a);
return(fp(p[a]));
}
int getsz(int pp){
return(-p[fp(pp)]);
}
void unon(int u, int v){
u = fp(u); v = fp(v);
if(-p[u] < -p[v])swap(u, v);
past_sz.pb({u, p[u]}); past_p.pb({v, p[v]});
if(u != v){
p[u] += p[v]; p[v] = u;
}
}
void rollback(){
p[past_p.back().fi] = past_p.back().se; past_p.pop_back();
p[past_sz.back().fi] = past_sz.back().se; past_sz.pop_back();
}
};
struct e{
int u, v, w;
bool operator <(const e &b){
return(w > b.w);
}
};
struct qq{
int id, a, b;
};
struct qq2{
int s, w, id;
bool operator <(const qq2 &b){
return(w > b.w);
}
};
vt<e>edge;
DSU dsu;
vt<qq>queries[sq + 1];
bool change[mxm + 1];
int nww[mxm + 1], ans[mxn + 1];
void solve(vt<qq>v){
dsu.init();
vt<qq2>ask;
for(int i = 0; i < v.size(); i++){
if(v[i].id == 1)change[v[i].a] = true;
else ask.pb({v[i].a, v[i].b, i});
}
sort(ask.begin(), ask.end());
vt<e>unchanged;
vt<pii>changed;
for(int i = 0; i < m; i++){
if(!change[i])unchanged.pb(edge[i]);
else changed.pb({i, edge[i].w});
}
sort(unchanged.begin(), unchanged.end());
int l = 0;
for(int i = 0; i < ask.size(); i++){
while(l < unchanged.size() && unchanged[l].w >= ask[i].w){
dsu.unon(unchanged[l].u, unchanged[l].v); l++;
}
for(int j = 0; j < ask[i].id; j++){
if(v[j].id == 1)edge[v[j].a].w = v[j].b;
}
int cnt = 0;
for(int j = 0; j < changed.size(); j++){
if(edge[changed[j].fi].w >= ask[i].w){
dsu.unon(edge[changed[j].fi].u, edge[changed[j].fi].v);
cnt++;
}
}
ans[ask[i].id] = dsu.getsz(ask[i].s);
forr(j, 0, cnt)dsu.rollback();
for(int j = 0; j < changed.size(); j++)edge[changed[j].fi].w = changed[j].se;
}
for(int i = 0; i < v.size(); i++){
if(v[i].id == 2)cout << ans[i] << "\n";
}
forr(i, 0, v.size()){
if(v[i].id == 1){
change[v[i].a] = false;
edge[v[i].a].w = v[i].b;
}
}
}
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> m;
forr(i, 0, m){
int u, v, w; cin >> u >> v >> w;
edge.pb({u, v, w});
}
cin >> q;
forr(i, 0, q){
int idq, u, v; cin >> idq >> u >> v;
if(idq == 1)--u;
queries[i / sq].pb({idq, u, v});
}
for(int i = 0; i <= (q - 1) / sq; i++){
solve(queries[i]);
}
return 0;
}
Compilation message
bridges.cpp: In function 'void solve(std::vector<qq>)':
bridges.cpp:76:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<qq>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
76 | for(int i = 0; i < v.size(); i++){
| ~~^~~~~~~~~~
bridges.cpp:89:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<qq2>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
89 | for(int i = 0; i < ask.size(); i++){
| ~~^~~~~~~~~~~~
bridges.cpp:90:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<e>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
90 | while(l < unchanged.size() && unchanged[l].w >= ask[i].w){
| ~~^~~~~~~~~~~~~~~~~~
bridges.cpp:97:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
97 | for(int j = 0; j < changed.size(); j++){
| ~~^~~~~~~~~~~~~~~~
bridges.cpp:105:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
105 | for(int j = 0; j < changed.size(); j++)edge[changed[j].fi].w = changed[j].se;
| ~~^~~~~~~~~~~~~~~~
bridges.cpp:107:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<qq>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
107 | for(int i = 0; i < v.size(); i++){
| ~~^~~~~~~~~~
bridges.cpp:12:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<qq>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
12 | #define forr(i, a, b) for(int i = a; i < b; i++)
......
110 | forr(i, 0, v.size()){
| ~~~~~~~~~~~~~~
bridges.cpp:110:5: note: in expansion of macro 'forr'
110 | forr(i, 0, v.size()){
| ^~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
468 KB |
Output is correct |
2 |
Correct |
0 ms |
468 KB |
Output is correct |
3 |
Correct |
40 ms |
804 KB |
Output is correct |
4 |
Correct |
6 ms |
724 KB |
Output is correct |
5 |
Correct |
22 ms |
740 KB |
Output is correct |
6 |
Correct |
20 ms |
748 KB |
Output is correct |
7 |
Correct |
21 ms |
724 KB |
Output is correct |
8 |
Correct |
21 ms |
724 KB |
Output is correct |
9 |
Correct |
25 ms |
728 KB |
Output is correct |
10 |
Correct |
21 ms |
740 KB |
Output is correct |
11 |
Correct |
21 ms |
748 KB |
Output is correct |
12 |
Correct |
22 ms |
748 KB |
Output is correct |
13 |
Correct |
28 ms |
752 KB |
Output is correct |
14 |
Correct |
25 ms |
760 KB |
Output is correct |
15 |
Correct |
22 ms |
756 KB |
Output is correct |
16 |
Correct |
22 ms |
724 KB |
Output is correct |
17 |
Correct |
22 ms |
736 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1202 ms |
5240 KB |
Output is correct |
2 |
Correct |
1219 ms |
5220 KB |
Output is correct |
3 |
Correct |
1206 ms |
5372 KB |
Output is correct |
4 |
Correct |
1184 ms |
5104 KB |
Output is correct |
5 |
Correct |
1176 ms |
5344 KB |
Output is correct |
6 |
Correct |
1492 ms |
5484 KB |
Output is correct |
7 |
Correct |
1476 ms |
5412 KB |
Output is correct |
8 |
Correct |
1482 ms |
5356 KB |
Output is correct |
9 |
Correct |
64 ms |
2196 KB |
Output is correct |
10 |
Correct |
957 ms |
5304 KB |
Output is correct |
11 |
Correct |
929 ms |
5248 KB |
Output is correct |
12 |
Correct |
973 ms |
5540 KB |
Output is correct |
13 |
Correct |
941 ms |
5084 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
933 ms |
4040 KB |
Output is correct |
2 |
Correct |
660 ms |
2792 KB |
Output is correct |
3 |
Correct |
1031 ms |
4196 KB |
Output is correct |
4 |
Correct |
924 ms |
4000 KB |
Output is correct |
5 |
Correct |
60 ms |
2176 KB |
Output is correct |
6 |
Correct |
1000 ms |
4140 KB |
Output is correct |
7 |
Correct |
870 ms |
4056 KB |
Output is correct |
8 |
Correct |
799 ms |
4008 KB |
Output is correct |
9 |
Correct |
625 ms |
4324 KB |
Output is correct |
10 |
Correct |
619 ms |
4308 KB |
Output is correct |
11 |
Correct |
608 ms |
3876 KB |
Output is correct |
12 |
Correct |
552 ms |
3844 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1544 ms |
8468 KB |
Output is correct |
2 |
Correct |
61 ms |
2252 KB |
Output is correct |
3 |
Correct |
167 ms |
6468 KB |
Output is correct |
4 |
Correct |
98 ms |
6468 KB |
Output is correct |
5 |
Correct |
959 ms |
8308 KB |
Output is correct |
6 |
Correct |
1497 ms |
8636 KB |
Output is correct |
7 |
Correct |
903 ms |
8400 KB |
Output is correct |
8 |
Correct |
669 ms |
5132 KB |
Output is correct |
9 |
Correct |
656 ms |
5136 KB |
Output is correct |
10 |
Correct |
682 ms |
5380 KB |
Output is correct |
11 |
Correct |
1133 ms |
7524 KB |
Output is correct |
12 |
Correct |
1127 ms |
7400 KB |
Output is correct |
13 |
Correct |
1148 ms |
7544 KB |
Output is correct |
14 |
Correct |
904 ms |
8612 KB |
Output is correct |
15 |
Correct |
924 ms |
8564 KB |
Output is correct |
16 |
Correct |
1522 ms |
8268 KB |
Output is correct |
17 |
Correct |
1520 ms |
8344 KB |
Output is correct |
18 |
Correct |
1534 ms |
8436 KB |
Output is correct |
19 |
Correct |
1505 ms |
8248 KB |
Output is correct |
20 |
Correct |
1288 ms |
7916 KB |
Output is correct |
21 |
Correct |
1273 ms |
8104 KB |
Output is correct |
22 |
Correct |
1454 ms |
8480 KB |
Output is correct |
23 |
Correct |
938 ms |
7824 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1202 ms |
5240 KB |
Output is correct |
2 |
Correct |
1219 ms |
5220 KB |
Output is correct |
3 |
Correct |
1206 ms |
5372 KB |
Output is correct |
4 |
Correct |
1184 ms |
5104 KB |
Output is correct |
5 |
Correct |
1176 ms |
5344 KB |
Output is correct |
6 |
Correct |
1492 ms |
5484 KB |
Output is correct |
7 |
Correct |
1476 ms |
5412 KB |
Output is correct |
8 |
Correct |
1482 ms |
5356 KB |
Output is correct |
9 |
Correct |
64 ms |
2196 KB |
Output is correct |
10 |
Correct |
957 ms |
5304 KB |
Output is correct |
11 |
Correct |
929 ms |
5248 KB |
Output is correct |
12 |
Correct |
973 ms |
5540 KB |
Output is correct |
13 |
Correct |
941 ms |
5084 KB |
Output is correct |
14 |
Correct |
933 ms |
4040 KB |
Output is correct |
15 |
Correct |
660 ms |
2792 KB |
Output is correct |
16 |
Correct |
1031 ms |
4196 KB |
Output is correct |
17 |
Correct |
924 ms |
4000 KB |
Output is correct |
18 |
Correct |
60 ms |
2176 KB |
Output is correct |
19 |
Correct |
1000 ms |
4140 KB |
Output is correct |
20 |
Correct |
870 ms |
4056 KB |
Output is correct |
21 |
Correct |
799 ms |
4008 KB |
Output is correct |
22 |
Correct |
625 ms |
4324 KB |
Output is correct |
23 |
Correct |
619 ms |
4308 KB |
Output is correct |
24 |
Correct |
608 ms |
3876 KB |
Output is correct |
25 |
Correct |
552 ms |
3844 KB |
Output is correct |
26 |
Correct |
1187 ms |
5244 KB |
Output is correct |
27 |
Correct |
1398 ms |
5348 KB |
Output is correct |
28 |
Correct |
1248 ms |
5260 KB |
Output is correct |
29 |
Correct |
1016 ms |
5176 KB |
Output is correct |
30 |
Correct |
1360 ms |
5304 KB |
Output is correct |
31 |
Correct |
1383 ms |
5308 KB |
Output is correct |
32 |
Correct |
1373 ms |
5476 KB |
Output is correct |
33 |
Correct |
1227 ms |
5144 KB |
Output is correct |
34 |
Correct |
1222 ms |
5232 KB |
Output is correct |
35 |
Correct |
1229 ms |
5224 KB |
Output is correct |
36 |
Correct |
1022 ms |
5320 KB |
Output is correct |
37 |
Correct |
1025 ms |
5200 KB |
Output is correct |
38 |
Correct |
1024 ms |
5304 KB |
Output is correct |
39 |
Correct |
784 ms |
5336 KB |
Output is correct |
40 |
Correct |
813 ms |
5160 KB |
Output is correct |
41 |
Correct |
779 ms |
5352 KB |
Output is correct |
42 |
Correct |
778 ms |
5104 KB |
Output is correct |
43 |
Correct |
795 ms |
5056 KB |
Output is correct |
44 |
Correct |
783 ms |
5020 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
468 KB |
Output is correct |
2 |
Correct |
0 ms |
468 KB |
Output is correct |
3 |
Correct |
40 ms |
804 KB |
Output is correct |
4 |
Correct |
6 ms |
724 KB |
Output is correct |
5 |
Correct |
22 ms |
740 KB |
Output is correct |
6 |
Correct |
20 ms |
748 KB |
Output is correct |
7 |
Correct |
21 ms |
724 KB |
Output is correct |
8 |
Correct |
21 ms |
724 KB |
Output is correct |
9 |
Correct |
25 ms |
728 KB |
Output is correct |
10 |
Correct |
21 ms |
740 KB |
Output is correct |
11 |
Correct |
21 ms |
748 KB |
Output is correct |
12 |
Correct |
22 ms |
748 KB |
Output is correct |
13 |
Correct |
28 ms |
752 KB |
Output is correct |
14 |
Correct |
25 ms |
760 KB |
Output is correct |
15 |
Correct |
22 ms |
756 KB |
Output is correct |
16 |
Correct |
22 ms |
724 KB |
Output is correct |
17 |
Correct |
22 ms |
736 KB |
Output is correct |
18 |
Correct |
1202 ms |
5240 KB |
Output is correct |
19 |
Correct |
1219 ms |
5220 KB |
Output is correct |
20 |
Correct |
1206 ms |
5372 KB |
Output is correct |
21 |
Correct |
1184 ms |
5104 KB |
Output is correct |
22 |
Correct |
1176 ms |
5344 KB |
Output is correct |
23 |
Correct |
1492 ms |
5484 KB |
Output is correct |
24 |
Correct |
1476 ms |
5412 KB |
Output is correct |
25 |
Correct |
1482 ms |
5356 KB |
Output is correct |
26 |
Correct |
64 ms |
2196 KB |
Output is correct |
27 |
Correct |
957 ms |
5304 KB |
Output is correct |
28 |
Correct |
929 ms |
5248 KB |
Output is correct |
29 |
Correct |
973 ms |
5540 KB |
Output is correct |
30 |
Correct |
941 ms |
5084 KB |
Output is correct |
31 |
Correct |
933 ms |
4040 KB |
Output is correct |
32 |
Correct |
660 ms |
2792 KB |
Output is correct |
33 |
Correct |
1031 ms |
4196 KB |
Output is correct |
34 |
Correct |
924 ms |
4000 KB |
Output is correct |
35 |
Correct |
60 ms |
2176 KB |
Output is correct |
36 |
Correct |
1000 ms |
4140 KB |
Output is correct |
37 |
Correct |
870 ms |
4056 KB |
Output is correct |
38 |
Correct |
799 ms |
4008 KB |
Output is correct |
39 |
Correct |
625 ms |
4324 KB |
Output is correct |
40 |
Correct |
619 ms |
4308 KB |
Output is correct |
41 |
Correct |
608 ms |
3876 KB |
Output is correct |
42 |
Correct |
552 ms |
3844 KB |
Output is correct |
43 |
Correct |
1544 ms |
8468 KB |
Output is correct |
44 |
Correct |
61 ms |
2252 KB |
Output is correct |
45 |
Correct |
167 ms |
6468 KB |
Output is correct |
46 |
Correct |
98 ms |
6468 KB |
Output is correct |
47 |
Correct |
959 ms |
8308 KB |
Output is correct |
48 |
Correct |
1497 ms |
8636 KB |
Output is correct |
49 |
Correct |
903 ms |
8400 KB |
Output is correct |
50 |
Correct |
669 ms |
5132 KB |
Output is correct |
51 |
Correct |
656 ms |
5136 KB |
Output is correct |
52 |
Correct |
682 ms |
5380 KB |
Output is correct |
53 |
Correct |
1133 ms |
7524 KB |
Output is correct |
54 |
Correct |
1127 ms |
7400 KB |
Output is correct |
55 |
Correct |
1148 ms |
7544 KB |
Output is correct |
56 |
Correct |
904 ms |
8612 KB |
Output is correct |
57 |
Correct |
924 ms |
8564 KB |
Output is correct |
58 |
Correct |
1522 ms |
8268 KB |
Output is correct |
59 |
Correct |
1520 ms |
8344 KB |
Output is correct |
60 |
Correct |
1534 ms |
8436 KB |
Output is correct |
61 |
Correct |
1505 ms |
8248 KB |
Output is correct |
62 |
Correct |
1288 ms |
7916 KB |
Output is correct |
63 |
Correct |
1273 ms |
8104 KB |
Output is correct |
64 |
Correct |
1454 ms |
8480 KB |
Output is correct |
65 |
Correct |
938 ms |
7824 KB |
Output is correct |
66 |
Correct |
1187 ms |
5244 KB |
Output is correct |
67 |
Correct |
1398 ms |
5348 KB |
Output is correct |
68 |
Correct |
1248 ms |
5260 KB |
Output is correct |
69 |
Correct |
1016 ms |
5176 KB |
Output is correct |
70 |
Correct |
1360 ms |
5304 KB |
Output is correct |
71 |
Correct |
1383 ms |
5308 KB |
Output is correct |
72 |
Correct |
1373 ms |
5476 KB |
Output is correct |
73 |
Correct |
1227 ms |
5144 KB |
Output is correct |
74 |
Correct |
1222 ms |
5232 KB |
Output is correct |
75 |
Correct |
1229 ms |
5224 KB |
Output is correct |
76 |
Correct |
1022 ms |
5320 KB |
Output is correct |
77 |
Correct |
1025 ms |
5200 KB |
Output is correct |
78 |
Correct |
1024 ms |
5304 KB |
Output is correct |
79 |
Correct |
784 ms |
5336 KB |
Output is correct |
80 |
Correct |
813 ms |
5160 KB |
Output is correct |
81 |
Correct |
779 ms |
5352 KB |
Output is correct |
82 |
Correct |
778 ms |
5104 KB |
Output is correct |
83 |
Correct |
795 ms |
5056 KB |
Output is correct |
84 |
Correct |
783 ms |
5020 KB |
Output is correct |
85 |
Correct |
2033 ms |
8100 KB |
Output is correct |
86 |
Correct |
213 ms |
8148 KB |
Output is correct |
87 |
Correct |
158 ms |
8268 KB |
Output is correct |
88 |
Correct |
1410 ms |
10356 KB |
Output is correct |
89 |
Correct |
1979 ms |
11920 KB |
Output is correct |
90 |
Correct |
1413 ms |
10424 KB |
Output is correct |
91 |
Correct |
1238 ms |
8084 KB |
Output is correct |
92 |
Correct |
1249 ms |
7888 KB |
Output is correct |
93 |
Correct |
1550 ms |
8188 KB |
Output is correct |
94 |
Correct |
1647 ms |
10188 KB |
Output is correct |
95 |
Correct |
1626 ms |
10256 KB |
Output is correct |
96 |
Correct |
1859 ms |
10088 KB |
Output is correct |
97 |
Correct |
1085 ms |
10708 KB |
Output is correct |
98 |
Correct |
1070 ms |
10012 KB |
Output is correct |
99 |
Correct |
2020 ms |
11688 KB |
Output is correct |
100 |
Correct |
2016 ms |
11972 KB |
Output is correct |
101 |
Correct |
2024 ms |
11912 KB |
Output is correct |
102 |
Correct |
1980 ms |
12048 KB |
Output is correct |
103 |
Correct |
2037 ms |
10636 KB |
Output is correct |
104 |
Correct |
2027 ms |
10800 KB |
Output is correct |
105 |
Correct |
1519 ms |
10588 KB |
Output is correct |
106 |
Correct |
1232 ms |
10428 KB |
Output is correct |
107 |
Correct |
1483 ms |
11332 KB |
Output is correct |
108 |
Correct |
2033 ms |
11664 KB |
Output is correct |
109 |
Correct |
1518 ms |
9292 KB |
Output is correct |