//by szh
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pii pair<int,int>
#define pll pair<long long,long long>
#define pb push_back
#define debug(x) cerr<<#x<<"="<<x<<endl
#define pq priority_queue
#define inf 0x3f
#define rep(i,a,b) for (int i=a;i<(b);i++)
#define MP make_pair
#define SZ(x) (int(x.size()))
#define ll long long
#define mod 1000000007
#define ALL(x) x.begin(),x.end()
void inc(int &a,int b) {a=(a+b)%mod;}
void dec(int &a,int b) {a=(a-b+mod)%mod;}
int lowbit(int x) {return x&(-x);}
ll p0w(ll base,ll p) {ll ret=1;while(p>0){if (p%2ll==1ll) ret=ret*base%mod;base=base*base%mod;p/=2ll;}return ret;}
const int maxn = 1e6+10;
int n,m,Q;
vector <pii> edge;
vector <pair<pii,int>> upd[maxn],q[maxn];
int ans[maxn];
vector <pii> change[maxn];
int f[maxn],sz[maxn];
vector <pair<int,pii>> hist;
int val[maxn];
int getf(int x) {
if (f[x]==x) return x;
else return getf(f[x]);
}
void merge(int u,int v,bool redo) {
int fu = getf(u),fv = getf(v);
if (fu==fv) return;
if (sz[fu]>sz[fv]) swap(fu,fv);
if (redo) hist.pb({fu,{fv,sz[fv]}});
f[fu] = fv;
sz[fv] += sz[fu];
}
bool cmp(int x,int y) {
return val[x]<val[y];
}
bool cmpp(pair<pii,int> x,pair<pii,int> y) {
return x.fi.se>y.fi.se;
}
void redoo() {
while (!hist.empty()) {
auto tmp = hist.back();
hist.pop_back();
f[tmp.fi]=tmp.fi;
sz[tmp.se.fi] = tmp.se.se;
}
}
void solve(int cur) {
rep(i,1,n+1) f[i] = i,sz[i] = 1;
for (auto i:upd[cur]) change[i.fi.fi].pb({i.se,i.fi.se});
vector <int> samedge,difedge;
rep(i,0,m) {
if (SZ(change[i])==0) samedge.pb(i);
else difedge.pb(i);
}
sort(ALL(samedge),cmp);
sort(ALL(q[cur]),cmpp);
for (auto i:q[cur]) {
while (!samedge.empty() and val[samedge.back()]>=i.fi.se) {
int idx = samedge.back();
samedge.pop_back();
merge(edge[idx].fi,edge[idx].se,false);
}
for (int j:difedge) {
int curval = val[j];
rep(k,0,SZ(change[j])) {
if (change[j][k].fi>i.se) break;
curval = change[j][k].se;
}
if (curval>=i.fi.se) merge(edge[j].fi,edge[j].se,true);
}
ans[i.se] = sz[getf(i.fi.fi)];
redoo();
}
for (int j:difedge) {
val[j] = change[j].back().se;
while (!change[j].empty()) change[j].pop_back();
}
}
int main() {
// freopen("input.txt","r",stdin);
memset(ans,-1,sizeof(ans));
std::ios::sync_with_stdio(false);cin.tie(0);
cin>>n>>m;
rep(i,0,m) {
int u,v,w;
cin>>u>>v>>w;
edge.pb({u,v});
val[i] = w;
}
cin>>Q;
int sz = (int)sqrt(m*log(n)/log(2));
if (sz==0) sz=1;
debug(sz);
rep(i,0,Q) {
int op,x,y;
cin>>op>>x>>y;
if (op==1) {
x--;
upd[i/sz].pb({{x,y},i});
}
else q[i/sz].pb({{x,y},i});
}
rep(i,0,(Q-1)/sz+1) solve(i);
rep(i,0,Q) {
if (ans[i]!=-1) cout<<ans[i]<<"\n";
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
37 ms |
74612 KB |
Output is correct |
2 |
Correct |
37 ms |
74700 KB |
Output is correct |
3 |
Correct |
54 ms |
75096 KB |
Output is correct |
4 |
Correct |
40 ms |
75144 KB |
Output is correct |
5 |
Correct |
51 ms |
75028 KB |
Output is correct |
6 |
Correct |
46 ms |
75036 KB |
Output is correct |
7 |
Correct |
43 ms |
74944 KB |
Output is correct |
8 |
Correct |
44 ms |
74928 KB |
Output is correct |
9 |
Correct |
47 ms |
74920 KB |
Output is correct |
10 |
Correct |
48 ms |
75020 KB |
Output is correct |
11 |
Correct |
46 ms |
75032 KB |
Output is correct |
12 |
Correct |
45 ms |
75016 KB |
Output is correct |
13 |
Correct |
46 ms |
75044 KB |
Output is correct |
14 |
Correct |
46 ms |
74996 KB |
Output is correct |
15 |
Correct |
49 ms |
75032 KB |
Output is correct |
16 |
Correct |
45 ms |
74944 KB |
Output is correct |
17 |
Correct |
51 ms |
74956 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1428 ms |
81312 KB |
Output is correct |
2 |
Correct |
1424 ms |
81288 KB |
Output is correct |
3 |
Correct |
1403 ms |
81416 KB |
Output is correct |
4 |
Correct |
1417 ms |
81436 KB |
Output is correct |
5 |
Correct |
1378 ms |
81452 KB |
Output is correct |
6 |
Correct |
1843 ms |
81140 KB |
Output is correct |
7 |
Correct |
1905 ms |
81072 KB |
Output is correct |
8 |
Correct |
1942 ms |
81052 KB |
Output is correct |
9 |
Correct |
68 ms |
79288 KB |
Output is correct |
10 |
Correct |
1057 ms |
80264 KB |
Output is correct |
11 |
Correct |
985 ms |
80168 KB |
Output is correct |
12 |
Correct |
1299 ms |
80584 KB |
Output is correct |
13 |
Correct |
1248 ms |
81856 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1117 ms |
80692 KB |
Output is correct |
2 |
Correct |
561 ms |
78812 KB |
Output is correct |
3 |
Correct |
1228 ms |
80392 KB |
Output is correct |
4 |
Correct |
1107 ms |
80720 KB |
Output is correct |
5 |
Correct |
74 ms |
79304 KB |
Output is correct |
6 |
Correct |
1184 ms |
80616 KB |
Output is correct |
7 |
Correct |
1060 ms |
80564 KB |
Output is correct |
8 |
Correct |
1008 ms |
80780 KB |
Output is correct |
9 |
Correct |
868 ms |
80228 KB |
Output is correct |
10 |
Correct |
834 ms |
80016 KB |
Output is correct |
11 |
Correct |
892 ms |
80688 KB |
Output is correct |
12 |
Correct |
809 ms |
80768 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1367 ms |
82532 KB |
Output is correct |
2 |
Correct |
70 ms |
79348 KB |
Output is correct |
3 |
Correct |
243 ms |
78752 KB |
Output is correct |
4 |
Correct |
128 ms |
79052 KB |
Output is correct |
5 |
Correct |
813 ms |
80876 KB |
Output is correct |
6 |
Correct |
1353 ms |
82556 KB |
Output is correct |
7 |
Correct |
772 ms |
80932 KB |
Output is correct |
8 |
Correct |
915 ms |
80208 KB |
Output is correct |
9 |
Correct |
915 ms |
80424 KB |
Output is correct |
10 |
Correct |
928 ms |
80216 KB |
Output is correct |
11 |
Correct |
1173 ms |
81644 KB |
Output is correct |
12 |
Correct |
1164 ms |
81988 KB |
Output is correct |
13 |
Correct |
1235 ms |
81600 KB |
Output is correct |
14 |
Correct |
674 ms |
80964 KB |
Output is correct |
15 |
Correct |
741 ms |
80888 KB |
Output is correct |
16 |
Correct |
1396 ms |
82260 KB |
Output is correct |
17 |
Correct |
1432 ms |
82244 KB |
Output is correct |
18 |
Correct |
1453 ms |
82452 KB |
Output is correct |
19 |
Correct |
1409 ms |
82764 KB |
Output is correct |
20 |
Correct |
1331 ms |
81828 KB |
Output is correct |
21 |
Correct |
1244 ms |
81584 KB |
Output is correct |
22 |
Correct |
1339 ms |
82276 KB |
Output is correct |
23 |
Correct |
862 ms |
80596 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1428 ms |
81312 KB |
Output is correct |
2 |
Correct |
1424 ms |
81288 KB |
Output is correct |
3 |
Correct |
1403 ms |
81416 KB |
Output is correct |
4 |
Correct |
1417 ms |
81436 KB |
Output is correct |
5 |
Correct |
1378 ms |
81452 KB |
Output is correct |
6 |
Correct |
1843 ms |
81140 KB |
Output is correct |
7 |
Correct |
1905 ms |
81072 KB |
Output is correct |
8 |
Correct |
1942 ms |
81052 KB |
Output is correct |
9 |
Correct |
68 ms |
79288 KB |
Output is correct |
10 |
Correct |
1057 ms |
80264 KB |
Output is correct |
11 |
Correct |
985 ms |
80168 KB |
Output is correct |
12 |
Correct |
1299 ms |
80584 KB |
Output is correct |
13 |
Correct |
1248 ms |
81856 KB |
Output is correct |
14 |
Correct |
1117 ms |
80692 KB |
Output is correct |
15 |
Correct |
561 ms |
78812 KB |
Output is correct |
16 |
Correct |
1228 ms |
80392 KB |
Output is correct |
17 |
Correct |
1107 ms |
80720 KB |
Output is correct |
18 |
Correct |
74 ms |
79304 KB |
Output is correct |
19 |
Correct |
1184 ms |
80616 KB |
Output is correct |
20 |
Correct |
1060 ms |
80564 KB |
Output is correct |
21 |
Correct |
1008 ms |
80780 KB |
Output is correct |
22 |
Correct |
868 ms |
80228 KB |
Output is correct |
23 |
Correct |
834 ms |
80016 KB |
Output is correct |
24 |
Correct |
892 ms |
80688 KB |
Output is correct |
25 |
Correct |
809 ms |
80768 KB |
Output is correct |
26 |
Correct |
1619 ms |
81304 KB |
Output is correct |
27 |
Correct |
1799 ms |
81104 KB |
Output is correct |
28 |
Correct |
1669 ms |
81280 KB |
Output is correct |
29 |
Correct |
1355 ms |
81260 KB |
Output is correct |
30 |
Correct |
1801 ms |
81100 KB |
Output is correct |
31 |
Correct |
1815 ms |
81096 KB |
Output is correct |
32 |
Correct |
1815 ms |
81096 KB |
Output is correct |
33 |
Correct |
1628 ms |
81300 KB |
Output is correct |
34 |
Correct |
1537 ms |
81456 KB |
Output is correct |
35 |
Correct |
1490 ms |
81400 KB |
Output is correct |
36 |
Correct |
1276 ms |
81360 KB |
Output is correct |
37 |
Correct |
1250 ms |
81176 KB |
Output is correct |
38 |
Correct |
1272 ms |
81460 KB |
Output is correct |
39 |
Correct |
1033 ms |
80884 KB |
Output is correct |
40 |
Correct |
1103 ms |
80780 KB |
Output is correct |
41 |
Correct |
1042 ms |
80988 KB |
Output is correct |
42 |
Correct |
1033 ms |
81748 KB |
Output is correct |
43 |
Correct |
1036 ms |
81704 KB |
Output is correct |
44 |
Correct |
1031 ms |
81644 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
37 ms |
74612 KB |
Output is correct |
2 |
Correct |
37 ms |
74700 KB |
Output is correct |
3 |
Correct |
54 ms |
75096 KB |
Output is correct |
4 |
Correct |
40 ms |
75144 KB |
Output is correct |
5 |
Correct |
51 ms |
75028 KB |
Output is correct |
6 |
Correct |
46 ms |
75036 KB |
Output is correct |
7 |
Correct |
43 ms |
74944 KB |
Output is correct |
8 |
Correct |
44 ms |
74928 KB |
Output is correct |
9 |
Correct |
47 ms |
74920 KB |
Output is correct |
10 |
Correct |
48 ms |
75020 KB |
Output is correct |
11 |
Correct |
46 ms |
75032 KB |
Output is correct |
12 |
Correct |
45 ms |
75016 KB |
Output is correct |
13 |
Correct |
46 ms |
75044 KB |
Output is correct |
14 |
Correct |
46 ms |
74996 KB |
Output is correct |
15 |
Correct |
49 ms |
75032 KB |
Output is correct |
16 |
Correct |
45 ms |
74944 KB |
Output is correct |
17 |
Correct |
51 ms |
74956 KB |
Output is correct |
18 |
Correct |
1428 ms |
81312 KB |
Output is correct |
19 |
Correct |
1424 ms |
81288 KB |
Output is correct |
20 |
Correct |
1403 ms |
81416 KB |
Output is correct |
21 |
Correct |
1417 ms |
81436 KB |
Output is correct |
22 |
Correct |
1378 ms |
81452 KB |
Output is correct |
23 |
Correct |
1843 ms |
81140 KB |
Output is correct |
24 |
Correct |
1905 ms |
81072 KB |
Output is correct |
25 |
Correct |
1942 ms |
81052 KB |
Output is correct |
26 |
Correct |
68 ms |
79288 KB |
Output is correct |
27 |
Correct |
1057 ms |
80264 KB |
Output is correct |
28 |
Correct |
985 ms |
80168 KB |
Output is correct |
29 |
Correct |
1299 ms |
80584 KB |
Output is correct |
30 |
Correct |
1248 ms |
81856 KB |
Output is correct |
31 |
Correct |
1117 ms |
80692 KB |
Output is correct |
32 |
Correct |
561 ms |
78812 KB |
Output is correct |
33 |
Correct |
1228 ms |
80392 KB |
Output is correct |
34 |
Correct |
1107 ms |
80720 KB |
Output is correct |
35 |
Correct |
74 ms |
79304 KB |
Output is correct |
36 |
Correct |
1184 ms |
80616 KB |
Output is correct |
37 |
Correct |
1060 ms |
80564 KB |
Output is correct |
38 |
Correct |
1008 ms |
80780 KB |
Output is correct |
39 |
Correct |
868 ms |
80228 KB |
Output is correct |
40 |
Correct |
834 ms |
80016 KB |
Output is correct |
41 |
Correct |
892 ms |
80688 KB |
Output is correct |
42 |
Correct |
809 ms |
80768 KB |
Output is correct |
43 |
Correct |
1367 ms |
82532 KB |
Output is correct |
44 |
Correct |
70 ms |
79348 KB |
Output is correct |
45 |
Correct |
243 ms |
78752 KB |
Output is correct |
46 |
Correct |
128 ms |
79052 KB |
Output is correct |
47 |
Correct |
813 ms |
80876 KB |
Output is correct |
48 |
Correct |
1353 ms |
82556 KB |
Output is correct |
49 |
Correct |
772 ms |
80932 KB |
Output is correct |
50 |
Correct |
915 ms |
80208 KB |
Output is correct |
51 |
Correct |
915 ms |
80424 KB |
Output is correct |
52 |
Correct |
928 ms |
80216 KB |
Output is correct |
53 |
Correct |
1173 ms |
81644 KB |
Output is correct |
54 |
Correct |
1164 ms |
81988 KB |
Output is correct |
55 |
Correct |
1235 ms |
81600 KB |
Output is correct |
56 |
Correct |
674 ms |
80964 KB |
Output is correct |
57 |
Correct |
741 ms |
80888 KB |
Output is correct |
58 |
Correct |
1396 ms |
82260 KB |
Output is correct |
59 |
Correct |
1432 ms |
82244 KB |
Output is correct |
60 |
Correct |
1453 ms |
82452 KB |
Output is correct |
61 |
Correct |
1409 ms |
82764 KB |
Output is correct |
62 |
Correct |
1331 ms |
81828 KB |
Output is correct |
63 |
Correct |
1244 ms |
81584 KB |
Output is correct |
64 |
Correct |
1339 ms |
82276 KB |
Output is correct |
65 |
Correct |
862 ms |
80596 KB |
Output is correct |
66 |
Correct |
1619 ms |
81304 KB |
Output is correct |
67 |
Correct |
1799 ms |
81104 KB |
Output is correct |
68 |
Correct |
1669 ms |
81280 KB |
Output is correct |
69 |
Correct |
1355 ms |
81260 KB |
Output is correct |
70 |
Correct |
1801 ms |
81100 KB |
Output is correct |
71 |
Correct |
1815 ms |
81096 KB |
Output is correct |
72 |
Correct |
1815 ms |
81096 KB |
Output is correct |
73 |
Correct |
1628 ms |
81300 KB |
Output is correct |
74 |
Correct |
1537 ms |
81456 KB |
Output is correct |
75 |
Correct |
1490 ms |
81400 KB |
Output is correct |
76 |
Correct |
1276 ms |
81360 KB |
Output is correct |
77 |
Correct |
1250 ms |
81176 KB |
Output is correct |
78 |
Correct |
1272 ms |
81460 KB |
Output is correct |
79 |
Correct |
1033 ms |
80884 KB |
Output is correct |
80 |
Correct |
1103 ms |
80780 KB |
Output is correct |
81 |
Correct |
1042 ms |
80988 KB |
Output is correct |
82 |
Correct |
1033 ms |
81748 KB |
Output is correct |
83 |
Correct |
1036 ms |
81704 KB |
Output is correct |
84 |
Correct |
1031 ms |
81644 KB |
Output is correct |
85 |
Correct |
2278 ms |
84180 KB |
Output is correct |
86 |
Correct |
289 ms |
78884 KB |
Output is correct |
87 |
Correct |
180 ms |
79136 KB |
Output is correct |
88 |
Correct |
1489 ms |
82564 KB |
Output is correct |
89 |
Correct |
2156 ms |
83952 KB |
Output is correct |
90 |
Correct |
1510 ms |
82316 KB |
Output is correct |
91 |
Correct |
1552 ms |
81204 KB |
Output is correct |
92 |
Correct |
1520 ms |
81304 KB |
Output is correct |
93 |
Correct |
1995 ms |
81176 KB |
Output is correct |
94 |
Correct |
1979 ms |
83412 KB |
Output is correct |
95 |
Correct |
1918 ms |
83396 KB |
Output is correct |
96 |
Correct |
2193 ms |
83108 KB |
Output is correct |
97 |
Correct |
1020 ms |
81272 KB |
Output is correct |
98 |
Correct |
1147 ms |
82260 KB |
Output is correct |
99 |
Correct |
2190 ms |
83932 KB |
Output is correct |
100 |
Correct |
2187 ms |
83800 KB |
Output is correct |
101 |
Correct |
2195 ms |
83956 KB |
Output is correct |
102 |
Correct |
2175 ms |
84020 KB |
Output is correct |
103 |
Correct |
2451 ms |
83076 KB |
Output is correct |
104 |
Correct |
2361 ms |
82964 KB |
Output is correct |
105 |
Correct |
1721 ms |
83096 KB |
Output is correct |
106 |
Correct |
1403 ms |
82756 KB |
Output is correct |
107 |
Correct |
1574 ms |
81864 KB |
Output is correct |
108 |
Correct |
2290 ms |
83372 KB |
Output is correct |
109 |
Correct |
1727 ms |
81844 KB |
Output is correct |