#pragma GCC optimize("O3")
#pragma GCC target("sse4")
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define gc getchar_unlocked()
#define pc(x) putchar_unlocked(x)
template<typename T> void scan(T &x){x = 0;bool _=0;T c=gc;_=c==45;c=_?gc:c;while(c<48||c>57)c=gc;for(;c<48||c>57;c=gc);for(;c>47&&c<58;c=gc)x=(x<<3)+(x<<1)+(c&15);x=_?-x:x;}
template<typename T> void printn(T n){bool _=0;_=n<0;n=_?-n:n;char snum[65];int i=0;do{snum[i++]=n%10+48;n/= 10;}while(n);--i;if (_)pc(45);while(i>=0)pc(snum[i--]);}
template<typename First, typename ... Ints> void scan(First &arg, Ints&... rest){scan(arg);scan(rest...);}
template<typename T> void print(T n){printn(n);pc(10);}
template<typename First, typename ... Ints> void print(First arg, Ints... rest){printn(arg);pc(32);print(rest...);}
constexpr int MM = 1e5+1, SZ = 800;
int n, m, q, a[MM], b[MM], c[MM], ans[MM], par[MM], sz[MM];
struct st{
int op, i, w, id;
bool operator<(const st &o) const{
return w > o.w;
}
} all[MM];
inline int find(int x){
while(x != par[x])
x = par[x];
return x;
}
std::vector<std::pair<int, int>> rm;
inline void merge(int x, int y, int keep){
x = find(x), y = find(y);
if(x == y)
return;
if(sz[x] > sz[y]){
int z = x;
x = y;
y = z;
}
par[x] = y;
sz[y] += sz[x];
if(!keep)
rm.emplace_back(x, y);
}
inline void pop(){
while(rm.size()){
int x = rm.back().first, y = rm.back().second;
rm.pop_back();
par[x] = x;
sz[y] -= sz[x];
}
}
inline void reset_dsu(){
for(int i = 1; i <= n; i++){
par[i] = i;
sz[i] = 1;
}
}
std::vector<int> e, ord, rmdone, yes;
bool used[MM], done[MM];
//used in this group, done in this group
int main(){
scan(n, m);
for(int i = 1; i <= m; i++)
scan(a[i], b[i], c[i]);
scan(q);
for(int i = 0; i < q; i++){
scan(all[i].op, all[i].i, all[i].w);
all[i].id = i;
}
for(int i = 0; i*SZ < q; i++){
int l = i*SZ, r = (i+1)*SZ;
if(r > q)
r = q;
std::sort(all+l, all+r);
reset_dsu();
e.clear();
ord.clear();
for(int j = l; j < r; j++){
if(all[j].op == 1)
used[all[j].i] = 1;
}
//loop edges (each one only once)
for(int j = 1; j <= m; j++){
if(used[j]) e.push_back(j); //some
else ord.push_back(j); //all
}
sort(all(ord), [](int x, int y){
return c[x] < c[y];
});
yes.clear();
for(int j = l; j < r; j++)
yes.emplace_back(j);
sort(all(yes), [](int x, int y){
return all[x].id > all[y].id;
});
//already sorted by greatest w
for(int j = l; j < r; j++){
if(all[j].op == 2){
//all (prev groups)
while(ord.size() and c[ord.back()] >= all[j].w){
int id = ord.back(); ord.pop_back();
merge(a[id], b[id], 1);
}
//specific to this group
for(int k: yes){
if(all[k].op == 1 and all[k].id < all[j].id){
int id = all[k].i;
if(!done[id]){
if(all[k].w >= all[j].w)
merge(a[id], b[id], 0);
done[id] = 1;
rmdone.emplace_back(id);
}
}
}
//some (prev groups)
for(int k: e){
if(!done[k] and c[k] >= all[j].w)
merge(a[k], b[k], 0);
}
ans[all[j].id] = sz[find(all[j].i)];
pop();
while(rmdone.size()){
done[rmdone.back()] = 0;
rmdone.pop_back();
}
}
}
for(int k = yes.size()-1; k >= 0; k--){
#define j yes[k]
if(all[j].op == 1){
used[all[j].i] = 0;
c[all[j].i] = all[j].w;
//update for future batches
}
}
}
for(int i = 0; i < q; i++){
if(ans[i])
print(ans[i]);
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
384 KB |
Output is correct |
2 |
Correct |
0 ms |
384 KB |
Output is correct |
3 |
Correct |
36 ms |
632 KB |
Output is correct |
4 |
Correct |
13 ms |
632 KB |
Output is correct |
5 |
Correct |
27 ms |
512 KB |
Output is correct |
6 |
Correct |
23 ms |
640 KB |
Output is correct |
7 |
Correct |
25 ms |
640 KB |
Output is correct |
8 |
Correct |
25 ms |
512 KB |
Output is correct |
9 |
Correct |
24 ms |
640 KB |
Output is correct |
10 |
Correct |
26 ms |
512 KB |
Output is correct |
11 |
Correct |
25 ms |
512 KB |
Output is correct |
12 |
Correct |
26 ms |
512 KB |
Output is correct |
13 |
Correct |
33 ms |
512 KB |
Output is correct |
14 |
Correct |
31 ms |
512 KB |
Output is correct |
15 |
Correct |
27 ms |
512 KB |
Output is correct |
16 |
Correct |
25 ms |
640 KB |
Output is correct |
17 |
Correct |
27 ms |
512 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1539 ms |
3756 KB |
Output is correct |
2 |
Correct |
1529 ms |
3856 KB |
Output is correct |
3 |
Correct |
1525 ms |
3828 KB |
Output is correct |
4 |
Correct |
1572 ms |
3816 KB |
Output is correct |
5 |
Correct |
1541 ms |
3828 KB |
Output is correct |
6 |
Correct |
2070 ms |
3956 KB |
Output is correct |
7 |
Correct |
2104 ms |
4468 KB |
Output is correct |
8 |
Correct |
2076 ms |
4464 KB |
Output is correct |
9 |
Correct |
91 ms |
3064 KB |
Output is correct |
10 |
Correct |
1100 ms |
4468 KB |
Output is correct |
11 |
Correct |
1052 ms |
4468 KB |
Output is correct |
12 |
Correct |
1356 ms |
4724 KB |
Output is correct |
13 |
Correct |
1279 ms |
4340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1214 ms |
3320 KB |
Output is correct |
2 |
Correct |
856 ms |
2936 KB |
Output is correct |
3 |
Correct |
1327 ms |
3448 KB |
Output is correct |
4 |
Correct |
1199 ms |
3852 KB |
Output is correct |
5 |
Correct |
102 ms |
2424 KB |
Output is correct |
6 |
Correct |
1303 ms |
3652 KB |
Output is correct |
7 |
Correct |
1105 ms |
3456 KB |
Output is correct |
8 |
Correct |
1024 ms |
3464 KB |
Output is correct |
9 |
Correct |
860 ms |
3648 KB |
Output is correct |
10 |
Correct |
818 ms |
3536 KB |
Output is correct |
11 |
Correct |
817 ms |
3380 KB |
Output is correct |
12 |
Correct |
774 ms |
3344 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2058 ms |
5064 KB |
Output is correct |
2 |
Correct |
91 ms |
2512 KB |
Output is correct |
3 |
Correct |
190 ms |
2428 KB |
Output is correct |
4 |
Correct |
70 ms |
2428 KB |
Output is correct |
5 |
Correct |
984 ms |
4952 KB |
Output is correct |
6 |
Correct |
1993 ms |
5136 KB |
Output is correct |
7 |
Correct |
1010 ms |
4988 KB |
Output is correct |
8 |
Correct |
995 ms |
3964 KB |
Output is correct |
9 |
Correct |
971 ms |
3952 KB |
Output is correct |
10 |
Correct |
989 ms |
4212 KB |
Output is correct |
11 |
Correct |
1519 ms |
4452 KB |
Output is correct |
12 |
Correct |
1476 ms |
4452 KB |
Output is correct |
13 |
Correct |
1542 ms |
4644 KB |
Output is correct |
14 |
Correct |
852 ms |
5156 KB |
Output is correct |
15 |
Correct |
919 ms |
4972 KB |
Output is correct |
16 |
Correct |
2117 ms |
4868 KB |
Output is correct |
17 |
Correct |
2130 ms |
4864 KB |
Output is correct |
18 |
Correct |
2037 ms |
4880 KB |
Output is correct |
19 |
Correct |
2122 ms |
4728 KB |
Output is correct |
20 |
Correct |
1718 ms |
4720 KB |
Output is correct |
21 |
Correct |
1748 ms |
4720 KB |
Output is correct |
22 |
Correct |
2134 ms |
5004 KB |
Output is correct |
23 |
Correct |
1123 ms |
4592 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1539 ms |
3756 KB |
Output is correct |
2 |
Correct |
1529 ms |
3856 KB |
Output is correct |
3 |
Correct |
1525 ms |
3828 KB |
Output is correct |
4 |
Correct |
1572 ms |
3816 KB |
Output is correct |
5 |
Correct |
1541 ms |
3828 KB |
Output is correct |
6 |
Correct |
2070 ms |
3956 KB |
Output is correct |
7 |
Correct |
2104 ms |
4468 KB |
Output is correct |
8 |
Correct |
2076 ms |
4464 KB |
Output is correct |
9 |
Correct |
91 ms |
3064 KB |
Output is correct |
10 |
Correct |
1100 ms |
4468 KB |
Output is correct |
11 |
Correct |
1052 ms |
4468 KB |
Output is correct |
12 |
Correct |
1356 ms |
4724 KB |
Output is correct |
13 |
Correct |
1279 ms |
4340 KB |
Output is correct |
14 |
Correct |
1214 ms |
3320 KB |
Output is correct |
15 |
Correct |
856 ms |
2936 KB |
Output is correct |
16 |
Correct |
1327 ms |
3448 KB |
Output is correct |
17 |
Correct |
1199 ms |
3852 KB |
Output is correct |
18 |
Correct |
102 ms |
2424 KB |
Output is correct |
19 |
Correct |
1303 ms |
3652 KB |
Output is correct |
20 |
Correct |
1105 ms |
3456 KB |
Output is correct |
21 |
Correct |
1024 ms |
3464 KB |
Output is correct |
22 |
Correct |
860 ms |
3648 KB |
Output is correct |
23 |
Correct |
818 ms |
3536 KB |
Output is correct |
24 |
Correct |
817 ms |
3380 KB |
Output is correct |
25 |
Correct |
774 ms |
3344 KB |
Output is correct |
26 |
Correct |
1611 ms |
4524 KB |
Output is correct |
27 |
Correct |
1857 ms |
4596 KB |
Output is correct |
28 |
Correct |
1702 ms |
4468 KB |
Output is correct |
29 |
Correct |
1346 ms |
4516 KB |
Output is correct |
30 |
Correct |
1837 ms |
4468 KB |
Output is correct |
31 |
Correct |
1856 ms |
4596 KB |
Output is correct |
32 |
Correct |
1883 ms |
4664 KB |
Output is correct |
33 |
Correct |
1618 ms |
4708 KB |
Output is correct |
34 |
Correct |
1661 ms |
4456 KB |
Output is correct |
35 |
Correct |
1650 ms |
4512 KB |
Output is correct |
36 |
Correct |
1380 ms |
4780 KB |
Output is correct |
37 |
Correct |
1359 ms |
4604 KB |
Output is correct |
38 |
Correct |
1346 ms |
4468 KB |
Output is correct |
39 |
Correct |
1180 ms |
4608 KB |
Output is correct |
40 |
Correct |
1140 ms |
4776 KB |
Output is correct |
41 |
Correct |
1153 ms |
4628 KB |
Output is correct |
42 |
Correct |
1078 ms |
4560 KB |
Output is correct |
43 |
Correct |
1046 ms |
4340 KB |
Output is correct |
44 |
Correct |
1043 ms |
4352 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
384 KB |
Output is correct |
2 |
Correct |
0 ms |
384 KB |
Output is correct |
3 |
Correct |
36 ms |
632 KB |
Output is correct |
4 |
Correct |
13 ms |
632 KB |
Output is correct |
5 |
Correct |
27 ms |
512 KB |
Output is correct |
6 |
Correct |
23 ms |
640 KB |
Output is correct |
7 |
Correct |
25 ms |
640 KB |
Output is correct |
8 |
Correct |
25 ms |
512 KB |
Output is correct |
9 |
Correct |
24 ms |
640 KB |
Output is correct |
10 |
Correct |
26 ms |
512 KB |
Output is correct |
11 |
Correct |
25 ms |
512 KB |
Output is correct |
12 |
Correct |
26 ms |
512 KB |
Output is correct |
13 |
Correct |
33 ms |
512 KB |
Output is correct |
14 |
Correct |
31 ms |
512 KB |
Output is correct |
15 |
Correct |
27 ms |
512 KB |
Output is correct |
16 |
Correct |
25 ms |
640 KB |
Output is correct |
17 |
Correct |
27 ms |
512 KB |
Output is correct |
18 |
Correct |
1539 ms |
3756 KB |
Output is correct |
19 |
Correct |
1529 ms |
3856 KB |
Output is correct |
20 |
Correct |
1525 ms |
3828 KB |
Output is correct |
21 |
Correct |
1572 ms |
3816 KB |
Output is correct |
22 |
Correct |
1541 ms |
3828 KB |
Output is correct |
23 |
Correct |
2070 ms |
3956 KB |
Output is correct |
24 |
Correct |
2104 ms |
4468 KB |
Output is correct |
25 |
Correct |
2076 ms |
4464 KB |
Output is correct |
26 |
Correct |
91 ms |
3064 KB |
Output is correct |
27 |
Correct |
1100 ms |
4468 KB |
Output is correct |
28 |
Correct |
1052 ms |
4468 KB |
Output is correct |
29 |
Correct |
1356 ms |
4724 KB |
Output is correct |
30 |
Correct |
1279 ms |
4340 KB |
Output is correct |
31 |
Correct |
1214 ms |
3320 KB |
Output is correct |
32 |
Correct |
856 ms |
2936 KB |
Output is correct |
33 |
Correct |
1327 ms |
3448 KB |
Output is correct |
34 |
Correct |
1199 ms |
3852 KB |
Output is correct |
35 |
Correct |
102 ms |
2424 KB |
Output is correct |
36 |
Correct |
1303 ms |
3652 KB |
Output is correct |
37 |
Correct |
1105 ms |
3456 KB |
Output is correct |
38 |
Correct |
1024 ms |
3464 KB |
Output is correct |
39 |
Correct |
860 ms |
3648 KB |
Output is correct |
40 |
Correct |
818 ms |
3536 KB |
Output is correct |
41 |
Correct |
817 ms |
3380 KB |
Output is correct |
42 |
Correct |
774 ms |
3344 KB |
Output is correct |
43 |
Correct |
2058 ms |
5064 KB |
Output is correct |
44 |
Correct |
91 ms |
2512 KB |
Output is correct |
45 |
Correct |
190 ms |
2428 KB |
Output is correct |
46 |
Correct |
70 ms |
2428 KB |
Output is correct |
47 |
Correct |
984 ms |
4952 KB |
Output is correct |
48 |
Correct |
1993 ms |
5136 KB |
Output is correct |
49 |
Correct |
1010 ms |
4988 KB |
Output is correct |
50 |
Correct |
995 ms |
3964 KB |
Output is correct |
51 |
Correct |
971 ms |
3952 KB |
Output is correct |
52 |
Correct |
989 ms |
4212 KB |
Output is correct |
53 |
Correct |
1519 ms |
4452 KB |
Output is correct |
54 |
Correct |
1476 ms |
4452 KB |
Output is correct |
55 |
Correct |
1542 ms |
4644 KB |
Output is correct |
56 |
Correct |
852 ms |
5156 KB |
Output is correct |
57 |
Correct |
919 ms |
4972 KB |
Output is correct |
58 |
Correct |
2117 ms |
4868 KB |
Output is correct |
59 |
Correct |
2130 ms |
4864 KB |
Output is correct |
60 |
Correct |
2037 ms |
4880 KB |
Output is correct |
61 |
Correct |
2122 ms |
4728 KB |
Output is correct |
62 |
Correct |
1718 ms |
4720 KB |
Output is correct |
63 |
Correct |
1748 ms |
4720 KB |
Output is correct |
64 |
Correct |
2134 ms |
5004 KB |
Output is correct |
65 |
Correct |
1123 ms |
4592 KB |
Output is correct |
66 |
Correct |
1611 ms |
4524 KB |
Output is correct |
67 |
Correct |
1857 ms |
4596 KB |
Output is correct |
68 |
Correct |
1702 ms |
4468 KB |
Output is correct |
69 |
Correct |
1346 ms |
4516 KB |
Output is correct |
70 |
Correct |
1837 ms |
4468 KB |
Output is correct |
71 |
Correct |
1856 ms |
4596 KB |
Output is correct |
72 |
Correct |
1883 ms |
4664 KB |
Output is correct |
73 |
Correct |
1618 ms |
4708 KB |
Output is correct |
74 |
Correct |
1661 ms |
4456 KB |
Output is correct |
75 |
Correct |
1650 ms |
4512 KB |
Output is correct |
76 |
Correct |
1380 ms |
4780 KB |
Output is correct |
77 |
Correct |
1359 ms |
4604 KB |
Output is correct |
78 |
Correct |
1346 ms |
4468 KB |
Output is correct |
79 |
Correct |
1180 ms |
4608 KB |
Output is correct |
80 |
Correct |
1140 ms |
4776 KB |
Output is correct |
81 |
Correct |
1153 ms |
4628 KB |
Output is correct |
82 |
Correct |
1078 ms |
4560 KB |
Output is correct |
83 |
Correct |
1046 ms |
4340 KB |
Output is correct |
84 |
Correct |
1043 ms |
4352 KB |
Output is correct |
85 |
Correct |
2553 ms |
5680 KB |
Output is correct |
86 |
Correct |
230 ms |
3312 KB |
Output is correct |
87 |
Correct |
108 ms |
3196 KB |
Output is correct |
88 |
Correct |
1488 ms |
5696 KB |
Output is correct |
89 |
Correct |
2591 ms |
5744 KB |
Output is correct |
90 |
Correct |
1432 ms |
5616 KB |
Output is correct |
91 |
Correct |
1663 ms |
4640 KB |
Output is correct |
92 |
Correct |
1681 ms |
4796 KB |
Output is correct |
93 |
Correct |
2262 ms |
4900 KB |
Output is correct |
94 |
Correct |
2114 ms |
5060 KB |
Output is correct |
95 |
Correct |
2089 ms |
5100 KB |
Output is correct |
96 |
Correct |
2312 ms |
5124 KB |
Output is correct |
97 |
Correct |
1183 ms |
5964 KB |
Output is correct |
98 |
Correct |
1146 ms |
5300 KB |
Output is correct |
99 |
Correct |
2572 ms |
5572 KB |
Output is correct |
100 |
Correct |
2592 ms |
5356 KB |
Output is correct |
101 |
Correct |
2634 ms |
5368 KB |
Output is correct |
102 |
Correct |
2581 ms |
5368 KB |
Output is correct |
103 |
Correct |
2485 ms |
5108 KB |
Output is correct |
104 |
Correct |
2632 ms |
7792 KB |
Output is correct |
105 |
Correct |
1958 ms |
7836 KB |
Output is correct |
106 |
Correct |
1603 ms |
7276 KB |
Output is correct |
107 |
Correct |
1981 ms |
7904 KB |
Output is correct |
108 |
Correct |
2542 ms |
8304 KB |
Output is correct |
109 |
Correct |
1744 ms |
6572 KB |
Output is correct |