#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+5, 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(){
memset(ans, -1, sizeof ans);
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();
}
}
}
reverse(all(yes));
for(int j: yes){
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 |
5 ms |
768 KB |
Output is correct |
2 |
Correct |
5 ms |
768 KB |
Output is correct |
3 |
Correct |
42 ms |
1024 KB |
Output is correct |
4 |
Correct |
14 ms |
1024 KB |
Output is correct |
5 |
Correct |
30 ms |
1024 KB |
Output is correct |
6 |
Correct |
27 ms |
1024 KB |
Output is correct |
7 |
Correct |
33 ms |
1016 KB |
Output is correct |
8 |
Correct |
29 ms |
1024 KB |
Output is correct |
9 |
Correct |
29 ms |
1024 KB |
Output is correct |
10 |
Correct |
32 ms |
1024 KB |
Output is correct |
11 |
Correct |
30 ms |
1024 KB |
Output is correct |
12 |
Correct |
31 ms |
1024 KB |
Output is correct |
13 |
Correct |
38 ms |
1024 KB |
Output is correct |
14 |
Correct |
36 ms |
1144 KB |
Output is correct |
15 |
Correct |
32 ms |
1024 KB |
Output is correct |
16 |
Correct |
29 ms |
1024 KB |
Output is correct |
17 |
Correct |
30 ms |
1024 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1505 ms |
3956 KB |
Output is correct |
2 |
Correct |
1504 ms |
6644 KB |
Output is correct |
3 |
Correct |
1504 ms |
6624 KB |
Output is correct |
4 |
Correct |
1550 ms |
6644 KB |
Output is correct |
5 |
Correct |
1562 ms |
6592 KB |
Output is correct |
6 |
Correct |
2094 ms |
6644 KB |
Output is correct |
7 |
Correct |
2082 ms |
6644 KB |
Output is correct |
8 |
Correct |
2093 ms |
6644 KB |
Output is correct |
9 |
Correct |
98 ms |
3832 KB |
Output is correct |
10 |
Correct |
1105 ms |
5620 KB |
Output is correct |
11 |
Correct |
1046 ms |
5620 KB |
Output is correct |
12 |
Correct |
1360 ms |
6748 KB |
Output is correct |
13 |
Correct |
1294 ms |
6516 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1198 ms |
3448 KB |
Output is correct |
2 |
Correct |
826 ms |
2936 KB |
Output is correct |
3 |
Correct |
1356 ms |
3704 KB |
Output is correct |
4 |
Correct |
1182 ms |
3704 KB |
Output is correct |
5 |
Correct |
99 ms |
2680 KB |
Output is correct |
6 |
Correct |
1269 ms |
3704 KB |
Output is correct |
7 |
Correct |
1114 ms |
3576 KB |
Output is correct |
8 |
Correct |
1028 ms |
3576 KB |
Output is correct |
9 |
Correct |
846 ms |
3832 KB |
Output is correct |
10 |
Correct |
811 ms |
3704 KB |
Output is correct |
11 |
Correct |
815 ms |
3576 KB |
Output is correct |
12 |
Correct |
736 ms |
3532 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2004 ms |
4904 KB |
Output is correct |
2 |
Correct |
96 ms |
2680 KB |
Output is correct |
3 |
Correct |
197 ms |
2940 KB |
Output is correct |
4 |
Correct |
75 ms |
2940 KB |
Output is correct |
5 |
Correct |
949 ms |
5084 KB |
Output is correct |
6 |
Correct |
1940 ms |
5104 KB |
Output is correct |
7 |
Correct |
953 ms |
5232 KB |
Output is correct |
8 |
Correct |
986 ms |
4084 KB |
Output is correct |
9 |
Correct |
978 ms |
4040 KB |
Output is correct |
10 |
Correct |
984 ms |
4168 KB |
Output is correct |
11 |
Correct |
1502 ms |
4592 KB |
Output is correct |
12 |
Correct |
1440 ms |
4588 KB |
Output is correct |
13 |
Correct |
1488 ms |
4720 KB |
Output is correct |
14 |
Correct |
834 ms |
5232 KB |
Output is correct |
15 |
Correct |
893 ms |
5232 KB |
Output is correct |
16 |
Correct |
1989 ms |
5072 KB |
Output is correct |
17 |
Correct |
2012 ms |
5104 KB |
Output is correct |
18 |
Correct |
1992 ms |
5104 KB |
Output is correct |
19 |
Correct |
1951 ms |
5064 KB |
Output is correct |
20 |
Correct |
1672 ms |
4976 KB |
Output is correct |
21 |
Correct |
1698 ms |
5100 KB |
Output is correct |
22 |
Correct |
1915 ms |
5112 KB |
Output is correct |
23 |
Correct |
1098 ms |
5100 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1505 ms |
3956 KB |
Output is correct |
2 |
Correct |
1504 ms |
6644 KB |
Output is correct |
3 |
Correct |
1504 ms |
6624 KB |
Output is correct |
4 |
Correct |
1550 ms |
6644 KB |
Output is correct |
5 |
Correct |
1562 ms |
6592 KB |
Output is correct |
6 |
Correct |
2094 ms |
6644 KB |
Output is correct |
7 |
Correct |
2082 ms |
6644 KB |
Output is correct |
8 |
Correct |
2093 ms |
6644 KB |
Output is correct |
9 |
Correct |
98 ms |
3832 KB |
Output is correct |
10 |
Correct |
1105 ms |
5620 KB |
Output is correct |
11 |
Correct |
1046 ms |
5620 KB |
Output is correct |
12 |
Correct |
1360 ms |
6748 KB |
Output is correct |
13 |
Correct |
1294 ms |
6516 KB |
Output is correct |
14 |
Correct |
1198 ms |
3448 KB |
Output is correct |
15 |
Correct |
826 ms |
2936 KB |
Output is correct |
16 |
Correct |
1356 ms |
3704 KB |
Output is correct |
17 |
Correct |
1182 ms |
3704 KB |
Output is correct |
18 |
Correct |
99 ms |
2680 KB |
Output is correct |
19 |
Correct |
1269 ms |
3704 KB |
Output is correct |
20 |
Correct |
1114 ms |
3576 KB |
Output is correct |
21 |
Correct |
1028 ms |
3576 KB |
Output is correct |
22 |
Correct |
846 ms |
3832 KB |
Output is correct |
23 |
Correct |
811 ms |
3704 KB |
Output is correct |
24 |
Correct |
815 ms |
3576 KB |
Output is correct |
25 |
Correct |
736 ms |
3532 KB |
Output is correct |
26 |
Correct |
1603 ms |
6620 KB |
Output is correct |
27 |
Correct |
1850 ms |
6516 KB |
Output is correct |
28 |
Correct |
1627 ms |
6772 KB |
Output is correct |
29 |
Correct |
1324 ms |
6528 KB |
Output is correct |
30 |
Correct |
1810 ms |
6516 KB |
Output is correct |
31 |
Correct |
1849 ms |
6516 KB |
Output is correct |
32 |
Correct |
1875 ms |
6484 KB |
Output is correct |
33 |
Correct |
1601 ms |
6772 KB |
Output is correct |
34 |
Correct |
1602 ms |
6900 KB |
Output is correct |
35 |
Correct |
1613 ms |
6684 KB |
Output is correct |
36 |
Correct |
1343 ms |
6528 KB |
Output is correct |
37 |
Correct |
1342 ms |
6644 KB |
Output is correct |
38 |
Correct |
1338 ms |
6516 KB |
Output is correct |
39 |
Correct |
1124 ms |
6644 KB |
Output is correct |
40 |
Correct |
1124 ms |
6772 KB |
Output is correct |
41 |
Correct |
1126 ms |
6696 KB |
Output is correct |
42 |
Correct |
1047 ms |
6400 KB |
Output is correct |
43 |
Correct |
1043 ms |
6468 KB |
Output is correct |
44 |
Correct |
1053 ms |
6472 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
768 KB |
Output is correct |
2 |
Correct |
5 ms |
768 KB |
Output is correct |
3 |
Correct |
42 ms |
1024 KB |
Output is correct |
4 |
Correct |
14 ms |
1024 KB |
Output is correct |
5 |
Correct |
30 ms |
1024 KB |
Output is correct |
6 |
Correct |
27 ms |
1024 KB |
Output is correct |
7 |
Correct |
33 ms |
1016 KB |
Output is correct |
8 |
Correct |
29 ms |
1024 KB |
Output is correct |
9 |
Correct |
29 ms |
1024 KB |
Output is correct |
10 |
Correct |
32 ms |
1024 KB |
Output is correct |
11 |
Correct |
30 ms |
1024 KB |
Output is correct |
12 |
Correct |
31 ms |
1024 KB |
Output is correct |
13 |
Correct |
38 ms |
1024 KB |
Output is correct |
14 |
Correct |
36 ms |
1144 KB |
Output is correct |
15 |
Correct |
32 ms |
1024 KB |
Output is correct |
16 |
Correct |
29 ms |
1024 KB |
Output is correct |
17 |
Correct |
30 ms |
1024 KB |
Output is correct |
18 |
Correct |
1505 ms |
3956 KB |
Output is correct |
19 |
Correct |
1504 ms |
6644 KB |
Output is correct |
20 |
Correct |
1504 ms |
6624 KB |
Output is correct |
21 |
Correct |
1550 ms |
6644 KB |
Output is correct |
22 |
Correct |
1562 ms |
6592 KB |
Output is correct |
23 |
Correct |
2094 ms |
6644 KB |
Output is correct |
24 |
Correct |
2082 ms |
6644 KB |
Output is correct |
25 |
Correct |
2093 ms |
6644 KB |
Output is correct |
26 |
Correct |
98 ms |
3832 KB |
Output is correct |
27 |
Correct |
1105 ms |
5620 KB |
Output is correct |
28 |
Correct |
1046 ms |
5620 KB |
Output is correct |
29 |
Correct |
1360 ms |
6748 KB |
Output is correct |
30 |
Correct |
1294 ms |
6516 KB |
Output is correct |
31 |
Correct |
1198 ms |
3448 KB |
Output is correct |
32 |
Correct |
826 ms |
2936 KB |
Output is correct |
33 |
Correct |
1356 ms |
3704 KB |
Output is correct |
34 |
Correct |
1182 ms |
3704 KB |
Output is correct |
35 |
Correct |
99 ms |
2680 KB |
Output is correct |
36 |
Correct |
1269 ms |
3704 KB |
Output is correct |
37 |
Correct |
1114 ms |
3576 KB |
Output is correct |
38 |
Correct |
1028 ms |
3576 KB |
Output is correct |
39 |
Correct |
846 ms |
3832 KB |
Output is correct |
40 |
Correct |
811 ms |
3704 KB |
Output is correct |
41 |
Correct |
815 ms |
3576 KB |
Output is correct |
42 |
Correct |
736 ms |
3532 KB |
Output is correct |
43 |
Correct |
2004 ms |
4904 KB |
Output is correct |
44 |
Correct |
96 ms |
2680 KB |
Output is correct |
45 |
Correct |
197 ms |
2940 KB |
Output is correct |
46 |
Correct |
75 ms |
2940 KB |
Output is correct |
47 |
Correct |
949 ms |
5084 KB |
Output is correct |
48 |
Correct |
1940 ms |
5104 KB |
Output is correct |
49 |
Correct |
953 ms |
5232 KB |
Output is correct |
50 |
Correct |
986 ms |
4084 KB |
Output is correct |
51 |
Correct |
978 ms |
4040 KB |
Output is correct |
52 |
Correct |
984 ms |
4168 KB |
Output is correct |
53 |
Correct |
1502 ms |
4592 KB |
Output is correct |
54 |
Correct |
1440 ms |
4588 KB |
Output is correct |
55 |
Correct |
1488 ms |
4720 KB |
Output is correct |
56 |
Correct |
834 ms |
5232 KB |
Output is correct |
57 |
Correct |
893 ms |
5232 KB |
Output is correct |
58 |
Correct |
1989 ms |
5072 KB |
Output is correct |
59 |
Correct |
2012 ms |
5104 KB |
Output is correct |
60 |
Correct |
1992 ms |
5104 KB |
Output is correct |
61 |
Correct |
1951 ms |
5064 KB |
Output is correct |
62 |
Correct |
1672 ms |
4976 KB |
Output is correct |
63 |
Correct |
1698 ms |
5100 KB |
Output is correct |
64 |
Correct |
1915 ms |
5112 KB |
Output is correct |
65 |
Correct |
1098 ms |
5100 KB |
Output is correct |
66 |
Correct |
1603 ms |
6620 KB |
Output is correct |
67 |
Correct |
1850 ms |
6516 KB |
Output is correct |
68 |
Correct |
1627 ms |
6772 KB |
Output is correct |
69 |
Correct |
1324 ms |
6528 KB |
Output is correct |
70 |
Correct |
1810 ms |
6516 KB |
Output is correct |
71 |
Correct |
1849 ms |
6516 KB |
Output is correct |
72 |
Correct |
1875 ms |
6484 KB |
Output is correct |
73 |
Correct |
1601 ms |
6772 KB |
Output is correct |
74 |
Correct |
1602 ms |
6900 KB |
Output is correct |
75 |
Correct |
1613 ms |
6684 KB |
Output is correct |
76 |
Correct |
1343 ms |
6528 KB |
Output is correct |
77 |
Correct |
1342 ms |
6644 KB |
Output is correct |
78 |
Correct |
1338 ms |
6516 KB |
Output is correct |
79 |
Correct |
1124 ms |
6644 KB |
Output is correct |
80 |
Correct |
1124 ms |
6772 KB |
Output is correct |
81 |
Correct |
1126 ms |
6696 KB |
Output is correct |
82 |
Correct |
1047 ms |
6400 KB |
Output is correct |
83 |
Correct |
1043 ms |
6468 KB |
Output is correct |
84 |
Correct |
1053 ms |
6472 KB |
Output is correct |
85 |
Correct |
2547 ms |
8684 KB |
Output is correct |
86 |
Correct |
237 ms |
4732 KB |
Output is correct |
87 |
Correct |
113 ms |
4732 KB |
Output is correct |
88 |
Correct |
1451 ms |
7280 KB |
Output is correct |
89 |
Correct |
2586 ms |
8688 KB |
Output is correct |
90 |
Correct |
1429 ms |
7152 KB |
Output is correct |
91 |
Correct |
1640 ms |
6520 KB |
Output is correct |
92 |
Correct |
1652 ms |
6644 KB |
Output is correct |
93 |
Correct |
2186 ms |
6520 KB |
Output is correct |
94 |
Correct |
2129 ms |
7496 KB |
Output is correct |
95 |
Correct |
2111 ms |
7668 KB |
Output is correct |
96 |
Correct |
2302 ms |
7548 KB |
Output is correct |
97 |
Correct |
1118 ms |
7280 KB |
Output is correct |
98 |
Correct |
1132 ms |
6896 KB |
Output is correct |
99 |
Correct |
2565 ms |
8504 KB |
Output is correct |
100 |
Correct |
2555 ms |
8560 KB |
Output is correct |
101 |
Correct |
2582 ms |
8592 KB |
Output is correct |
102 |
Correct |
2596 ms |
8688 KB |
Output is correct |
103 |
Correct |
2543 ms |
7920 KB |
Output is correct |
104 |
Correct |
2526 ms |
7780 KB |
Output is correct |
105 |
Correct |
1971 ms |
7676 KB |
Output is correct |
106 |
Correct |
1607 ms |
7420 KB |
Output is correct |
107 |
Correct |
1927 ms |
8048 KB |
Output is correct |
108 |
Correct |
2529 ms |
8432 KB |
Output is correct |
109 |
Correct |
1708 ms |
6636 KB |
Output is correct |