#include "bits/stdc++.h"
using namespace std;
#define ar array
const int B = 320;
const int N = 1e5 + 5;
int par[N], sz[N], used[N], uu[N];
signed main(){
ios::sync_with_stdio(0); cin.tie(0);
int n, m; cin>>n>>m;
vector<ar<int, 3>> e(m);
for(int i=0;i<m;i++) cin>>e[i][0]>>e[i][1]>>e[i][2];
int Q; cin>>Q;
vector<ar<int, 3>> q(Q);
vector<int> res(Q);
for(int i=0;i<Q;i++){
cin>>q[i][0]>>q[i][1]>>q[i][2];
if(q[i][0] == 1) q[i][1]--;
}
vector<int> p(m); iota(p.begin(), p.end(), 0);
sort(p.begin(), p.end(), [&](int i, int j){
return e[i][2] > e[j][2];
});
for(int b=0;b * B<Q;b++){
//~ cout<<"here"<<endl;
for(int i=1;i<=n;i++) par[i] = i, sz[i] = 1;
vector<ar<int, 2>> last;
function<int(int)> ff = [&](int x) { return (par[x] == x ? x : ff(par[x])); };
auto fmerge = [&](int a, int b, bool t){
a = ff(a), b = ff(b);
if(a == b) return;
if(sz[a] < sz[b]) swap(a, b);
par[b] = a, sz[a] += sz[b];
if(t) last.push_back({a, b});
};
function<int(int)> f = [&](int x) { return (par[x] == x ? x : par[x] = f(par[x])); };
auto merge = [&](int a, int b){
a = f(a), b = f(b);
if(a == b) return;
if(sz[a] < sz[b]) swap(a, b);
par[b] = a, sz[a] += sz[b];
};
int l = b * B, r = min(Q, (b + 1) * B);
vector<int> qq, tt;
for(int i=l;i<r;i++){
if(q[i][0] == 1){
tt.push_back(q[i][1]);
used[q[i][1]] = 1;
} else {
qq.push_back(i);
}
}
sort(tt.begin(), tt.end()); tt.erase(unique(tt.begin(), tt.end()), tt.end());
sort(qq.begin(), qq.end(), [&](int i, int j){
return (q[i][2] > q[j][2]);
});
int j=0;
for(auto i : qq){ int w = q[i][2];
while(j<m && e[p[j]][2] >= w){
if(!used[p[j]]){
merge(e[p[j]][0], e[p[j]][1]);
} j++;
}
for(int k=i-1;k>=l;k--){
if(q[k][0] != 1 || uu[q[k][1]]) continue;
uu[q[k][1]] = 1;
if(q[k][2] >= w){
fmerge(e[q[k][1]][0], e[q[k][1]][1], 1);
}
}
for(auto x : tt){
if(uu[x]) { uu[x] = 0; continue; }
if(e[x][2] >= w){
fmerge(e[x][0], e[x][1], 1);
}
}
res[i] = sz[ff(q[i][1])];
while(!last.empty()){
int a = last.back()[0], b = last.back()[1];
sz[a] -= sz[b], par[b] = b;
last.pop_back();
}
}
for(int k=l;k<r;k++){
if(q[k][0] == 1){
e[q[k][1]][2] = q[k][2];
}
}
{
vector<int> tmp;
sort(tt.begin(), tt.end(), [&](int i, int j){
return (e[i][2] > e[j][2]);
});
int l = 0, r = 0;
while(l < m || r < (int)tt.size()){
while(l < m && used[p[l]]) l++;
if(l < m && r < (int)tt.size()){
if(e[p[l]][2] > e[tt[r]][2]){
tmp.push_back(p[l++]);
} else {
tmp.push_back(tt[r++]);
}
} else if(l < m){
tmp.push_back(p[l++]);
} else if(r < (int)tt.size()){
tmp.push_back(tt[r++]);
}
}
swap(p, tmp);
//~ vector<int> t(m); iota(t.begin(), t.end(), 0);
//~ sort(t.begin(), t.end(), [&](int i, int j){
//~ return (e[i][2] > e[j][2]);
//~ });
//~ for(auto x : t) cout<<x<<" ";
//~ cout<<endl;
//~ for(auto x : p) cout<<x<<" ";
//~ cout<<endl;
}
for(auto x : tt) used[x] = 0;
}
for(int i=0;i<Q;i++){
if(q[i][0] == 2) cout<<res[i]<<"\n";
} cout<<"\n";
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
18 ms |
696 KB |
Output is correct |
4 |
Correct |
5 ms |
596 KB |
Output is correct |
5 |
Correct |
17 ms |
724 KB |
Output is correct |
6 |
Correct |
14 ms |
596 KB |
Output is correct |
7 |
Correct |
17 ms |
468 KB |
Output is correct |
8 |
Correct |
16 ms |
664 KB |
Output is correct |
9 |
Correct |
20 ms |
468 KB |
Output is correct |
10 |
Correct |
17 ms |
640 KB |
Output is correct |
11 |
Correct |
17 ms |
632 KB |
Output is correct |
12 |
Correct |
19 ms |
640 KB |
Output is correct |
13 |
Correct |
21 ms |
648 KB |
Output is correct |
14 |
Correct |
21 ms |
644 KB |
Output is correct |
15 |
Correct |
19 ms |
596 KB |
Output is correct |
16 |
Correct |
18 ms |
556 KB |
Output is correct |
17 |
Correct |
17 ms |
576 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1172 ms |
3928 KB |
Output is correct |
2 |
Correct |
1196 ms |
6664 KB |
Output is correct |
3 |
Correct |
1177 ms |
6780 KB |
Output is correct |
4 |
Correct |
1224 ms |
6740 KB |
Output is correct |
5 |
Correct |
1189 ms |
6720 KB |
Output is correct |
6 |
Correct |
1531 ms |
6728 KB |
Output is correct |
7 |
Correct |
1529 ms |
6788 KB |
Output is correct |
8 |
Correct |
1547 ms |
6768 KB |
Output is correct |
9 |
Correct |
42 ms |
3404 KB |
Output is correct |
10 |
Correct |
1081 ms |
5676 KB |
Output is correct |
11 |
Correct |
1037 ms |
5636 KB |
Output is correct |
12 |
Correct |
1057 ms |
6872 KB |
Output is correct |
13 |
Correct |
1076 ms |
6768 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
814 ms |
3184 KB |
Output is correct |
2 |
Correct |
441 ms |
3928 KB |
Output is correct |
3 |
Correct |
883 ms |
5484 KB |
Output is correct |
4 |
Correct |
799 ms |
5704 KB |
Output is correct |
5 |
Correct |
44 ms |
3408 KB |
Output is correct |
6 |
Correct |
857 ms |
5652 KB |
Output is correct |
7 |
Correct |
765 ms |
5664 KB |
Output is correct |
8 |
Correct |
730 ms |
5560 KB |
Output is correct |
9 |
Correct |
642 ms |
5832 KB |
Output is correct |
10 |
Correct |
640 ms |
5604 KB |
Output is correct |
11 |
Correct |
660 ms |
5552 KB |
Output is correct |
12 |
Correct |
611 ms |
5320 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1694 ms |
5152 KB |
Output is correct |
2 |
Correct |
48 ms |
3416 KB |
Output is correct |
3 |
Correct |
148 ms |
4632 KB |
Output is correct |
4 |
Correct |
107 ms |
4584 KB |
Output is correct |
5 |
Correct |
1453 ms |
7132 KB |
Output is correct |
6 |
Correct |
1788 ms |
7840 KB |
Output is correct |
7 |
Correct |
1412 ms |
6844 KB |
Output is correct |
8 |
Correct |
950 ms |
5656 KB |
Output is correct |
9 |
Correct |
908 ms |
5764 KB |
Output is correct |
10 |
Correct |
935 ms |
5628 KB |
Output is correct |
11 |
Correct |
1580 ms |
7028 KB |
Output is correct |
12 |
Correct |
1532 ms |
7168 KB |
Output is correct |
13 |
Correct |
1569 ms |
7092 KB |
Output is correct |
14 |
Correct |
1357 ms |
6940 KB |
Output is correct |
15 |
Correct |
1411 ms |
6900 KB |
Output is correct |
16 |
Correct |
1929 ms |
7484 KB |
Output is correct |
17 |
Correct |
1971 ms |
7604 KB |
Output is correct |
18 |
Correct |
1962 ms |
7568 KB |
Output is correct |
19 |
Correct |
1934 ms |
7560 KB |
Output is correct |
20 |
Correct |
1814 ms |
7856 KB |
Output is correct |
21 |
Correct |
1793 ms |
7852 KB |
Output is correct |
22 |
Correct |
1858 ms |
7960 KB |
Output is correct |
23 |
Correct |
1551 ms |
6916 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1172 ms |
3928 KB |
Output is correct |
2 |
Correct |
1196 ms |
6664 KB |
Output is correct |
3 |
Correct |
1177 ms |
6780 KB |
Output is correct |
4 |
Correct |
1224 ms |
6740 KB |
Output is correct |
5 |
Correct |
1189 ms |
6720 KB |
Output is correct |
6 |
Correct |
1531 ms |
6728 KB |
Output is correct |
7 |
Correct |
1529 ms |
6788 KB |
Output is correct |
8 |
Correct |
1547 ms |
6768 KB |
Output is correct |
9 |
Correct |
42 ms |
3404 KB |
Output is correct |
10 |
Correct |
1081 ms |
5676 KB |
Output is correct |
11 |
Correct |
1037 ms |
5636 KB |
Output is correct |
12 |
Correct |
1057 ms |
6872 KB |
Output is correct |
13 |
Correct |
1076 ms |
6768 KB |
Output is correct |
14 |
Correct |
814 ms |
3184 KB |
Output is correct |
15 |
Correct |
441 ms |
3928 KB |
Output is correct |
16 |
Correct |
883 ms |
5484 KB |
Output is correct |
17 |
Correct |
799 ms |
5704 KB |
Output is correct |
18 |
Correct |
44 ms |
3408 KB |
Output is correct |
19 |
Correct |
857 ms |
5652 KB |
Output is correct |
20 |
Correct |
765 ms |
5664 KB |
Output is correct |
21 |
Correct |
730 ms |
5560 KB |
Output is correct |
22 |
Correct |
642 ms |
5832 KB |
Output is correct |
23 |
Correct |
640 ms |
5604 KB |
Output is correct |
24 |
Correct |
660 ms |
5552 KB |
Output is correct |
25 |
Correct |
611 ms |
5320 KB |
Output is correct |
26 |
Correct |
1199 ms |
6152 KB |
Output is correct |
27 |
Correct |
1381 ms |
6372 KB |
Output is correct |
28 |
Correct |
1246 ms |
6240 KB |
Output is correct |
29 |
Correct |
1105 ms |
6216 KB |
Output is correct |
30 |
Correct |
1387 ms |
6312 KB |
Output is correct |
31 |
Correct |
1415 ms |
6420 KB |
Output is correct |
32 |
Correct |
1388 ms |
6528 KB |
Output is correct |
33 |
Correct |
1265 ms |
6252 KB |
Output is correct |
34 |
Correct |
1262 ms |
6028 KB |
Output is correct |
35 |
Correct |
1281 ms |
6004 KB |
Output is correct |
36 |
Correct |
1120 ms |
6272 KB |
Output is correct |
37 |
Correct |
1111 ms |
6016 KB |
Output is correct |
38 |
Correct |
1109 ms |
5872 KB |
Output is correct |
39 |
Correct |
1046 ms |
6048 KB |
Output is correct |
40 |
Correct |
1044 ms |
5880 KB |
Output is correct |
41 |
Correct |
1059 ms |
5952 KB |
Output is correct |
42 |
Correct |
944 ms |
5988 KB |
Output is correct |
43 |
Correct |
990 ms |
6000 KB |
Output is correct |
44 |
Correct |
925 ms |
5932 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
18 ms |
696 KB |
Output is correct |
4 |
Correct |
5 ms |
596 KB |
Output is correct |
5 |
Correct |
17 ms |
724 KB |
Output is correct |
6 |
Correct |
14 ms |
596 KB |
Output is correct |
7 |
Correct |
17 ms |
468 KB |
Output is correct |
8 |
Correct |
16 ms |
664 KB |
Output is correct |
9 |
Correct |
20 ms |
468 KB |
Output is correct |
10 |
Correct |
17 ms |
640 KB |
Output is correct |
11 |
Correct |
17 ms |
632 KB |
Output is correct |
12 |
Correct |
19 ms |
640 KB |
Output is correct |
13 |
Correct |
21 ms |
648 KB |
Output is correct |
14 |
Correct |
21 ms |
644 KB |
Output is correct |
15 |
Correct |
19 ms |
596 KB |
Output is correct |
16 |
Correct |
18 ms |
556 KB |
Output is correct |
17 |
Correct |
17 ms |
576 KB |
Output is correct |
18 |
Correct |
1172 ms |
3928 KB |
Output is correct |
19 |
Correct |
1196 ms |
6664 KB |
Output is correct |
20 |
Correct |
1177 ms |
6780 KB |
Output is correct |
21 |
Correct |
1224 ms |
6740 KB |
Output is correct |
22 |
Correct |
1189 ms |
6720 KB |
Output is correct |
23 |
Correct |
1531 ms |
6728 KB |
Output is correct |
24 |
Correct |
1529 ms |
6788 KB |
Output is correct |
25 |
Correct |
1547 ms |
6768 KB |
Output is correct |
26 |
Correct |
42 ms |
3404 KB |
Output is correct |
27 |
Correct |
1081 ms |
5676 KB |
Output is correct |
28 |
Correct |
1037 ms |
5636 KB |
Output is correct |
29 |
Correct |
1057 ms |
6872 KB |
Output is correct |
30 |
Correct |
1076 ms |
6768 KB |
Output is correct |
31 |
Correct |
814 ms |
3184 KB |
Output is correct |
32 |
Correct |
441 ms |
3928 KB |
Output is correct |
33 |
Correct |
883 ms |
5484 KB |
Output is correct |
34 |
Correct |
799 ms |
5704 KB |
Output is correct |
35 |
Correct |
44 ms |
3408 KB |
Output is correct |
36 |
Correct |
857 ms |
5652 KB |
Output is correct |
37 |
Correct |
765 ms |
5664 KB |
Output is correct |
38 |
Correct |
730 ms |
5560 KB |
Output is correct |
39 |
Correct |
642 ms |
5832 KB |
Output is correct |
40 |
Correct |
640 ms |
5604 KB |
Output is correct |
41 |
Correct |
660 ms |
5552 KB |
Output is correct |
42 |
Correct |
611 ms |
5320 KB |
Output is correct |
43 |
Correct |
1694 ms |
5152 KB |
Output is correct |
44 |
Correct |
48 ms |
3416 KB |
Output is correct |
45 |
Correct |
148 ms |
4632 KB |
Output is correct |
46 |
Correct |
107 ms |
4584 KB |
Output is correct |
47 |
Correct |
1453 ms |
7132 KB |
Output is correct |
48 |
Correct |
1788 ms |
7840 KB |
Output is correct |
49 |
Correct |
1412 ms |
6844 KB |
Output is correct |
50 |
Correct |
950 ms |
5656 KB |
Output is correct |
51 |
Correct |
908 ms |
5764 KB |
Output is correct |
52 |
Correct |
935 ms |
5628 KB |
Output is correct |
53 |
Correct |
1580 ms |
7028 KB |
Output is correct |
54 |
Correct |
1532 ms |
7168 KB |
Output is correct |
55 |
Correct |
1569 ms |
7092 KB |
Output is correct |
56 |
Correct |
1357 ms |
6940 KB |
Output is correct |
57 |
Correct |
1411 ms |
6900 KB |
Output is correct |
58 |
Correct |
1929 ms |
7484 KB |
Output is correct |
59 |
Correct |
1971 ms |
7604 KB |
Output is correct |
60 |
Correct |
1962 ms |
7568 KB |
Output is correct |
61 |
Correct |
1934 ms |
7560 KB |
Output is correct |
62 |
Correct |
1814 ms |
7856 KB |
Output is correct |
63 |
Correct |
1793 ms |
7852 KB |
Output is correct |
64 |
Correct |
1858 ms |
7960 KB |
Output is correct |
65 |
Correct |
1551 ms |
6916 KB |
Output is correct |
66 |
Correct |
1199 ms |
6152 KB |
Output is correct |
67 |
Correct |
1381 ms |
6372 KB |
Output is correct |
68 |
Correct |
1246 ms |
6240 KB |
Output is correct |
69 |
Correct |
1105 ms |
6216 KB |
Output is correct |
70 |
Correct |
1387 ms |
6312 KB |
Output is correct |
71 |
Correct |
1415 ms |
6420 KB |
Output is correct |
72 |
Correct |
1388 ms |
6528 KB |
Output is correct |
73 |
Correct |
1265 ms |
6252 KB |
Output is correct |
74 |
Correct |
1262 ms |
6028 KB |
Output is correct |
75 |
Correct |
1281 ms |
6004 KB |
Output is correct |
76 |
Correct |
1120 ms |
6272 KB |
Output is correct |
77 |
Correct |
1111 ms |
6016 KB |
Output is correct |
78 |
Correct |
1109 ms |
5872 KB |
Output is correct |
79 |
Correct |
1046 ms |
6048 KB |
Output is correct |
80 |
Correct |
1044 ms |
5880 KB |
Output is correct |
81 |
Correct |
1059 ms |
5952 KB |
Output is correct |
82 |
Correct |
944 ms |
5988 KB |
Output is correct |
83 |
Correct |
990 ms |
6000 KB |
Output is correct |
84 |
Correct |
925 ms |
5932 KB |
Output is correct |
85 |
Correct |
2055 ms |
9860 KB |
Output is correct |
86 |
Correct |
180 ms |
5804 KB |
Output is correct |
87 |
Correct |
132 ms |
5968 KB |
Output is correct |
88 |
Correct |
1745 ms |
8488 KB |
Output is correct |
89 |
Correct |
2060 ms |
10028 KB |
Output is correct |
90 |
Correct |
1717 ms |
8084 KB |
Output is correct |
91 |
Correct |
1298 ms |
6604 KB |
Output is correct |
92 |
Correct |
1274 ms |
6720 KB |
Output is correct |
93 |
Correct |
1559 ms |
6748 KB |
Output is correct |
94 |
Correct |
1942 ms |
8376 KB |
Output is correct |
95 |
Correct |
1857 ms |
8664 KB |
Output is correct |
96 |
Correct |
1992 ms |
8252 KB |
Output is correct |
97 |
Correct |
1601 ms |
7832 KB |
Output is correct |
98 |
Correct |
1618 ms |
7716 KB |
Output is correct |
99 |
Correct |
2232 ms |
9916 KB |
Output is correct |
100 |
Correct |
2234 ms |
9788 KB |
Output is correct |
101 |
Correct |
2280 ms |
9756 KB |
Output is correct |
102 |
Correct |
2225 ms |
9988 KB |
Output is correct |
103 |
Correct |
2176 ms |
8612 KB |
Output is correct |
104 |
Correct |
2145 ms |
8572 KB |
Output is correct |
105 |
Correct |
1984 ms |
8168 KB |
Output is correct |
106 |
Correct |
1686 ms |
8128 KB |
Output is correct |
107 |
Correct |
1927 ms |
8436 KB |
Output is correct |
108 |
Correct |
2108 ms |
9392 KB |
Output is correct |
109 |
Correct |
1859 ms |
7308 KB |
Output is correct |