#include<bits/stdc++.h>
#pragma GCC target("avx")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef pair<ll,ll> P;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<bool> vb;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define REP(i,k,n) for(ll i=(ll)(k);i<(ll)(n);i++)
#define fi first
#define se second
#define pb emplace_back
#define all(a) a.begin(),a.end()
#define lb(v,k) (lower_bound(all(v),k)-v.begin())
#define dame(a) {out(a);return 0;}
#define rsort(a) {sort(all(a));reverse(all(a));}
template<class T> bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
template<class T> bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}
template<class T> void out(T a){cout<<a<<'\n';}
template<class T> void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<'\n';}
template<class T> void outvv(T v){rep(i,v.size())outv(v[i]);}
template<class T> void outp(T p){printf("(%d,%d)",p.fi,p.se);cout<<'\n';}
template<class T> void outvp(T v){for(auto p:v)printf("(%d,%d)",p.fi,p.se);cout<<'\n';}
template<class T> void outvvp(T v){rep(i,v.size())outvp(v[i]);}
inline ll readll() {
ll x = 0;
char ch = getchar_unlocked();
while (ch < '0' || ch > '9') ch = getchar_unlocked();
while (ch >= '0' && ch <= '9'){
x = (x << 3) + (x << 1) + ch - '0';
ch = getchar_unlocked();
}
return x;
}
class UF{
vi par,sz;
public:
ll cnt;
vp memo;
UF(ll n){
par=vi(n,-1);sz=vi(n,1);cnt=n;
}
ll root(ll i){if(par[i]==-1)return i;return root(par[i]);}
void merge(ll a,ll b,bool flag){
a=root(a);b=root(b);
if(a==b)return;
if(sz[a]>sz[b])swap(a,b);
if(flag){memo.pb(a,par[a]);memo.pb(b,sz[b]);}
par[a]=b;sz[b]+=sz[a];cnt--;
}
void rollback(){
while(!memo.empty()){
sz[memo.back().fi]=memo.back().se;memo.pop_back();
par[memo.back().fi]=memo.back().se;memo.pop_back();
cnt++;
}
}
ll get(ll i){
return sz[root(i)];
}
};
int main(){
ll n=readll(),m=readll(),B=1000;
vp edge(m);
vi weight(m);
rep(i,m){
edge[i].fi=readll()-1;edge[i].se=readll()-1;weight[i]=readll();
}
ll Q=readll();
vvi query(Q,vi(3));
ll cnt=0;
rep(i,Q){
query[i][0]=readll();
query[i][1]=readll()-1;
query[i][2]=readll();
if(query[i][0]==1)query[i][0]=-1;
else query[i][0]=cnt++;
}
vi ans(cnt);
rep(i,Q/B+1){
UF uf(n);
vb sp(m,false);
vp q;
REP(j,i*B,min((i+1)*B,Q)){
if(query[j][0]==-1)sp[query[j][1]]=true;
else q.pb(query[j][2],j);
}
rsort(q);
vp s;rep(j,m)if(!sp[j])s.pb(weight[j],j);rsort(s);
ll w=0;
vb use(m,false);
for(auto x:q){
while(w!=s.size()&&s[w].fi>=x.fi){
uf.merge(edge[s[w].se].fi,edge[s[w].se].se,0);
w++;
}
for(int j=x.se-1;j>=i*B;j--)if(query[j][0]==-1&&!use[query[j][1]]){
use[query[j][1]]=true;
if(query[j][2]>=x.fi)uf.merge(edge[query[j][1]].fi,edge[query[j][1]].se,1);
}
REP(j,x.se+1,min((i+1)*B,Q))if(query[j][0]==-1&&!use[query[j][1]]&&weight[query[j][1]]>=x.fi)uf.merge(edge[query[j][1]].fi,edge[query[j][1]].se,1);
ans[query[x.se][0]]=uf.get(query[x.se][1]);
uf.rollback();
REP(j,i*B,x.se)if(query[j][0]==-1)use[query[j][1]]=false;
}
REP(j,i*B,min((i+1)*B,Q))if(query[j][0]==-1)weight[query[j][1]]=query[j][2];
}
for(ll x:ans)out(x);
}
Compilation message
bridges.cpp: In function 'int main()':
bridges.cpp:100:20: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
100 | while(w!=s.size()&&s[w].fi>=x.fi){
| ~^~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
57 ms |
1004 KB |
Output is correct |
4 |
Correct |
17 ms |
1004 KB |
Output is correct |
5 |
Correct |
56 ms |
1004 KB |
Output is correct |
6 |
Correct |
47 ms |
1004 KB |
Output is correct |
7 |
Correct |
49 ms |
1004 KB |
Output is correct |
8 |
Correct |
54 ms |
1004 KB |
Output is correct |
9 |
Correct |
48 ms |
1004 KB |
Output is correct |
10 |
Correct |
55 ms |
876 KB |
Output is correct |
11 |
Correct |
55 ms |
876 KB |
Output is correct |
12 |
Correct |
56 ms |
876 KB |
Output is correct |
13 |
Correct |
67 ms |
1004 KB |
Output is correct |
14 |
Correct |
63 ms |
1004 KB |
Output is correct |
15 |
Correct |
58 ms |
1004 KB |
Output is correct |
16 |
Correct |
47 ms |
1004 KB |
Output is correct |
17 |
Correct |
49 ms |
1004 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1682 ms |
10264 KB |
Output is correct |
2 |
Correct |
1735 ms |
10468 KB |
Output is correct |
3 |
Correct |
1738 ms |
10652 KB |
Output is correct |
4 |
Correct |
1833 ms |
10224 KB |
Output is correct |
5 |
Correct |
1807 ms |
10476 KB |
Output is correct |
6 |
Correct |
2619 ms |
10308 KB |
Output is correct |
7 |
Correct |
2661 ms |
10420 KB |
Output is correct |
8 |
Correct |
2665 ms |
10384 KB |
Output is correct |
9 |
Correct |
171 ms |
6792 KB |
Output is correct |
10 |
Correct |
1546 ms |
10140 KB |
Output is correct |
11 |
Correct |
1516 ms |
10300 KB |
Output is correct |
12 |
Correct |
1531 ms |
10564 KB |
Output is correct |
13 |
Correct |
1441 ms |
9956 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1380 ms |
9056 KB |
Output is correct |
2 |
Correct |
1096 ms |
6960 KB |
Output is correct |
3 |
Correct |
1564 ms |
8568 KB |
Output is correct |
4 |
Correct |
1336 ms |
8896 KB |
Output is correct |
5 |
Correct |
169 ms |
6764 KB |
Output is correct |
6 |
Correct |
1496 ms |
8876 KB |
Output is correct |
7 |
Correct |
1259 ms |
8696 KB |
Output is correct |
8 |
Correct |
1135 ms |
8700 KB |
Output is correct |
9 |
Correct |
949 ms |
9028 KB |
Output is correct |
10 |
Correct |
878 ms |
8896 KB |
Output is correct |
11 |
Correct |
872 ms |
8332 KB |
Output is correct |
12 |
Correct |
760 ms |
8468 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1909 ms |
13724 KB |
Output is correct |
2 |
Correct |
171 ms |
6792 KB |
Output is correct |
3 |
Correct |
182 ms |
7140 KB |
Output is correct |
4 |
Correct |
139 ms |
7000 KB |
Output is correct |
5 |
Correct |
1770 ms |
13856 KB |
Output is correct |
6 |
Correct |
1890 ms |
13760 KB |
Output is correct |
7 |
Correct |
1804 ms |
13808 KB |
Output is correct |
8 |
Correct |
956 ms |
10828 KB |
Output is correct |
9 |
Correct |
949 ms |
10720 KB |
Output is correct |
10 |
Correct |
936 ms |
10644 KB |
Output is correct |
11 |
Correct |
1480 ms |
12572 KB |
Output is correct |
12 |
Correct |
1443 ms |
12600 KB |
Output is correct |
13 |
Correct |
1450 ms |
12444 KB |
Output is correct |
14 |
Correct |
1533 ms |
13432 KB |
Output is correct |
15 |
Correct |
1674 ms |
13920 KB |
Output is correct |
16 |
Correct |
1864 ms |
13540 KB |
Output is correct |
17 |
Correct |
1895 ms |
13592 KB |
Output is correct |
18 |
Correct |
1885 ms |
13616 KB |
Output is correct |
19 |
Correct |
1845 ms |
13612 KB |
Output is correct |
20 |
Correct |
1643 ms |
13104 KB |
Output is correct |
21 |
Correct |
1601 ms |
13020 KB |
Output is correct |
22 |
Correct |
1814 ms |
13452 KB |
Output is correct |
23 |
Correct |
1746 ms |
12928 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1682 ms |
10264 KB |
Output is correct |
2 |
Correct |
1735 ms |
10468 KB |
Output is correct |
3 |
Correct |
1738 ms |
10652 KB |
Output is correct |
4 |
Correct |
1833 ms |
10224 KB |
Output is correct |
5 |
Correct |
1807 ms |
10476 KB |
Output is correct |
6 |
Correct |
2619 ms |
10308 KB |
Output is correct |
7 |
Correct |
2661 ms |
10420 KB |
Output is correct |
8 |
Correct |
2665 ms |
10384 KB |
Output is correct |
9 |
Correct |
171 ms |
6792 KB |
Output is correct |
10 |
Correct |
1546 ms |
10140 KB |
Output is correct |
11 |
Correct |
1516 ms |
10300 KB |
Output is correct |
12 |
Correct |
1531 ms |
10564 KB |
Output is correct |
13 |
Correct |
1441 ms |
9956 KB |
Output is correct |
14 |
Correct |
1380 ms |
9056 KB |
Output is correct |
15 |
Correct |
1096 ms |
6960 KB |
Output is correct |
16 |
Correct |
1564 ms |
8568 KB |
Output is correct |
17 |
Correct |
1336 ms |
8896 KB |
Output is correct |
18 |
Correct |
169 ms |
6764 KB |
Output is correct |
19 |
Correct |
1496 ms |
8876 KB |
Output is correct |
20 |
Correct |
1259 ms |
8696 KB |
Output is correct |
21 |
Correct |
1135 ms |
8700 KB |
Output is correct |
22 |
Correct |
949 ms |
9028 KB |
Output is correct |
23 |
Correct |
878 ms |
8896 KB |
Output is correct |
24 |
Correct |
872 ms |
8332 KB |
Output is correct |
25 |
Correct |
760 ms |
8468 KB |
Output is correct |
26 |
Correct |
1736 ms |
10192 KB |
Output is correct |
27 |
Correct |
2052 ms |
10368 KB |
Output is correct |
28 |
Correct |
1736 ms |
10368 KB |
Output is correct |
29 |
Correct |
1343 ms |
10396 KB |
Output is correct |
30 |
Correct |
2017 ms |
10360 KB |
Output is correct |
31 |
Correct |
2017 ms |
10184 KB |
Output is correct |
32 |
Correct |
2041 ms |
10460 KB |
Output is correct |
33 |
Correct |
1729 ms |
10120 KB |
Output is correct |
34 |
Correct |
1731 ms |
10368 KB |
Output is correct |
35 |
Correct |
1781 ms |
10088 KB |
Output is correct |
36 |
Correct |
1377 ms |
10324 KB |
Output is correct |
37 |
Correct |
1411 ms |
10264 KB |
Output is correct |
38 |
Correct |
1433 ms |
10168 KB |
Output is correct |
39 |
Correct |
1230 ms |
10460 KB |
Output is correct |
40 |
Correct |
1219 ms |
10692 KB |
Output is correct |
41 |
Correct |
1164 ms |
10504 KB |
Output is correct |
42 |
Correct |
1016 ms |
9852 KB |
Output is correct |
43 |
Correct |
958 ms |
9912 KB |
Output is correct |
44 |
Correct |
1006 ms |
9976 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
57 ms |
1004 KB |
Output is correct |
4 |
Correct |
17 ms |
1004 KB |
Output is correct |
5 |
Correct |
56 ms |
1004 KB |
Output is correct |
6 |
Correct |
47 ms |
1004 KB |
Output is correct |
7 |
Correct |
49 ms |
1004 KB |
Output is correct |
8 |
Correct |
54 ms |
1004 KB |
Output is correct |
9 |
Correct |
48 ms |
1004 KB |
Output is correct |
10 |
Correct |
55 ms |
876 KB |
Output is correct |
11 |
Correct |
55 ms |
876 KB |
Output is correct |
12 |
Correct |
56 ms |
876 KB |
Output is correct |
13 |
Correct |
67 ms |
1004 KB |
Output is correct |
14 |
Correct |
63 ms |
1004 KB |
Output is correct |
15 |
Correct |
58 ms |
1004 KB |
Output is correct |
16 |
Correct |
47 ms |
1004 KB |
Output is correct |
17 |
Correct |
49 ms |
1004 KB |
Output is correct |
18 |
Correct |
1682 ms |
10264 KB |
Output is correct |
19 |
Correct |
1735 ms |
10468 KB |
Output is correct |
20 |
Correct |
1738 ms |
10652 KB |
Output is correct |
21 |
Correct |
1833 ms |
10224 KB |
Output is correct |
22 |
Correct |
1807 ms |
10476 KB |
Output is correct |
23 |
Correct |
2619 ms |
10308 KB |
Output is correct |
24 |
Correct |
2661 ms |
10420 KB |
Output is correct |
25 |
Correct |
2665 ms |
10384 KB |
Output is correct |
26 |
Correct |
171 ms |
6792 KB |
Output is correct |
27 |
Correct |
1546 ms |
10140 KB |
Output is correct |
28 |
Correct |
1516 ms |
10300 KB |
Output is correct |
29 |
Correct |
1531 ms |
10564 KB |
Output is correct |
30 |
Correct |
1441 ms |
9956 KB |
Output is correct |
31 |
Correct |
1380 ms |
9056 KB |
Output is correct |
32 |
Correct |
1096 ms |
6960 KB |
Output is correct |
33 |
Correct |
1564 ms |
8568 KB |
Output is correct |
34 |
Correct |
1336 ms |
8896 KB |
Output is correct |
35 |
Correct |
169 ms |
6764 KB |
Output is correct |
36 |
Correct |
1496 ms |
8876 KB |
Output is correct |
37 |
Correct |
1259 ms |
8696 KB |
Output is correct |
38 |
Correct |
1135 ms |
8700 KB |
Output is correct |
39 |
Correct |
949 ms |
9028 KB |
Output is correct |
40 |
Correct |
878 ms |
8896 KB |
Output is correct |
41 |
Correct |
872 ms |
8332 KB |
Output is correct |
42 |
Correct |
760 ms |
8468 KB |
Output is correct |
43 |
Correct |
1909 ms |
13724 KB |
Output is correct |
44 |
Correct |
171 ms |
6792 KB |
Output is correct |
45 |
Correct |
182 ms |
7140 KB |
Output is correct |
46 |
Correct |
139 ms |
7000 KB |
Output is correct |
47 |
Correct |
1770 ms |
13856 KB |
Output is correct |
48 |
Correct |
1890 ms |
13760 KB |
Output is correct |
49 |
Correct |
1804 ms |
13808 KB |
Output is correct |
50 |
Correct |
956 ms |
10828 KB |
Output is correct |
51 |
Correct |
949 ms |
10720 KB |
Output is correct |
52 |
Correct |
936 ms |
10644 KB |
Output is correct |
53 |
Correct |
1480 ms |
12572 KB |
Output is correct |
54 |
Correct |
1443 ms |
12600 KB |
Output is correct |
55 |
Correct |
1450 ms |
12444 KB |
Output is correct |
56 |
Correct |
1533 ms |
13432 KB |
Output is correct |
57 |
Correct |
1674 ms |
13920 KB |
Output is correct |
58 |
Correct |
1864 ms |
13540 KB |
Output is correct |
59 |
Correct |
1895 ms |
13592 KB |
Output is correct |
60 |
Correct |
1885 ms |
13616 KB |
Output is correct |
61 |
Correct |
1845 ms |
13612 KB |
Output is correct |
62 |
Correct |
1643 ms |
13104 KB |
Output is correct |
63 |
Correct |
1601 ms |
13020 KB |
Output is correct |
64 |
Correct |
1814 ms |
13452 KB |
Output is correct |
65 |
Correct |
1746 ms |
12928 KB |
Output is correct |
66 |
Correct |
1736 ms |
10192 KB |
Output is correct |
67 |
Correct |
2052 ms |
10368 KB |
Output is correct |
68 |
Correct |
1736 ms |
10368 KB |
Output is correct |
69 |
Correct |
1343 ms |
10396 KB |
Output is correct |
70 |
Correct |
2017 ms |
10360 KB |
Output is correct |
71 |
Correct |
2017 ms |
10184 KB |
Output is correct |
72 |
Correct |
2041 ms |
10460 KB |
Output is correct |
73 |
Correct |
1729 ms |
10120 KB |
Output is correct |
74 |
Correct |
1731 ms |
10368 KB |
Output is correct |
75 |
Correct |
1781 ms |
10088 KB |
Output is correct |
76 |
Correct |
1377 ms |
10324 KB |
Output is correct |
77 |
Correct |
1411 ms |
10264 KB |
Output is correct |
78 |
Correct |
1433 ms |
10168 KB |
Output is correct |
79 |
Correct |
1230 ms |
10460 KB |
Output is correct |
80 |
Correct |
1219 ms |
10692 KB |
Output is correct |
81 |
Correct |
1164 ms |
10504 KB |
Output is correct |
82 |
Correct |
1016 ms |
9852 KB |
Output is correct |
83 |
Correct |
958 ms |
9912 KB |
Output is correct |
84 |
Correct |
1006 ms |
9976 KB |
Output is correct |
85 |
Correct |
2632 ms |
13060 KB |
Output is correct |
86 |
Correct |
217 ms |
7088 KB |
Output is correct |
87 |
Correct |
180 ms |
7132 KB |
Output is correct |
88 |
Correct |
2364 ms |
13360 KB |
Output is correct |
89 |
Correct |
2693 ms |
13504 KB |
Output is correct |
90 |
Correct |
2350 ms |
13316 KB |
Output is correct |
91 |
Correct |
1941 ms |
10148 KB |
Output is correct |
92 |
Correct |
1905 ms |
10224 KB |
Output is correct |
93 |
Correct |
2642 ms |
10132 KB |
Output is correct |
94 |
Correct |
2344 ms |
12056 KB |
Output is correct |
95 |
Correct |
2578 ms |
12420 KB |
Output is correct |
96 |
Correct |
2909 ms |
12280 KB |
Output is correct |
97 |
Correct |
2239 ms |
13624 KB |
Output is correct |
98 |
Correct |
1963 ms |
13228 KB |
Output is correct |
99 |
Correct |
2678 ms |
13360 KB |
Output is correct |
100 |
Correct |
2623 ms |
13144 KB |
Output is correct |
101 |
Correct |
2768 ms |
13096 KB |
Output is correct |
102 |
Correct |
2744 ms |
13288 KB |
Output is correct |
103 |
Correct |
2784 ms |
12368 KB |
Output is correct |
104 |
Correct |
2812 ms |
12680 KB |
Output is correct |
105 |
Correct |
1980 ms |
12156 KB |
Output is correct |
106 |
Correct |
1531 ms |
12180 KB |
Output is correct |
107 |
Correct |
2041 ms |
13220 KB |
Output is correct |
108 |
Correct |
2553 ms |
13212 KB |
Output is correct |
109 |
Correct |
2399 ms |
12688 KB |
Output is correct |