#include<bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxN = 1e5 + 5;
const int mod = 1e9 + 7;
const ll oo = 1e18;
int n, m;
int block_size = 1000;
int mark[maxN];
int lab[maxN];
int res[maxN];
vector<pair<int, int>> vc;
int Findset(int u)
{
return lab[u] < 0 ? u : Findset(lab[u]);
}
void Unite(int u, int v)
{
int r = Findset(u), s = Findset(v);
if(r == s)
return;
if(lab[r] > lab[s])
swap(r, s);
vc.pb({r, lab[r]});
vc.pb({s, lab[s]});
lab[r] += lab[s];
lab[s] = r;
}
void roll_back(int sz)
{
while(vc.size() > sz)
{
pair<int, int> tmp = vc.back();
vc.pop_back();
lab[tmp.fi] = tmp.se;
}
}
struct TEdge
{
int u, v, w;
} e[maxN];
int q;
struct TQuery
{
int type;
int s, w;
} qu[maxN];
vector<int> upd[maxN];
void ReadInput()
{
cin >> n >> m;
for(int i=1; i<=m; i++)
{
int u, v, w;
cin >> u >> v >> w;
e[i] = {u, v, w};
}
cin >> q;
for(int i=1; i<=q; i++)
{
cin >> qu[i].type >> qu[i].s >> qu[i].w;
}
}
void Solve()
{
for(int i=1; i<=block_size; i++)
{
memset(lab, -1, sizeof lab);
vc.clear();
int l = block_size * (i - 1) + 1, r = min(q, block_size * i);
if(l > q)
break;
for(int j=1; j<=m; j++)
mark[j] = 0;
for(int j=l; j<=r; j++)
{
if(qu[j].type == 1)
{
mark[qu[j].s] = 1;
}
}
vector<int> unchanged, query, changed;
for(int j=1; j<=m; j++)
{
if(!mark[j])
unchanged.pb(j);
else
changed.pb(j);
}
for(int j=l; j<=r; j++)
if(qu[j].type == 2)
query.pb(j);
for(int j=l; j<=r; j++)
{
if(qu[j].type == 1)
e[qu[j].s].w = qu[j].w;
else
{
for(int v : changed)
if(e[v].w >= qu[j].w)
upd[j].pb(v);
}
}
sort(unchanged.begin(), unchanged.end(), [](int i, int j)
{
return e[i].w > e[j].w;
});
sort(query.begin(), query.end(), [](int i, int j)
{
return qu[i].w > qu[j].w;
});
int p = 0;
for(int j : query)
{
while(p < unchanged.size() && e[unchanged[p]].w >= qu[j].w)
{
Unite(e[unchanged[p]].u, e[unchanged[p]].v);
p++;
}
int sz = vc.size();
for(int v : upd[j])
{
// if(j == 5) cout << v << " ";
Unite(e[v].u, e[v].v);
}
res[j] = -lab[Findset(qu[j].s)];
roll_back(sz);
}
}
for(int i=1; i<=q; i++)
{
if(qu[i].type == 2)
cout << res[i] << '\n';
}
}
int32_t main()
{
// freopen("x.inp", "r", stdin);
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
ReadInput();
Solve();
}
Compilation message
bridges.cpp: In function 'void roll_back(int)':
bridges.cpp:37:21: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
37 | while(vc.size() > sz)
| ~~~~~~~~~~^~~~
bridges.cpp: In function 'void Solve()':
bridges.cpp:121:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
121 | while(p < unchanged.size() && e[unchanged[p]].w >= qu[j].w)
| ~~^~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
3028 KB |
Output is correct |
2 |
Correct |
2 ms |
3156 KB |
Output is correct |
3 |
Correct |
32 ms |
9108 KB |
Output is correct |
4 |
Correct |
5 ms |
3336 KB |
Output is correct |
5 |
Correct |
13 ms |
5004 KB |
Output is correct |
6 |
Correct |
10 ms |
4876 KB |
Output is correct |
7 |
Correct |
16 ms |
4820 KB |
Output is correct |
8 |
Correct |
14 ms |
4724 KB |
Output is correct |
9 |
Correct |
18 ms |
5832 KB |
Output is correct |
10 |
Correct |
16 ms |
4872 KB |
Output is correct |
11 |
Correct |
16 ms |
4876 KB |
Output is correct |
12 |
Correct |
20 ms |
5164 KB |
Output is correct |
13 |
Correct |
25 ms |
5784 KB |
Output is correct |
14 |
Correct |
20 ms |
5324 KB |
Output is correct |
15 |
Correct |
15 ms |
4948 KB |
Output is correct |
16 |
Correct |
17 ms |
5196 KB |
Output is correct |
17 |
Correct |
17 ms |
5184 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1262 ms |
73432 KB |
Output is correct |
2 |
Correct |
1248 ms |
73364 KB |
Output is correct |
3 |
Correct |
1267 ms |
73760 KB |
Output is correct |
4 |
Correct |
1238 ms |
73144 KB |
Output is correct |
5 |
Correct |
1221 ms |
73756 KB |
Output is correct |
6 |
Correct |
1772 ms |
125624 KB |
Output is correct |
7 |
Correct |
1741 ms |
125176 KB |
Output is correct |
8 |
Correct |
1757 ms |
123192 KB |
Output is correct |
9 |
Correct |
47 ms |
5116 KB |
Output is correct |
10 |
Correct |
1030 ms |
96956 KB |
Output is correct |
11 |
Correct |
965 ms |
97252 KB |
Output is correct |
12 |
Correct |
1130 ms |
53692 KB |
Output is correct |
13 |
Correct |
1012 ms |
47056 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1012 ms |
73124 KB |
Output is correct |
2 |
Correct |
750 ms |
90476 KB |
Output is correct |
3 |
Correct |
1167 ms |
98380 KB |
Output is correct |
4 |
Correct |
978 ms |
72572 KB |
Output is correct |
5 |
Correct |
41 ms |
4968 KB |
Output is correct |
6 |
Correct |
1123 ms |
92416 KB |
Output is correct |
7 |
Correct |
902 ms |
64752 KB |
Output is correct |
8 |
Correct |
793 ms |
48888 KB |
Output is correct |
9 |
Correct |
667 ms |
41064 KB |
Output is correct |
10 |
Correct |
603 ms |
29428 KB |
Output is correct |
11 |
Correct |
655 ms |
38520 KB |
Output is correct |
12 |
Correct |
579 ms |
28228 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1528 ms |
8276 KB |
Output is correct |
2 |
Correct |
36 ms |
5020 KB |
Output is correct |
3 |
Correct |
160 ms |
6020 KB |
Output is correct |
4 |
Correct |
77 ms |
5956 KB |
Output is correct |
5 |
Correct |
749 ms |
8168 KB |
Output is correct |
6 |
Correct |
1481 ms |
8228 KB |
Output is correct |
7 |
Correct |
757 ms |
8248 KB |
Output is correct |
8 |
Correct |
680 ms |
6996 KB |
Output is correct |
9 |
Correct |
688 ms |
7088 KB |
Output is correct |
10 |
Correct |
694 ms |
7284 KB |
Output is correct |
11 |
Correct |
1101 ms |
7796 KB |
Output is correct |
12 |
Correct |
1096 ms |
7660 KB |
Output is correct |
13 |
Correct |
1119 ms |
7764 KB |
Output is correct |
14 |
Correct |
640 ms |
8244 KB |
Output is correct |
15 |
Correct |
702 ms |
8144 KB |
Output is correct |
16 |
Correct |
1439 ms |
8348 KB |
Output is correct |
17 |
Correct |
1515 ms |
8420 KB |
Output is correct |
18 |
Correct |
1561 ms |
8296 KB |
Output is correct |
19 |
Correct |
1507 ms |
8208 KB |
Output is correct |
20 |
Correct |
1212 ms |
7892 KB |
Output is correct |
21 |
Correct |
1257 ms |
8012 KB |
Output is correct |
22 |
Correct |
1420 ms |
8196 KB |
Output is correct |
23 |
Correct |
823 ms |
7804 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1262 ms |
73432 KB |
Output is correct |
2 |
Correct |
1248 ms |
73364 KB |
Output is correct |
3 |
Correct |
1267 ms |
73760 KB |
Output is correct |
4 |
Correct |
1238 ms |
73144 KB |
Output is correct |
5 |
Correct |
1221 ms |
73756 KB |
Output is correct |
6 |
Correct |
1772 ms |
125624 KB |
Output is correct |
7 |
Correct |
1741 ms |
125176 KB |
Output is correct |
8 |
Correct |
1757 ms |
123192 KB |
Output is correct |
9 |
Correct |
47 ms |
5116 KB |
Output is correct |
10 |
Correct |
1030 ms |
96956 KB |
Output is correct |
11 |
Correct |
965 ms |
97252 KB |
Output is correct |
12 |
Correct |
1130 ms |
53692 KB |
Output is correct |
13 |
Correct |
1012 ms |
47056 KB |
Output is correct |
14 |
Correct |
1012 ms |
73124 KB |
Output is correct |
15 |
Correct |
750 ms |
90476 KB |
Output is correct |
16 |
Correct |
1167 ms |
98380 KB |
Output is correct |
17 |
Correct |
978 ms |
72572 KB |
Output is correct |
18 |
Correct |
41 ms |
4968 KB |
Output is correct |
19 |
Correct |
1123 ms |
92416 KB |
Output is correct |
20 |
Correct |
902 ms |
64752 KB |
Output is correct |
21 |
Correct |
793 ms |
48888 KB |
Output is correct |
22 |
Correct |
667 ms |
41064 KB |
Output is correct |
23 |
Correct |
603 ms |
29428 KB |
Output is correct |
24 |
Correct |
655 ms |
38520 KB |
Output is correct |
25 |
Correct |
579 ms |
28228 KB |
Output is correct |
26 |
Correct |
1242 ms |
73544 KB |
Output is correct |
27 |
Correct |
1496 ms |
100528 KB |
Output is correct |
28 |
Correct |
1343 ms |
71652 KB |
Output is correct |
29 |
Correct |
939 ms |
29024 KB |
Output is correct |
30 |
Correct |
1451 ms |
87936 KB |
Output is correct |
31 |
Correct |
1480 ms |
90284 KB |
Output is correct |
32 |
Correct |
1491 ms |
90788 KB |
Output is correct |
33 |
Correct |
1271 ms |
71968 KB |
Output is correct |
34 |
Correct |
1278 ms |
72112 KB |
Output is correct |
35 |
Correct |
1302 ms |
72440 KB |
Output is correct |
36 |
Correct |
997 ms |
35936 KB |
Output is correct |
37 |
Correct |
985 ms |
34708 KB |
Output is correct |
38 |
Correct |
967 ms |
33160 KB |
Output is correct |
39 |
Correct |
792 ms |
19292 KB |
Output is correct |
40 |
Correct |
829 ms |
18496 KB |
Output is correct |
41 |
Correct |
855 ms |
18164 KB |
Output is correct |
42 |
Correct |
748 ms |
17664 KB |
Output is correct |
43 |
Correct |
785 ms |
17240 KB |
Output is correct |
44 |
Correct |
773 ms |
16520 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
3028 KB |
Output is correct |
2 |
Correct |
2 ms |
3156 KB |
Output is correct |
3 |
Correct |
32 ms |
9108 KB |
Output is correct |
4 |
Correct |
5 ms |
3336 KB |
Output is correct |
5 |
Correct |
13 ms |
5004 KB |
Output is correct |
6 |
Correct |
10 ms |
4876 KB |
Output is correct |
7 |
Correct |
16 ms |
4820 KB |
Output is correct |
8 |
Correct |
14 ms |
4724 KB |
Output is correct |
9 |
Correct |
18 ms |
5832 KB |
Output is correct |
10 |
Correct |
16 ms |
4872 KB |
Output is correct |
11 |
Correct |
16 ms |
4876 KB |
Output is correct |
12 |
Correct |
20 ms |
5164 KB |
Output is correct |
13 |
Correct |
25 ms |
5784 KB |
Output is correct |
14 |
Correct |
20 ms |
5324 KB |
Output is correct |
15 |
Correct |
15 ms |
4948 KB |
Output is correct |
16 |
Correct |
17 ms |
5196 KB |
Output is correct |
17 |
Correct |
17 ms |
5184 KB |
Output is correct |
18 |
Correct |
1262 ms |
73432 KB |
Output is correct |
19 |
Correct |
1248 ms |
73364 KB |
Output is correct |
20 |
Correct |
1267 ms |
73760 KB |
Output is correct |
21 |
Correct |
1238 ms |
73144 KB |
Output is correct |
22 |
Correct |
1221 ms |
73756 KB |
Output is correct |
23 |
Correct |
1772 ms |
125624 KB |
Output is correct |
24 |
Correct |
1741 ms |
125176 KB |
Output is correct |
25 |
Correct |
1757 ms |
123192 KB |
Output is correct |
26 |
Correct |
47 ms |
5116 KB |
Output is correct |
27 |
Correct |
1030 ms |
96956 KB |
Output is correct |
28 |
Correct |
965 ms |
97252 KB |
Output is correct |
29 |
Correct |
1130 ms |
53692 KB |
Output is correct |
30 |
Correct |
1012 ms |
47056 KB |
Output is correct |
31 |
Correct |
1012 ms |
73124 KB |
Output is correct |
32 |
Correct |
750 ms |
90476 KB |
Output is correct |
33 |
Correct |
1167 ms |
98380 KB |
Output is correct |
34 |
Correct |
978 ms |
72572 KB |
Output is correct |
35 |
Correct |
41 ms |
4968 KB |
Output is correct |
36 |
Correct |
1123 ms |
92416 KB |
Output is correct |
37 |
Correct |
902 ms |
64752 KB |
Output is correct |
38 |
Correct |
793 ms |
48888 KB |
Output is correct |
39 |
Correct |
667 ms |
41064 KB |
Output is correct |
40 |
Correct |
603 ms |
29428 KB |
Output is correct |
41 |
Correct |
655 ms |
38520 KB |
Output is correct |
42 |
Correct |
579 ms |
28228 KB |
Output is correct |
43 |
Correct |
1528 ms |
8276 KB |
Output is correct |
44 |
Correct |
36 ms |
5020 KB |
Output is correct |
45 |
Correct |
160 ms |
6020 KB |
Output is correct |
46 |
Correct |
77 ms |
5956 KB |
Output is correct |
47 |
Correct |
749 ms |
8168 KB |
Output is correct |
48 |
Correct |
1481 ms |
8228 KB |
Output is correct |
49 |
Correct |
757 ms |
8248 KB |
Output is correct |
50 |
Correct |
680 ms |
6996 KB |
Output is correct |
51 |
Correct |
688 ms |
7088 KB |
Output is correct |
52 |
Correct |
694 ms |
7284 KB |
Output is correct |
53 |
Correct |
1101 ms |
7796 KB |
Output is correct |
54 |
Correct |
1096 ms |
7660 KB |
Output is correct |
55 |
Correct |
1119 ms |
7764 KB |
Output is correct |
56 |
Correct |
640 ms |
8244 KB |
Output is correct |
57 |
Correct |
702 ms |
8144 KB |
Output is correct |
58 |
Correct |
1439 ms |
8348 KB |
Output is correct |
59 |
Correct |
1515 ms |
8420 KB |
Output is correct |
60 |
Correct |
1561 ms |
8296 KB |
Output is correct |
61 |
Correct |
1507 ms |
8208 KB |
Output is correct |
62 |
Correct |
1212 ms |
7892 KB |
Output is correct |
63 |
Correct |
1257 ms |
8012 KB |
Output is correct |
64 |
Correct |
1420 ms |
8196 KB |
Output is correct |
65 |
Correct |
823 ms |
7804 KB |
Output is correct |
66 |
Correct |
1242 ms |
73544 KB |
Output is correct |
67 |
Correct |
1496 ms |
100528 KB |
Output is correct |
68 |
Correct |
1343 ms |
71652 KB |
Output is correct |
69 |
Correct |
939 ms |
29024 KB |
Output is correct |
70 |
Correct |
1451 ms |
87936 KB |
Output is correct |
71 |
Correct |
1480 ms |
90284 KB |
Output is correct |
72 |
Correct |
1491 ms |
90788 KB |
Output is correct |
73 |
Correct |
1271 ms |
71968 KB |
Output is correct |
74 |
Correct |
1278 ms |
72112 KB |
Output is correct |
75 |
Correct |
1302 ms |
72440 KB |
Output is correct |
76 |
Correct |
997 ms |
35936 KB |
Output is correct |
77 |
Correct |
985 ms |
34708 KB |
Output is correct |
78 |
Correct |
967 ms |
33160 KB |
Output is correct |
79 |
Correct |
792 ms |
19292 KB |
Output is correct |
80 |
Correct |
829 ms |
18496 KB |
Output is correct |
81 |
Correct |
855 ms |
18164 KB |
Output is correct |
82 |
Correct |
748 ms |
17664 KB |
Output is correct |
83 |
Correct |
785 ms |
17240 KB |
Output is correct |
84 |
Correct |
773 ms |
16520 KB |
Output is correct |
85 |
Correct |
1992 ms |
74648 KB |
Output is correct |
86 |
Correct |
205 ms |
12184 KB |
Output is correct |
87 |
Correct |
125 ms |
16396 KB |
Output is correct |
88 |
Correct |
1247 ms |
87460 KB |
Output is correct |
89 |
Correct |
2003 ms |
73364 KB |
Output is correct |
90 |
Correct |
1199 ms |
95168 KB |
Output is correct |
91 |
Correct |
1333 ms |
73428 KB |
Output is correct |
92 |
Correct |
1300 ms |
73204 KB |
Output is correct |
93 |
Correct |
1800 ms |
110580 KB |
Output is correct |
94 |
Correct |
1823 ms |
74332 KB |
Output is correct |
95 |
Correct |
1792 ms |
74240 KB |
Output is correct |
96 |
Correct |
2099 ms |
113852 KB |
Output is correct |
97 |
Correct |
1037 ms |
41624 KB |
Output is correct |
98 |
Correct |
1063 ms |
38360 KB |
Output is correct |
99 |
Correct |
2122 ms |
76032 KB |
Output is correct |
100 |
Correct |
1936 ms |
74944 KB |
Output is correct |
101 |
Correct |
2005 ms |
75016 KB |
Output is correct |
102 |
Correct |
2004 ms |
74964 KB |
Output is correct |
103 |
Correct |
2193 ms |
118300 KB |
Output is correct |
104 |
Correct |
2118 ms |
118392 KB |
Output is correct |
105 |
Correct |
1524 ms |
48048 KB |
Output is correct |
106 |
Correct |
1250 ms |
28268 KB |
Output is correct |
107 |
Correct |
1475 ms |
54608 KB |
Output is correct |
108 |
Correct |
2043 ms |
110316 KB |
Output is correct |
109 |
Correct |
1428 ms |
114000 KB |
Output is correct |