#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
#define ep emplace
#define eb emplace_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef pair<int,int>pi;
typedef pair<ll,ll>pl;
const int inf=1e9+7;
const ll INF=1e18+7;
const int siz=500;
int pa[50010],sz[50010];
int par(int x)
{
while(pa[x]!=0)
x=pa[x];
return x;
}
vector<pi>rbv;
inline void uni(int x,int y,bool rbf)
{
x=par(x);
y=par(y);
if(x==y)
return;
if(sz[x]>sz[y])
swap(x,y);
if(rbf)
rbv.eb(x,0),rbv.eb(y,sz[y]);
pa[x]=y;
sz[y]+=sz[x];
return;
}
inline void init(int n)
{
fill(pa+1,pa+n+1,0);
fill(sz+1,sz+n+1,1);
return;
}
inline void rb(pi&x)
{
(x.se==0?pa[x.fi]:sz[x.fi])=x.se;
return;
}
inline void rb()
{
reverse(all(rbv));
for(pi&t:rbv)
rb(t);
rbv.clear();
return;
}
int eu[100010],ev[100010],ed[100010];
vector<int>edge;
bool chk[100010];
int n,m,q;
inline void solve(vector<pair<int,pi> >&v)
{
fill(chk+1,chk+m+1,0);
init(n);
vector<int>change;
for(auto&t:v)
if(t.fi==1)
chk[t.se.fi]=1,change.eb(t.se.fi);
sort(all(change));
change.erase(unique(all(change)),change.end());
int C=0;
multimap<int,pair<pi,vector<int> >,greater<int> >mp;
for(auto&tq:v)
{
if(tq.fi==1)
ed[tq.se.fi]=tq.se.se;
else
{
vector<int>qv;
for(int&te:change)
if(ed[te]>=tq.se.se)
qv.eb(te);
mp.ep(tq.se.se,make_pair(pi(tq.se.fi,C),qv));
C++;
}
}
v.clear();
vector<int>ans(C);
vector<int>cur;
for(int&t:edge)
if(!chk[t])
cur.eb(t);
int vi=0;
for(auto&tq:mp)
{
while(vi<(int)cur.size()&&ed[cur[vi]]>=tq.fi)
uni(eu[cur[vi]],ev[cur[vi]],0),vi++;
for(int&tv:tq.se.se)
uni(eu[tv],ev[tv],1);
ans[tq.se.fi.se]=sz[par(tq.se.fi.fi)];
rb();
}
sort(all(change),[=](int&x,int&y){return ed[x]>ed[y];});
int ai=0,bi=0;
edge.clear();
while(ai<(int)change.size()&&bi<(int)cur.size())
{
if(ed[change[ai]]>ed[cur[bi]])
edge.eb(change[ai]),ai++;
else
edge.eb(cur[bi]),bi++;
}
while(ai<(int)change.size())
edge.eb(change[ai]),ai++;
while(bi<(int)cur.size())
edge.eb(cur[bi]),bi++;
for(int&t:ans)
cout<<t<<'\n';
return;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin>>n>>m;
for(int i=0;i++<m;)
cin>>eu[i]>>ev[i]>>ed[i],edge.eb(i);
sort(all(edge),[=](int&x,int&y){return ed[x]>ed[y];});
cin>>q;
vector<pair<int,pi> >qv;
while(q-->0)
{
int t,u,v;
cin>>t>>u>>v;
qv.eb(t,pi(u,v));
if((int)qv.size()>siz)
solve(qv);
}
if(!qv.empty())
solve(qv);
cout.flush();
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
384 KB |
Output is correct |
2 |
Correct |
4 ms |
384 KB |
Output is correct |
3 |
Correct |
28 ms |
640 KB |
Output is correct |
4 |
Correct |
9 ms |
512 KB |
Output is correct |
5 |
Correct |
18 ms |
640 KB |
Output is correct |
6 |
Correct |
17 ms |
640 KB |
Output is correct |
7 |
Correct |
20 ms |
512 KB |
Output is correct |
8 |
Correct |
21 ms |
640 KB |
Output is correct |
9 |
Correct |
23 ms |
640 KB |
Output is correct |
10 |
Correct |
21 ms |
640 KB |
Output is correct |
11 |
Correct |
21 ms |
640 KB |
Output is correct |
12 |
Correct |
24 ms |
640 KB |
Output is correct |
13 |
Correct |
26 ms |
640 KB |
Output is correct |
14 |
Correct |
24 ms |
640 KB |
Output is correct |
15 |
Correct |
23 ms |
640 KB |
Output is correct |
16 |
Correct |
22 ms |
640 KB |
Output is correct |
17 |
Correct |
22 ms |
512 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
900 ms |
4020 KB |
Output is correct |
2 |
Correct |
859 ms |
5108 KB |
Output is correct |
3 |
Correct |
875 ms |
5132 KB |
Output is correct |
4 |
Correct |
865 ms |
5176 KB |
Output is correct |
5 |
Correct |
873 ms |
5316 KB |
Output is correct |
6 |
Correct |
1217 ms |
5292 KB |
Output is correct |
7 |
Correct |
1208 ms |
5316 KB |
Output is correct |
8 |
Correct |
1227 ms |
5300 KB |
Output is correct |
9 |
Correct |
55 ms |
1912 KB |
Output is correct |
10 |
Correct |
900 ms |
4152 KB |
Output is correct |
11 |
Correct |
852 ms |
4316 KB |
Output is correct |
12 |
Correct |
774 ms |
5308 KB |
Output is correct |
13 |
Correct |
735 ms |
4924 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
750 ms |
3256 KB |
Output is correct |
2 |
Correct |
534 ms |
2552 KB |
Output is correct |
3 |
Correct |
804 ms |
4188 KB |
Output is correct |
4 |
Correct |
697 ms |
4304 KB |
Output is correct |
5 |
Correct |
52 ms |
1916 KB |
Output is correct |
6 |
Correct |
770 ms |
4100 KB |
Output is correct |
7 |
Correct |
644 ms |
4148 KB |
Output is correct |
8 |
Correct |
566 ms |
4124 KB |
Output is correct |
9 |
Correct |
491 ms |
4092 KB |
Output is correct |
10 |
Correct |
473 ms |
4116 KB |
Output is correct |
11 |
Correct |
529 ms |
3852 KB |
Output is correct |
12 |
Correct |
431 ms |
3836 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1174 ms |
3960 KB |
Output is correct |
2 |
Correct |
54 ms |
632 KB |
Output is correct |
3 |
Correct |
127 ms |
3060 KB |
Output is correct |
4 |
Correct |
111 ms |
3120 KB |
Output is correct |
5 |
Correct |
960 ms |
3920 KB |
Output is correct |
6 |
Correct |
1135 ms |
4032 KB |
Output is correct |
7 |
Correct |
941 ms |
3924 KB |
Output is correct |
8 |
Correct |
528 ms |
2360 KB |
Output is correct |
9 |
Correct |
539 ms |
2384 KB |
Output is correct |
10 |
Correct |
524 ms |
2592 KB |
Output is correct |
11 |
Correct |
879 ms |
3304 KB |
Output is correct |
12 |
Correct |
835 ms |
3284 KB |
Output is correct |
13 |
Correct |
891 ms |
3500 KB |
Output is correct |
14 |
Correct |
947 ms |
4136 KB |
Output is correct |
15 |
Correct |
953 ms |
4064 KB |
Output is correct |
16 |
Correct |
1168 ms |
4108 KB |
Output is correct |
17 |
Correct |
1189 ms |
4056 KB |
Output is correct |
18 |
Correct |
1193 ms |
3972 KB |
Output is correct |
19 |
Correct |
1214 ms |
4168 KB |
Output is correct |
20 |
Correct |
1038 ms |
3968 KB |
Output is correct |
21 |
Correct |
1026 ms |
3952 KB |
Output is correct |
22 |
Correct |
1155 ms |
4176 KB |
Output is correct |
23 |
Correct |
933 ms |
3704 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
900 ms |
4020 KB |
Output is correct |
2 |
Correct |
859 ms |
5108 KB |
Output is correct |
3 |
Correct |
875 ms |
5132 KB |
Output is correct |
4 |
Correct |
865 ms |
5176 KB |
Output is correct |
5 |
Correct |
873 ms |
5316 KB |
Output is correct |
6 |
Correct |
1217 ms |
5292 KB |
Output is correct |
7 |
Correct |
1208 ms |
5316 KB |
Output is correct |
8 |
Correct |
1227 ms |
5300 KB |
Output is correct |
9 |
Correct |
55 ms |
1912 KB |
Output is correct |
10 |
Correct |
900 ms |
4152 KB |
Output is correct |
11 |
Correct |
852 ms |
4316 KB |
Output is correct |
12 |
Correct |
774 ms |
5308 KB |
Output is correct |
13 |
Correct |
735 ms |
4924 KB |
Output is correct |
14 |
Correct |
750 ms |
3256 KB |
Output is correct |
15 |
Correct |
534 ms |
2552 KB |
Output is correct |
16 |
Correct |
804 ms |
4188 KB |
Output is correct |
17 |
Correct |
697 ms |
4304 KB |
Output is correct |
18 |
Correct |
52 ms |
1916 KB |
Output is correct |
19 |
Correct |
770 ms |
4100 KB |
Output is correct |
20 |
Correct |
644 ms |
4148 KB |
Output is correct |
21 |
Correct |
566 ms |
4124 KB |
Output is correct |
22 |
Correct |
491 ms |
4092 KB |
Output is correct |
23 |
Correct |
473 ms |
4116 KB |
Output is correct |
24 |
Correct |
529 ms |
3852 KB |
Output is correct |
25 |
Correct |
431 ms |
3836 KB |
Output is correct |
26 |
Correct |
957 ms |
5396 KB |
Output is correct |
27 |
Correct |
1110 ms |
5340 KB |
Output is correct |
28 |
Correct |
979 ms |
5300 KB |
Output is correct |
29 |
Correct |
717 ms |
5192 KB |
Output is correct |
30 |
Correct |
1052 ms |
5052 KB |
Output is correct |
31 |
Correct |
1079 ms |
5160 KB |
Output is correct |
32 |
Correct |
1087 ms |
5420 KB |
Output is correct |
33 |
Correct |
935 ms |
5452 KB |
Output is correct |
34 |
Correct |
944 ms |
5244 KB |
Output is correct |
35 |
Correct |
961 ms |
5192 KB |
Output is correct |
36 |
Correct |
734 ms |
5304 KB |
Output is correct |
37 |
Correct |
760 ms |
5124 KB |
Output is correct |
38 |
Correct |
727 ms |
5244 KB |
Output is correct |
39 |
Correct |
615 ms |
5104 KB |
Output is correct |
40 |
Correct |
623 ms |
5120 KB |
Output is correct |
41 |
Correct |
618 ms |
5288 KB |
Output is correct |
42 |
Correct |
576 ms |
5148 KB |
Output is correct |
43 |
Correct |
569 ms |
4848 KB |
Output is correct |
44 |
Correct |
564 ms |
5108 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
384 KB |
Output is correct |
2 |
Correct |
4 ms |
384 KB |
Output is correct |
3 |
Correct |
28 ms |
640 KB |
Output is correct |
4 |
Correct |
9 ms |
512 KB |
Output is correct |
5 |
Correct |
18 ms |
640 KB |
Output is correct |
6 |
Correct |
17 ms |
640 KB |
Output is correct |
7 |
Correct |
20 ms |
512 KB |
Output is correct |
8 |
Correct |
21 ms |
640 KB |
Output is correct |
9 |
Correct |
23 ms |
640 KB |
Output is correct |
10 |
Correct |
21 ms |
640 KB |
Output is correct |
11 |
Correct |
21 ms |
640 KB |
Output is correct |
12 |
Correct |
24 ms |
640 KB |
Output is correct |
13 |
Correct |
26 ms |
640 KB |
Output is correct |
14 |
Correct |
24 ms |
640 KB |
Output is correct |
15 |
Correct |
23 ms |
640 KB |
Output is correct |
16 |
Correct |
22 ms |
640 KB |
Output is correct |
17 |
Correct |
22 ms |
512 KB |
Output is correct |
18 |
Correct |
900 ms |
4020 KB |
Output is correct |
19 |
Correct |
859 ms |
5108 KB |
Output is correct |
20 |
Correct |
875 ms |
5132 KB |
Output is correct |
21 |
Correct |
865 ms |
5176 KB |
Output is correct |
22 |
Correct |
873 ms |
5316 KB |
Output is correct |
23 |
Correct |
1217 ms |
5292 KB |
Output is correct |
24 |
Correct |
1208 ms |
5316 KB |
Output is correct |
25 |
Correct |
1227 ms |
5300 KB |
Output is correct |
26 |
Correct |
55 ms |
1912 KB |
Output is correct |
27 |
Correct |
900 ms |
4152 KB |
Output is correct |
28 |
Correct |
852 ms |
4316 KB |
Output is correct |
29 |
Correct |
774 ms |
5308 KB |
Output is correct |
30 |
Correct |
735 ms |
4924 KB |
Output is correct |
31 |
Correct |
750 ms |
3256 KB |
Output is correct |
32 |
Correct |
534 ms |
2552 KB |
Output is correct |
33 |
Correct |
804 ms |
4188 KB |
Output is correct |
34 |
Correct |
697 ms |
4304 KB |
Output is correct |
35 |
Correct |
52 ms |
1916 KB |
Output is correct |
36 |
Correct |
770 ms |
4100 KB |
Output is correct |
37 |
Correct |
644 ms |
4148 KB |
Output is correct |
38 |
Correct |
566 ms |
4124 KB |
Output is correct |
39 |
Correct |
491 ms |
4092 KB |
Output is correct |
40 |
Correct |
473 ms |
4116 KB |
Output is correct |
41 |
Correct |
529 ms |
3852 KB |
Output is correct |
42 |
Correct |
431 ms |
3836 KB |
Output is correct |
43 |
Correct |
1174 ms |
3960 KB |
Output is correct |
44 |
Correct |
54 ms |
632 KB |
Output is correct |
45 |
Correct |
127 ms |
3060 KB |
Output is correct |
46 |
Correct |
111 ms |
3120 KB |
Output is correct |
47 |
Correct |
960 ms |
3920 KB |
Output is correct |
48 |
Correct |
1135 ms |
4032 KB |
Output is correct |
49 |
Correct |
941 ms |
3924 KB |
Output is correct |
50 |
Correct |
528 ms |
2360 KB |
Output is correct |
51 |
Correct |
539 ms |
2384 KB |
Output is correct |
52 |
Correct |
524 ms |
2592 KB |
Output is correct |
53 |
Correct |
879 ms |
3304 KB |
Output is correct |
54 |
Correct |
835 ms |
3284 KB |
Output is correct |
55 |
Correct |
891 ms |
3500 KB |
Output is correct |
56 |
Correct |
947 ms |
4136 KB |
Output is correct |
57 |
Correct |
953 ms |
4064 KB |
Output is correct |
58 |
Correct |
1168 ms |
4108 KB |
Output is correct |
59 |
Correct |
1189 ms |
4056 KB |
Output is correct |
60 |
Correct |
1193 ms |
3972 KB |
Output is correct |
61 |
Correct |
1214 ms |
4168 KB |
Output is correct |
62 |
Correct |
1038 ms |
3968 KB |
Output is correct |
63 |
Correct |
1026 ms |
3952 KB |
Output is correct |
64 |
Correct |
1155 ms |
4176 KB |
Output is correct |
65 |
Correct |
933 ms |
3704 KB |
Output is correct |
66 |
Correct |
957 ms |
5396 KB |
Output is correct |
67 |
Correct |
1110 ms |
5340 KB |
Output is correct |
68 |
Correct |
979 ms |
5300 KB |
Output is correct |
69 |
Correct |
717 ms |
5192 KB |
Output is correct |
70 |
Correct |
1052 ms |
5052 KB |
Output is correct |
71 |
Correct |
1079 ms |
5160 KB |
Output is correct |
72 |
Correct |
1087 ms |
5420 KB |
Output is correct |
73 |
Correct |
935 ms |
5452 KB |
Output is correct |
74 |
Correct |
944 ms |
5244 KB |
Output is correct |
75 |
Correct |
961 ms |
5192 KB |
Output is correct |
76 |
Correct |
734 ms |
5304 KB |
Output is correct |
77 |
Correct |
760 ms |
5124 KB |
Output is correct |
78 |
Correct |
727 ms |
5244 KB |
Output is correct |
79 |
Correct |
615 ms |
5104 KB |
Output is correct |
80 |
Correct |
623 ms |
5120 KB |
Output is correct |
81 |
Correct |
618 ms |
5288 KB |
Output is correct |
82 |
Correct |
576 ms |
5148 KB |
Output is correct |
83 |
Correct |
569 ms |
4848 KB |
Output is correct |
84 |
Correct |
564 ms |
5108 KB |
Output is correct |
85 |
Correct |
1477 ms |
8132 KB |
Output is correct |
86 |
Correct |
148 ms |
5036 KB |
Output is correct |
87 |
Correct |
134 ms |
5252 KB |
Output is correct |
88 |
Correct |
1285 ms |
6588 KB |
Output is correct |
89 |
Correct |
1456 ms |
7840 KB |
Output is correct |
90 |
Correct |
1323 ms |
6496 KB |
Output is correct |
91 |
Correct |
971 ms |
5196 KB |
Output is correct |
92 |
Correct |
976 ms |
5284 KB |
Output is correct |
93 |
Correct |
1275 ms |
5296 KB |
Output is correct |
94 |
Correct |
1250 ms |
6496 KB |
Output is correct |
95 |
Correct |
1214 ms |
6616 KB |
Output is correct |
96 |
Correct |
1325 ms |
6540 KB |
Output is correct |
97 |
Correct |
1082 ms |
6244 KB |
Output is correct |
98 |
Correct |
1122 ms |
6096 KB |
Output is correct |
99 |
Correct |
1489 ms |
7752 KB |
Output is correct |
100 |
Correct |
1518 ms |
7824 KB |
Output is correct |
101 |
Correct |
1526 ms |
7932 KB |
Output is correct |
102 |
Correct |
1527 ms |
7792 KB |
Output is correct |
103 |
Correct |
1507 ms |
7172 KB |
Output is correct |
104 |
Correct |
1507 ms |
7296 KB |
Output is correct |
105 |
Correct |
1193 ms |
6544 KB |
Output is correct |
106 |
Correct |
992 ms |
6348 KB |
Output is correct |
107 |
Correct |
1170 ms |
6928 KB |
Output is correct |
108 |
Correct |
1476 ms |
7792 KB |
Output is correct |
109 |
Correct |
1250 ms |
5728 KB |
Output is correct |