#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
using namespace std;
const int INF = 2e9;
struct UnionFind {
vector<int> root;
vector<array<int, 4>> V;
bool mode;
UnionFind(int N) {
root.resize(N);
fill(root.begin(),root.end(),-1);
mode = false;
}
int Find(int n) {
if(root[n]<0) return n;
int r = Find(root[n]);
if(!mode) root[n] = r;
return r;
}
int Merge(int x, int y) {
x = Find(x), y = Find(y);
if(x==y) return 0;
if(root[x]>root[y]) swap(x, y);
if(mode) V.push_back({x, root[x], y, root[y]});
root[x] += root[y];
root[y] = x;
return 1;
}
void rollback() {
if(V.size()==0) return;
auto it = V.back();
root[it[0]] = it[1], root[it[2]] = it[3];
V.pop_back();
}
};
int A[100005];
int B[100005];
int C[100005];
int D[100005];
array<int, 3> Query[100005];
int ans[100005];
int sB = 2000;
bool chan[100005];
int N, M;
vector<array<int, 2>> idx2;
vector<int> idx;
int id(int n) {
return lower_bound(idx.begin(),idx.end(),n)-idx.begin();
}
clock_t sttime;
void calc(int s, int e) {
int i, j;
for(i=s;i<e;i++) {
if(Query[i][0]==1) {
chan[Query[i][1]] = true;
}
}
idx.clear();
for(i=0;i<M;i++) {
if(!chan[idx2[i][1]]) idx.push_back(idx2[i][0]);
}
idx.erase(unique(idx.begin(),idx.end()),idx.end());
vector<vector<int>> V1, V2;
V1.resize(idx.size()+1);
V2.resize(idx.size()+1);
vector<int> E;
for(i=0;i<M;i++) {
if(!chan[i]) {
V1[lower_bound(idx.begin(),idx.end(),C[i])-idx.begin()].push_back(i);
}
else E.push_back(i);
}
vector<array<int, 3>> F;
for(i=s;i<e;i++) {
if(Query[i][0]==2) {
V2[lower_bound(idx.begin(),idx.end(),Query[i][2])-idx.begin()].push_back(i);
}
else F.push_back({i, Query[i][1], Query[i][2]});
}
UnionFind UF(N);
int pv = e+1, st = -1;
for(i=idx.size();i>=0;i--) {
for(int k : V1[i]) {
UF.Merge(A[k], B[k]);
pv = e+1, st = -1;
}
sort(V2[i].begin(),V2[i].end());
for(int k : V2[i]) {
if(pv > k) {
for(int v : E) {
D[v] = C[v];
}
for(j=0;j<F.size();j++) {
if(F[j][0] < k) D[F[j][1]] = F[j][2];
else {
break;
}
}
st = j;
}
else {
for(j = st; j < F.size();j++) {
if(F[j][0]<k) D[F[j][1]] = F[j][2];
else {
break;
}
}
st = j;
}
pv = k;
int sum = 0;
UF.mode = true;
for(int v : E) {
if(Query[k][2] <= D[v]) {
sum += UF.Merge(A[v], B[v]);
}
}
ans[k] = -UF.root[UF.Find(Query[k][1])];
while(sum--) {
UF.rollback();
}
UF.mode = false;
}
}
for(i=s;i<e;i++) {
if(Query[i][0]==1) C[Query[i][1]] = Query[i][2];
}
vector<array<int, 2>> V5, V6;
for(i=0;i<M;i++) {
if(idx2[i][0]==C[idx2[i][1]]) V5.push_back(idx2[i]);
else V6.push_back({C[idx2[i][1]], idx2[i][1]});
}
sort(V6.begin(),V6.end());
idx2.clear();
idx2.resize(M);
for(i=0;i+1<V5.size();i++) {
assert(V5[i][0]<=V5[i+1][0]);
}
merge(V5.begin(),V5.end(),V6.begin(),V6.end(),idx2.begin());
for(i=0;i+1<idx2.size();i++) {
assert(idx2[i][0]<=idx2[i+1][0]);
}
for(i=0;i<M;i++) chan[i] = false;
}
signed main() {
cin.sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> N >> M;
int i, j;
sttime = clock();
for(i=0;i<M;i++) {
cin >> A[i] >> B[i] >> C[i];
A[i]--, B[i]--;
}
int Q;
cin >> Q;
int cnt1 = 0;
for(i=0;i<Q;i++) {
cin >> Query[i][0] >> Query[i][1] >> Query[i][2];
Query[i][1]--;
if(Query[i][0]==1) cnt1++;
}
for(i=0;i<M;i++) idx2.push_back({C[i], i});
sort(idx2.begin(),idx2.end());
int pt = 0;
for(i=0;i<Q;i++) {
if(i-pt+1==sB||i==Q-1) {
calc(pt, i+1);
pt = i+1;
}
}
for(i=0;i<Q;i++) {
if(Query[i][0]==2) cout << ans[i] << '\n';
}
}
Compilation message
bridges.cpp: In function 'void calc(int, int)':
bridges.cpp:95:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
95 | for(j=0;j<F.size();j++) {
| ~^~~~~~~~~
bridges.cpp:104:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
104 | for(j = st; j < F.size();j++) {
| ~~^~~~~~~~~~
bridges.cpp:138:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
138 | for(i=0;i+1<V5.size();i++) {
| ~~~^~~~~~~~~~
bridges.cpp:142:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
142 | for(i=0;i+1<idx2.size();i++) {
| ~~~^~~~~~~~~~~~
bridges.cpp: In function 'int main()':
bridges.cpp:152:12: warning: unused variable 'j' [-Wunused-variable]
152 | int i, j;
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
27 ms |
624 KB |
Output is correct |
4 |
Correct |
4 ms |
468 KB |
Output is correct |
5 |
Correct |
8 ms |
520 KB |
Output is correct |
6 |
Correct |
6 ms |
468 KB |
Output is correct |
7 |
Correct |
9 ms |
468 KB |
Output is correct |
8 |
Correct |
8 ms |
468 KB |
Output is correct |
9 |
Correct |
9 ms |
468 KB |
Output is correct |
10 |
Correct |
8 ms |
468 KB |
Output is correct |
11 |
Correct |
9 ms |
540 KB |
Output is correct |
12 |
Correct |
9 ms |
548 KB |
Output is correct |
13 |
Correct |
12 ms |
468 KB |
Output is correct |
14 |
Correct |
11 ms |
544 KB |
Output is correct |
15 |
Correct |
13 ms |
536 KB |
Output is correct |
16 |
Correct |
9 ms |
468 KB |
Output is correct |
17 |
Correct |
9 ms |
468 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1837 ms |
8336 KB |
Output is correct |
2 |
Correct |
1699 ms |
8604 KB |
Output is correct |
3 |
Correct |
1684 ms |
8480 KB |
Output is correct |
4 |
Correct |
1708 ms |
8516 KB |
Output is correct |
5 |
Correct |
1818 ms |
8400 KB |
Output is correct |
6 |
Correct |
2291 ms |
8840 KB |
Output is correct |
7 |
Correct |
2168 ms |
8960 KB |
Output is correct |
8 |
Correct |
2057 ms |
8864 KB |
Output is correct |
9 |
Correct |
29 ms |
2132 KB |
Output is correct |
10 |
Correct |
1177 ms |
4900 KB |
Output is correct |
11 |
Correct |
1056 ms |
4940 KB |
Output is correct |
12 |
Correct |
1225 ms |
9132 KB |
Output is correct |
13 |
Correct |
1167 ms |
8584 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1366 ms |
6408 KB |
Output is correct |
2 |
Correct |
920 ms |
3416 KB |
Output is correct |
3 |
Correct |
1411 ms |
6460 KB |
Output is correct |
4 |
Correct |
1330 ms |
6464 KB |
Output is correct |
5 |
Correct |
37 ms |
2124 KB |
Output is correct |
6 |
Correct |
1447 ms |
6548 KB |
Output is correct |
7 |
Correct |
1222 ms |
6504 KB |
Output is correct |
8 |
Correct |
1052 ms |
6584 KB |
Output is correct |
9 |
Correct |
798 ms |
6708 KB |
Output is correct |
10 |
Correct |
706 ms |
6620 KB |
Output is correct |
11 |
Correct |
811 ms |
6276 KB |
Output is correct |
12 |
Correct |
703 ms |
6412 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1698 ms |
15096 KB |
Output is correct |
2 |
Correct |
28 ms |
2228 KB |
Output is correct |
3 |
Correct |
185 ms |
12724 KB |
Output is correct |
4 |
Correct |
61 ms |
5552 KB |
Output is correct |
5 |
Correct |
322 ms |
7120 KB |
Output is correct |
6 |
Correct |
1624 ms |
14884 KB |
Output is correct |
7 |
Correct |
328 ms |
7044 KB |
Output is correct |
8 |
Correct |
709 ms |
8708 KB |
Output is correct |
9 |
Correct |
740 ms |
8712 KB |
Output is correct |
10 |
Correct |
745 ms |
8760 KB |
Output is correct |
11 |
Correct |
1187 ms |
12048 KB |
Output is correct |
12 |
Correct |
1141 ms |
12056 KB |
Output is correct |
13 |
Correct |
1167 ms |
12252 KB |
Output is correct |
14 |
Correct |
284 ms |
7024 KB |
Output is correct |
15 |
Correct |
319 ms |
7252 KB |
Output is correct |
16 |
Correct |
1562 ms |
14848 KB |
Output is correct |
17 |
Correct |
1724 ms |
14904 KB |
Output is correct |
18 |
Correct |
1685 ms |
17040 KB |
Output is correct |
19 |
Correct |
1703 ms |
17084 KB |
Output is correct |
20 |
Correct |
1312 ms |
15476 KB |
Output is correct |
21 |
Correct |
1407 ms |
15520 KB |
Output is correct |
22 |
Correct |
1513 ms |
16756 KB |
Output is correct |
23 |
Correct |
478 ms |
8268 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1837 ms |
8336 KB |
Output is correct |
2 |
Correct |
1699 ms |
8604 KB |
Output is correct |
3 |
Correct |
1684 ms |
8480 KB |
Output is correct |
4 |
Correct |
1708 ms |
8516 KB |
Output is correct |
5 |
Correct |
1818 ms |
8400 KB |
Output is correct |
6 |
Correct |
2291 ms |
8840 KB |
Output is correct |
7 |
Correct |
2168 ms |
8960 KB |
Output is correct |
8 |
Correct |
2057 ms |
8864 KB |
Output is correct |
9 |
Correct |
29 ms |
2132 KB |
Output is correct |
10 |
Correct |
1177 ms |
4900 KB |
Output is correct |
11 |
Correct |
1056 ms |
4940 KB |
Output is correct |
12 |
Correct |
1225 ms |
9132 KB |
Output is correct |
13 |
Correct |
1167 ms |
8584 KB |
Output is correct |
14 |
Correct |
1366 ms |
6408 KB |
Output is correct |
15 |
Correct |
920 ms |
3416 KB |
Output is correct |
16 |
Correct |
1411 ms |
6460 KB |
Output is correct |
17 |
Correct |
1330 ms |
6464 KB |
Output is correct |
18 |
Correct |
37 ms |
2124 KB |
Output is correct |
19 |
Correct |
1447 ms |
6548 KB |
Output is correct |
20 |
Correct |
1222 ms |
6504 KB |
Output is correct |
21 |
Correct |
1052 ms |
6584 KB |
Output is correct |
22 |
Correct |
798 ms |
6708 KB |
Output is correct |
23 |
Correct |
706 ms |
6620 KB |
Output is correct |
24 |
Correct |
811 ms |
6276 KB |
Output is correct |
25 |
Correct |
703 ms |
6412 KB |
Output is correct |
26 |
Correct |
1810 ms |
8720 KB |
Output is correct |
27 |
Correct |
2108 ms |
9204 KB |
Output is correct |
28 |
Correct |
1936 ms |
8584 KB |
Output is correct |
29 |
Correct |
1281 ms |
8664 KB |
Output is correct |
30 |
Correct |
2177 ms |
8600 KB |
Output is correct |
31 |
Correct |
2176 ms |
8588 KB |
Output is correct |
32 |
Correct |
2153 ms |
8816 KB |
Output is correct |
33 |
Correct |
1920 ms |
8764 KB |
Output is correct |
34 |
Correct |
1894 ms |
8896 KB |
Output is correct |
35 |
Correct |
1965 ms |
8788 KB |
Output is correct |
36 |
Correct |
1355 ms |
8828 KB |
Output is correct |
37 |
Correct |
1349 ms |
8428 KB |
Output is correct |
38 |
Correct |
1322 ms |
8388 KB |
Output is correct |
39 |
Correct |
948 ms |
8588 KB |
Output is correct |
40 |
Correct |
912 ms |
8740 KB |
Output is correct |
41 |
Correct |
873 ms |
8720 KB |
Output is correct |
42 |
Correct |
949 ms |
8388 KB |
Output is correct |
43 |
Correct |
1002 ms |
8240 KB |
Output is correct |
44 |
Correct |
989 ms |
8416 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
27 ms |
624 KB |
Output is correct |
4 |
Correct |
4 ms |
468 KB |
Output is correct |
5 |
Correct |
8 ms |
520 KB |
Output is correct |
6 |
Correct |
6 ms |
468 KB |
Output is correct |
7 |
Correct |
9 ms |
468 KB |
Output is correct |
8 |
Correct |
8 ms |
468 KB |
Output is correct |
9 |
Correct |
9 ms |
468 KB |
Output is correct |
10 |
Correct |
8 ms |
468 KB |
Output is correct |
11 |
Correct |
9 ms |
540 KB |
Output is correct |
12 |
Correct |
9 ms |
548 KB |
Output is correct |
13 |
Correct |
12 ms |
468 KB |
Output is correct |
14 |
Correct |
11 ms |
544 KB |
Output is correct |
15 |
Correct |
13 ms |
536 KB |
Output is correct |
16 |
Correct |
9 ms |
468 KB |
Output is correct |
17 |
Correct |
9 ms |
468 KB |
Output is correct |
18 |
Correct |
1837 ms |
8336 KB |
Output is correct |
19 |
Correct |
1699 ms |
8604 KB |
Output is correct |
20 |
Correct |
1684 ms |
8480 KB |
Output is correct |
21 |
Correct |
1708 ms |
8516 KB |
Output is correct |
22 |
Correct |
1818 ms |
8400 KB |
Output is correct |
23 |
Correct |
2291 ms |
8840 KB |
Output is correct |
24 |
Correct |
2168 ms |
8960 KB |
Output is correct |
25 |
Correct |
2057 ms |
8864 KB |
Output is correct |
26 |
Correct |
29 ms |
2132 KB |
Output is correct |
27 |
Correct |
1177 ms |
4900 KB |
Output is correct |
28 |
Correct |
1056 ms |
4940 KB |
Output is correct |
29 |
Correct |
1225 ms |
9132 KB |
Output is correct |
30 |
Correct |
1167 ms |
8584 KB |
Output is correct |
31 |
Correct |
1366 ms |
6408 KB |
Output is correct |
32 |
Correct |
920 ms |
3416 KB |
Output is correct |
33 |
Correct |
1411 ms |
6460 KB |
Output is correct |
34 |
Correct |
1330 ms |
6464 KB |
Output is correct |
35 |
Correct |
37 ms |
2124 KB |
Output is correct |
36 |
Correct |
1447 ms |
6548 KB |
Output is correct |
37 |
Correct |
1222 ms |
6504 KB |
Output is correct |
38 |
Correct |
1052 ms |
6584 KB |
Output is correct |
39 |
Correct |
798 ms |
6708 KB |
Output is correct |
40 |
Correct |
706 ms |
6620 KB |
Output is correct |
41 |
Correct |
811 ms |
6276 KB |
Output is correct |
42 |
Correct |
703 ms |
6412 KB |
Output is correct |
43 |
Correct |
1698 ms |
15096 KB |
Output is correct |
44 |
Correct |
28 ms |
2228 KB |
Output is correct |
45 |
Correct |
185 ms |
12724 KB |
Output is correct |
46 |
Correct |
61 ms |
5552 KB |
Output is correct |
47 |
Correct |
322 ms |
7120 KB |
Output is correct |
48 |
Correct |
1624 ms |
14884 KB |
Output is correct |
49 |
Correct |
328 ms |
7044 KB |
Output is correct |
50 |
Correct |
709 ms |
8708 KB |
Output is correct |
51 |
Correct |
740 ms |
8712 KB |
Output is correct |
52 |
Correct |
745 ms |
8760 KB |
Output is correct |
53 |
Correct |
1187 ms |
12048 KB |
Output is correct |
54 |
Correct |
1141 ms |
12056 KB |
Output is correct |
55 |
Correct |
1167 ms |
12252 KB |
Output is correct |
56 |
Correct |
284 ms |
7024 KB |
Output is correct |
57 |
Correct |
319 ms |
7252 KB |
Output is correct |
58 |
Correct |
1562 ms |
14848 KB |
Output is correct |
59 |
Correct |
1724 ms |
14904 KB |
Output is correct |
60 |
Correct |
1685 ms |
17040 KB |
Output is correct |
61 |
Correct |
1703 ms |
17084 KB |
Output is correct |
62 |
Correct |
1312 ms |
15476 KB |
Output is correct |
63 |
Correct |
1407 ms |
15520 KB |
Output is correct |
64 |
Correct |
1513 ms |
16756 KB |
Output is correct |
65 |
Correct |
478 ms |
8268 KB |
Output is correct |
66 |
Correct |
1810 ms |
8720 KB |
Output is correct |
67 |
Correct |
2108 ms |
9204 KB |
Output is correct |
68 |
Correct |
1936 ms |
8584 KB |
Output is correct |
69 |
Correct |
1281 ms |
8664 KB |
Output is correct |
70 |
Correct |
2177 ms |
8600 KB |
Output is correct |
71 |
Correct |
2176 ms |
8588 KB |
Output is correct |
72 |
Correct |
2153 ms |
8816 KB |
Output is correct |
73 |
Correct |
1920 ms |
8764 KB |
Output is correct |
74 |
Correct |
1894 ms |
8896 KB |
Output is correct |
75 |
Correct |
1965 ms |
8788 KB |
Output is correct |
76 |
Correct |
1355 ms |
8828 KB |
Output is correct |
77 |
Correct |
1349 ms |
8428 KB |
Output is correct |
78 |
Correct |
1322 ms |
8388 KB |
Output is correct |
79 |
Correct |
948 ms |
8588 KB |
Output is correct |
80 |
Correct |
912 ms |
8740 KB |
Output is correct |
81 |
Correct |
873 ms |
8720 KB |
Output is correct |
82 |
Correct |
949 ms |
8388 KB |
Output is correct |
83 |
Correct |
1002 ms |
8240 KB |
Output is correct |
84 |
Correct |
989 ms |
8416 KB |
Output is correct |
85 |
Correct |
2513 ms |
17540 KB |
Output is correct |
86 |
Correct |
236 ms |
15200 KB |
Output is correct |
87 |
Correct |
85 ms |
7792 KB |
Output is correct |
88 |
Correct |
780 ms |
9592 KB |
Output is correct |
89 |
Correct |
2615 ms |
16932 KB |
Output is correct |
90 |
Correct |
852 ms |
9364 KB |
Output is correct |
91 |
Correct |
2016 ms |
11144 KB |
Output is correct |
92 |
Correct |
2041 ms |
11068 KB |
Output is correct |
93 |
Correct |
2839 ms |
11060 KB |
Output is correct |
94 |
Correct |
2161 ms |
14300 KB |
Output is correct |
95 |
Correct |
2192 ms |
14408 KB |
Output is correct |
96 |
Correct |
2150 ms |
14216 KB |
Output is correct |
97 |
Correct |
456 ms |
9528 KB |
Output is correct |
98 |
Correct |
547 ms |
9452 KB |
Output is correct |
99 |
Correct |
2580 ms |
17124 KB |
Output is correct |
100 |
Correct |
2387 ms |
17280 KB |
Output is correct |
101 |
Correct |
2434 ms |
17084 KB |
Output is correct |
102 |
Correct |
2446 ms |
17096 KB |
Output is correct |
103 |
Correct |
2232 ms |
15256 KB |
Output is correct |
104 |
Correct |
2203 ms |
15264 KB |
Output is correct |
105 |
Correct |
1592 ms |
14784 KB |
Output is correct |
106 |
Correct |
1310 ms |
13828 KB |
Output is correct |
107 |
Correct |
1511 ms |
15400 KB |
Output is correct |
108 |
Correct |
2355 ms |
16504 KB |
Output is correct |
109 |
Correct |
989 ms |
8476 KB |
Output is correct |