#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define bit(n,i) ((n>>i)&1)
#define all(x) x.begin(),x.end()
//#pragma GCC optimize("O2,unroll-loops")
//#pragma GCC target("avx,avx2,bmi,bmi2,sse,sse2,sse3,ssse3,sse4,popcnt")
//#define int long long
typedef long long ll;
typedef pair<int,int> pii;
typedef double db;
typedef pair<db,db> pdd;
typedef pair<ll,ll> pll;
const ll maxn=1e5+5;
const ll maxk=2e5+5;
const ll block_sz=1000;
const ll inf=1e9;
const ll mod=111539786;
int n,m,q;
struct dsu_rollback
{
int par[maxn];
vector<pii> save;
void init()
{
for1(i,1,n) par[i]=-1;
save.clear();
}
int Find(int u)
{
return ((par[u]<0)?(u):Find(par[u]));
}
void Union(int u,int v)
{
if ((u=Find(u))==(v=Find(v))) return;
if (par[u]>par[v]) swap(u,v);
save.pb({v,par[v]});
par[u]+=par[v];
par[v]=u;
}
void Roll(int x)
{
while (save.size()>x)
{
int v=save.back().fi;
int pv=save.back().se;
int u=par[v];
save.pop_back();;
par[u]-=pv;
par[v]=pv;
}
}
int Get(int u)
{
return par[Find(u)]*(-1);
}
}dsu;
struct Edge
{
int u,v,d,i;
bool operator <(const Edge& o) const
{
return d>o.d;
}
}e[maxn];
struct queri
{
int t,s,w,s1;
bool operator <(const queri& o) const
{
return w>o.w;
}
}qr[maxn];
int x[maxn];
int ans[maxn];
vector<int> Lqr[maxn/block_sz +1][3];
int spe[maxn];
bool cc[maxn];
void sol()
{
cin >> n>> m;
for1(i,1,m)
{
int u,v,d; cin >> u>>v>>d;
e[i]={u,v,d,i};
}
cin >> q;
for1(i,1,q)
{
int t,s1,s,w; cin >> t>> s1>> w;
if (t==1) s=x[s1];
else s=s1;
qr[i]={t,s,w,s1};
Lqr[i/block_sz][t].pb(i);
}
for1(g,0,q/block_sz)
{
sort(e+1,e+1+m);
for1(i,1,m) {x[e[i].i]=i;}
sort(all(Lqr[g][2]),[](int x,int y)
{
return qr[x].w>qr[y].w;
});
for(int i: Lqr[g][1])
{
qr[i].s=x[qr[i].s1];
spe[qr[i].s]=1;
}
int j=1;
dsu.init();
for(int i: Lqr[g][2])
{
while (j<=m && e[j].d >= qr[i].w)
{
if (!spe[j])
{
dsu.Union(e[j].u,e[j].v);
}
j++;
}
int sv=dsu.save.size();
int moc=upper_bound(all(Lqr[g][1]),i)-Lqr[g][1].begin();
for2(xx,moc-1,0)
{
int x=Lqr[g][1][xx];
if (cc[qr[x].s]) continue;
cc[qr[x].s]=1;
if(qr[x].w>= qr[i].w)
{
dsu.Union(e[qr[x].s].u,e[qr[x].s].v);
}
}
for1(xx,moc,(int)Lqr[g][1].size()-1)
{
int x=Lqr[g][1][xx];
if (cc[qr[x].s]) continue;
cc[qr[x].s]=1;
if (e[qr[x].s].d>=qr[i].w) dsu.Union(e[qr[x].s].u,e[qr[x].s].v);
}
for(int x: Lqr[g][1]) cc[qr[x].s]=0;
ans[i]=dsu.Get(qr[i].s);
dsu.Roll(sv);
}
for(int i:Lqr[g][1])
{
e[qr[i].s].d=qr[i].w;
spe[qr[i].s]=0;
}
}
for1(i,1,q) if (qr[i].t==2) cout << ans[i]<<'\n';
}
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
// freopen("F.inp","r",stdin);
// freopen("F.out","w",stdout);
int t=1;//cin >> t;
while (t--)
{
sol();
}
}
/*
*/
Compilation message
bridges.cpp: In member function 'void dsu_rollback::Roll(int)':
bridges.cpp:49:27: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
49 | while (save.size()>x)
| ~~~~~~~~~~~^~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
4444 KB |
Output is correct |
2 |
Correct |
1 ms |
4444 KB |
Output is correct |
3 |
Correct |
18 ms |
4440 KB |
Output is correct |
4 |
Correct |
3 ms |
2392 KB |
Output is correct |
5 |
Correct |
16 ms |
4444 KB |
Output is correct |
6 |
Correct |
13 ms |
4444 KB |
Output is correct |
7 |
Correct |
12 ms |
4444 KB |
Output is correct |
8 |
Correct |
14 ms |
4444 KB |
Output is correct |
9 |
Correct |
13 ms |
4444 KB |
Output is correct |
10 |
Correct |
15 ms |
4444 KB |
Output is correct |
11 |
Correct |
13 ms |
4624 KB |
Output is correct |
12 |
Correct |
14 ms |
4444 KB |
Output is correct |
13 |
Correct |
19 ms |
4636 KB |
Output is correct |
14 |
Correct |
17 ms |
4444 KB |
Output is correct |
15 |
Correct |
16 ms |
4624 KB |
Output is correct |
16 |
Correct |
15 ms |
4636 KB |
Output is correct |
17 |
Correct |
13 ms |
4444 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
510 ms |
5904 KB |
Output is correct |
2 |
Correct |
553 ms |
5900 KB |
Output is correct |
3 |
Correct |
513 ms |
5908 KB |
Output is correct |
4 |
Correct |
611 ms |
5896 KB |
Output is correct |
5 |
Correct |
615 ms |
5908 KB |
Output is correct |
6 |
Correct |
828 ms |
6416 KB |
Output is correct |
7 |
Correct |
834 ms |
6160 KB |
Output is correct |
8 |
Correct |
817 ms |
6160 KB |
Output is correct |
9 |
Correct |
33 ms |
5208 KB |
Output is correct |
10 |
Correct |
458 ms |
5876 KB |
Output is correct |
11 |
Correct |
447 ms |
5908 KB |
Output is correct |
12 |
Correct |
448 ms |
6340 KB |
Output is correct |
13 |
Correct |
483 ms |
6092 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
401 ms |
5924 KB |
Output is correct |
2 |
Correct |
322 ms |
5208 KB |
Output is correct |
3 |
Correct |
459 ms |
5924 KB |
Output is correct |
4 |
Correct |
392 ms |
5596 KB |
Output is correct |
5 |
Correct |
26 ms |
4956 KB |
Output is correct |
6 |
Correct |
430 ms |
5660 KB |
Output is correct |
7 |
Correct |
388 ms |
5684 KB |
Output is correct |
8 |
Correct |
351 ms |
5676 KB |
Output is correct |
9 |
Correct |
272 ms |
5936 KB |
Output is correct |
10 |
Correct |
258 ms |
5844 KB |
Output is correct |
11 |
Correct |
270 ms |
5656 KB |
Output is correct |
12 |
Correct |
244 ms |
5652 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
407 ms |
6060 KB |
Output is correct |
2 |
Correct |
26 ms |
4952 KB |
Output is correct |
3 |
Correct |
62 ms |
4728 KB |
Output is correct |
4 |
Correct |
52 ms |
4700 KB |
Output is correct |
5 |
Correct |
390 ms |
6228 KB |
Output is correct |
6 |
Correct |
399 ms |
6088 KB |
Output is correct |
7 |
Correct |
387 ms |
6216 KB |
Output is correct |
8 |
Correct |
186 ms |
5676 KB |
Output is correct |
9 |
Correct |
175 ms |
5712 KB |
Output is correct |
10 |
Correct |
182 ms |
5932 KB |
Output is correct |
11 |
Correct |
302 ms |
6088 KB |
Output is correct |
12 |
Correct |
280 ms |
5840 KB |
Output is correct |
13 |
Correct |
305 ms |
5936 KB |
Output is correct |
14 |
Correct |
385 ms |
6348 KB |
Output is correct |
15 |
Correct |
376 ms |
6316 KB |
Output is correct |
16 |
Correct |
432 ms |
6048 KB |
Output is correct |
17 |
Correct |
425 ms |
6052 KB |
Output is correct |
18 |
Correct |
424 ms |
6092 KB |
Output is correct |
19 |
Correct |
449 ms |
6056 KB |
Output is correct |
20 |
Correct |
403 ms |
6208 KB |
Output is correct |
21 |
Correct |
357 ms |
6212 KB |
Output is correct |
22 |
Correct |
411 ms |
6240 KB |
Output is correct |
23 |
Correct |
323 ms |
6132 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
510 ms |
5904 KB |
Output is correct |
2 |
Correct |
553 ms |
5900 KB |
Output is correct |
3 |
Correct |
513 ms |
5908 KB |
Output is correct |
4 |
Correct |
611 ms |
5896 KB |
Output is correct |
5 |
Correct |
615 ms |
5908 KB |
Output is correct |
6 |
Correct |
828 ms |
6416 KB |
Output is correct |
7 |
Correct |
834 ms |
6160 KB |
Output is correct |
8 |
Correct |
817 ms |
6160 KB |
Output is correct |
9 |
Correct |
33 ms |
5208 KB |
Output is correct |
10 |
Correct |
458 ms |
5876 KB |
Output is correct |
11 |
Correct |
447 ms |
5908 KB |
Output is correct |
12 |
Correct |
448 ms |
6340 KB |
Output is correct |
13 |
Correct |
483 ms |
6092 KB |
Output is correct |
14 |
Correct |
401 ms |
5924 KB |
Output is correct |
15 |
Correct |
322 ms |
5208 KB |
Output is correct |
16 |
Correct |
459 ms |
5924 KB |
Output is correct |
17 |
Correct |
392 ms |
5596 KB |
Output is correct |
18 |
Correct |
26 ms |
4956 KB |
Output is correct |
19 |
Correct |
430 ms |
5660 KB |
Output is correct |
20 |
Correct |
388 ms |
5684 KB |
Output is correct |
21 |
Correct |
351 ms |
5676 KB |
Output is correct |
22 |
Correct |
272 ms |
5936 KB |
Output is correct |
23 |
Correct |
258 ms |
5844 KB |
Output is correct |
24 |
Correct |
270 ms |
5656 KB |
Output is correct |
25 |
Correct |
244 ms |
5652 KB |
Output is correct |
26 |
Correct |
494 ms |
6020 KB |
Output is correct |
27 |
Correct |
618 ms |
5964 KB |
Output is correct |
28 |
Correct |
521 ms |
5896 KB |
Output is correct |
29 |
Correct |
424 ms |
5892 KB |
Output is correct |
30 |
Correct |
620 ms |
6092 KB |
Output is correct |
31 |
Correct |
599 ms |
5836 KB |
Output is correct |
32 |
Correct |
609 ms |
5924 KB |
Output is correct |
33 |
Correct |
540 ms |
6092 KB |
Output is correct |
34 |
Correct |
575 ms |
6104 KB |
Output is correct |
35 |
Correct |
545 ms |
5888 KB |
Output is correct |
36 |
Correct |
441 ms |
5908 KB |
Output is correct |
37 |
Correct |
445 ms |
5888 KB |
Output is correct |
38 |
Correct |
433 ms |
6096 KB |
Output is correct |
39 |
Correct |
343 ms |
5928 KB |
Output is correct |
40 |
Correct |
394 ms |
5836 KB |
Output is correct |
41 |
Correct |
341 ms |
5840 KB |
Output is correct |
42 |
Correct |
313 ms |
5848 KB |
Output is correct |
43 |
Correct |
319 ms |
5956 KB |
Output is correct |
44 |
Correct |
310 ms |
5988 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
4444 KB |
Output is correct |
2 |
Correct |
1 ms |
4444 KB |
Output is correct |
3 |
Correct |
18 ms |
4440 KB |
Output is correct |
4 |
Correct |
3 ms |
2392 KB |
Output is correct |
5 |
Correct |
16 ms |
4444 KB |
Output is correct |
6 |
Correct |
13 ms |
4444 KB |
Output is correct |
7 |
Correct |
12 ms |
4444 KB |
Output is correct |
8 |
Correct |
14 ms |
4444 KB |
Output is correct |
9 |
Correct |
13 ms |
4444 KB |
Output is correct |
10 |
Correct |
15 ms |
4444 KB |
Output is correct |
11 |
Correct |
13 ms |
4624 KB |
Output is correct |
12 |
Correct |
14 ms |
4444 KB |
Output is correct |
13 |
Correct |
19 ms |
4636 KB |
Output is correct |
14 |
Correct |
17 ms |
4444 KB |
Output is correct |
15 |
Correct |
16 ms |
4624 KB |
Output is correct |
16 |
Correct |
15 ms |
4636 KB |
Output is correct |
17 |
Correct |
13 ms |
4444 KB |
Output is correct |
18 |
Correct |
510 ms |
5904 KB |
Output is correct |
19 |
Correct |
553 ms |
5900 KB |
Output is correct |
20 |
Correct |
513 ms |
5908 KB |
Output is correct |
21 |
Correct |
611 ms |
5896 KB |
Output is correct |
22 |
Correct |
615 ms |
5908 KB |
Output is correct |
23 |
Correct |
828 ms |
6416 KB |
Output is correct |
24 |
Correct |
834 ms |
6160 KB |
Output is correct |
25 |
Correct |
817 ms |
6160 KB |
Output is correct |
26 |
Correct |
33 ms |
5208 KB |
Output is correct |
27 |
Correct |
458 ms |
5876 KB |
Output is correct |
28 |
Correct |
447 ms |
5908 KB |
Output is correct |
29 |
Correct |
448 ms |
6340 KB |
Output is correct |
30 |
Correct |
483 ms |
6092 KB |
Output is correct |
31 |
Correct |
401 ms |
5924 KB |
Output is correct |
32 |
Correct |
322 ms |
5208 KB |
Output is correct |
33 |
Correct |
459 ms |
5924 KB |
Output is correct |
34 |
Correct |
392 ms |
5596 KB |
Output is correct |
35 |
Correct |
26 ms |
4956 KB |
Output is correct |
36 |
Correct |
430 ms |
5660 KB |
Output is correct |
37 |
Correct |
388 ms |
5684 KB |
Output is correct |
38 |
Correct |
351 ms |
5676 KB |
Output is correct |
39 |
Correct |
272 ms |
5936 KB |
Output is correct |
40 |
Correct |
258 ms |
5844 KB |
Output is correct |
41 |
Correct |
270 ms |
5656 KB |
Output is correct |
42 |
Correct |
244 ms |
5652 KB |
Output is correct |
43 |
Correct |
407 ms |
6060 KB |
Output is correct |
44 |
Correct |
26 ms |
4952 KB |
Output is correct |
45 |
Correct |
62 ms |
4728 KB |
Output is correct |
46 |
Correct |
52 ms |
4700 KB |
Output is correct |
47 |
Correct |
390 ms |
6228 KB |
Output is correct |
48 |
Correct |
399 ms |
6088 KB |
Output is correct |
49 |
Correct |
387 ms |
6216 KB |
Output is correct |
50 |
Correct |
186 ms |
5676 KB |
Output is correct |
51 |
Correct |
175 ms |
5712 KB |
Output is correct |
52 |
Correct |
182 ms |
5932 KB |
Output is correct |
53 |
Correct |
302 ms |
6088 KB |
Output is correct |
54 |
Correct |
280 ms |
5840 KB |
Output is correct |
55 |
Correct |
305 ms |
5936 KB |
Output is correct |
56 |
Correct |
385 ms |
6348 KB |
Output is correct |
57 |
Correct |
376 ms |
6316 KB |
Output is correct |
58 |
Correct |
432 ms |
6048 KB |
Output is correct |
59 |
Correct |
425 ms |
6052 KB |
Output is correct |
60 |
Correct |
424 ms |
6092 KB |
Output is correct |
61 |
Correct |
449 ms |
6056 KB |
Output is correct |
62 |
Correct |
403 ms |
6208 KB |
Output is correct |
63 |
Correct |
357 ms |
6212 KB |
Output is correct |
64 |
Correct |
411 ms |
6240 KB |
Output is correct |
65 |
Correct |
323 ms |
6132 KB |
Output is correct |
66 |
Correct |
494 ms |
6020 KB |
Output is correct |
67 |
Correct |
618 ms |
5964 KB |
Output is correct |
68 |
Correct |
521 ms |
5896 KB |
Output is correct |
69 |
Correct |
424 ms |
5892 KB |
Output is correct |
70 |
Correct |
620 ms |
6092 KB |
Output is correct |
71 |
Correct |
599 ms |
5836 KB |
Output is correct |
72 |
Correct |
609 ms |
5924 KB |
Output is correct |
73 |
Correct |
540 ms |
6092 KB |
Output is correct |
74 |
Correct |
575 ms |
6104 KB |
Output is correct |
75 |
Correct |
545 ms |
5888 KB |
Output is correct |
76 |
Correct |
441 ms |
5908 KB |
Output is correct |
77 |
Correct |
445 ms |
5888 KB |
Output is correct |
78 |
Correct |
433 ms |
6096 KB |
Output is correct |
79 |
Correct |
343 ms |
5928 KB |
Output is correct |
80 |
Correct |
394 ms |
5836 KB |
Output is correct |
81 |
Correct |
341 ms |
5840 KB |
Output is correct |
82 |
Correct |
313 ms |
5848 KB |
Output is correct |
83 |
Correct |
319 ms |
5956 KB |
Output is correct |
84 |
Correct |
310 ms |
5988 KB |
Output is correct |
85 |
Correct |
875 ms |
6068 KB |
Output is correct |
86 |
Correct |
92 ms |
4808 KB |
Output is correct |
87 |
Correct |
69 ms |
4912 KB |
Output is correct |
88 |
Correct |
614 ms |
6100 KB |
Output is correct |
89 |
Correct |
872 ms |
6072 KB |
Output is correct |
90 |
Correct |
600 ms |
6316 KB |
Output is correct |
91 |
Correct |
587 ms |
6092 KB |
Output is correct |
92 |
Correct |
566 ms |
5840 KB |
Output is correct |
93 |
Correct |
740 ms |
5888 KB |
Output is correct |
94 |
Correct |
756 ms |
6088 KB |
Output is correct |
95 |
Correct |
749 ms |
5928 KB |
Output is correct |
96 |
Correct |
903 ms |
6088 KB |
Output is correct |
97 |
Correct |
465 ms |
6300 KB |
Output is correct |
98 |
Correct |
483 ms |
6092 KB |
Output is correct |
99 |
Correct |
920 ms |
6056 KB |
Output is correct |
100 |
Correct |
987 ms |
6092 KB |
Output is correct |
101 |
Correct |
916 ms |
6060 KB |
Output is correct |
102 |
Correct |
940 ms |
6104 KB |
Output is correct |
103 |
Correct |
859 ms |
6172 KB |
Output is correct |
104 |
Correct |
899 ms |
6168 KB |
Output is correct |
105 |
Correct |
720 ms |
5928 KB |
Output is correct |
106 |
Correct |
522 ms |
5864 KB |
Output is correct |
107 |
Correct |
658 ms |
6172 KB |
Output is correct |
108 |
Correct |
873 ms |
6252 KB |
Output is correct |
109 |
Correct |
638 ms |
6136 KB |
Output is correct |