#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=800;
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 |
44 ms |
1004 KB |
Output is correct |
4 |
Correct |
21 ms |
1004 KB |
Output is correct |
5 |
Correct |
47 ms |
980 KB |
Output is correct |
6 |
Correct |
42 ms |
876 KB |
Output is correct |
7 |
Correct |
44 ms |
1004 KB |
Output is correct |
8 |
Correct |
48 ms |
876 KB |
Output is correct |
9 |
Correct |
39 ms |
876 KB |
Output is correct |
10 |
Correct |
46 ms |
876 KB |
Output is correct |
11 |
Correct |
46 ms |
876 KB |
Output is correct |
12 |
Correct |
47 ms |
876 KB |
Output is correct |
13 |
Correct |
56 ms |
876 KB |
Output is correct |
14 |
Correct |
53 ms |
984 KB |
Output is correct |
15 |
Correct |
49 ms |
876 KB |
Output is correct |
16 |
Correct |
42 ms |
1004 KB |
Output is correct |
17 |
Correct |
43 ms |
876 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1747 ms |
10028 KB |
Output is correct |
2 |
Correct |
1790 ms |
10060 KB |
Output is correct |
3 |
Correct |
1775 ms |
10116 KB |
Output is correct |
4 |
Correct |
1874 ms |
10304 KB |
Output is correct |
5 |
Correct |
1918 ms |
10260 KB |
Output is correct |
6 |
Correct |
2436 ms |
10176 KB |
Output is correct |
7 |
Correct |
2441 ms |
10184 KB |
Output is correct |
8 |
Correct |
2442 ms |
10268 KB |
Output is correct |
9 |
Correct |
161 ms |
6764 KB |
Output is correct |
10 |
Correct |
1501 ms |
10148 KB |
Output is correct |
11 |
Correct |
1510 ms |
10144 KB |
Output is correct |
12 |
Correct |
1648 ms |
10480 KB |
Output is correct |
13 |
Correct |
1601 ms |
9792 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1513 ms |
8652 KB |
Output is correct |
2 |
Correct |
947 ms |
6924 KB |
Output is correct |
3 |
Correct |
1500 ms |
8672 KB |
Output is correct |
4 |
Correct |
1371 ms |
8840 KB |
Output is correct |
5 |
Correct |
165 ms |
6792 KB |
Output is correct |
6 |
Correct |
1477 ms |
8656 KB |
Output is correct |
7 |
Correct |
1285 ms |
8576 KB |
Output is correct |
8 |
Correct |
1203 ms |
8812 KB |
Output is correct |
9 |
Correct |
1034 ms |
8940 KB |
Output is correct |
10 |
Correct |
1006 ms |
9000 KB |
Output is correct |
11 |
Correct |
952 ms |
8312 KB |
Output is correct |
12 |
Correct |
874 ms |
8512 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2466 ms |
13712 KB |
Output is correct |
2 |
Correct |
182 ms |
6764 KB |
Output is correct |
3 |
Correct |
215 ms |
7004 KB |
Output is correct |
4 |
Correct |
199 ms |
7136 KB |
Output is correct |
5 |
Correct |
2204 ms |
13440 KB |
Output is correct |
6 |
Correct |
2468 ms |
13728 KB |
Output is correct |
7 |
Correct |
2260 ms |
13720 KB |
Output is correct |
8 |
Correct |
1197 ms |
10704 KB |
Output is correct |
9 |
Correct |
1214 ms |
10604 KB |
Output is correct |
10 |
Correct |
1183 ms |
10584 KB |
Output is correct |
11 |
Correct |
1876 ms |
12452 KB |
Output is correct |
12 |
Correct |
1884 ms |
12740 KB |
Output is correct |
13 |
Correct |
1946 ms |
12504 KB |
Output is correct |
14 |
Correct |
1968 ms |
13432 KB |
Output is correct |
15 |
Correct |
2132 ms |
13572 KB |
Output is correct |
16 |
Correct |
2605 ms |
13672 KB |
Output is correct |
17 |
Correct |
2370 ms |
13392 KB |
Output is correct |
18 |
Correct |
2389 ms |
13572 KB |
Output is correct |
19 |
Correct |
2648 ms |
13396 KB |
Output is correct |
20 |
Correct |
2025 ms |
13284 KB |
Output is correct |
21 |
Correct |
2047 ms |
13028 KB |
Output is correct |
22 |
Correct |
2313 ms |
13452 KB |
Output is correct |
23 |
Correct |
2259 ms |
12560 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1747 ms |
10028 KB |
Output is correct |
2 |
Correct |
1790 ms |
10060 KB |
Output is correct |
3 |
Correct |
1775 ms |
10116 KB |
Output is correct |
4 |
Correct |
1874 ms |
10304 KB |
Output is correct |
5 |
Correct |
1918 ms |
10260 KB |
Output is correct |
6 |
Correct |
2436 ms |
10176 KB |
Output is correct |
7 |
Correct |
2441 ms |
10184 KB |
Output is correct |
8 |
Correct |
2442 ms |
10268 KB |
Output is correct |
9 |
Correct |
161 ms |
6764 KB |
Output is correct |
10 |
Correct |
1501 ms |
10148 KB |
Output is correct |
11 |
Correct |
1510 ms |
10144 KB |
Output is correct |
12 |
Correct |
1648 ms |
10480 KB |
Output is correct |
13 |
Correct |
1601 ms |
9792 KB |
Output is correct |
14 |
Correct |
1513 ms |
8652 KB |
Output is correct |
15 |
Correct |
947 ms |
6924 KB |
Output is correct |
16 |
Correct |
1500 ms |
8672 KB |
Output is correct |
17 |
Correct |
1371 ms |
8840 KB |
Output is correct |
18 |
Correct |
165 ms |
6792 KB |
Output is correct |
19 |
Correct |
1477 ms |
8656 KB |
Output is correct |
20 |
Correct |
1285 ms |
8576 KB |
Output is correct |
21 |
Correct |
1203 ms |
8812 KB |
Output is correct |
22 |
Correct |
1034 ms |
8940 KB |
Output is correct |
23 |
Correct |
1006 ms |
9000 KB |
Output is correct |
24 |
Correct |
952 ms |
8312 KB |
Output is correct |
25 |
Correct |
874 ms |
8512 KB |
Output is correct |
26 |
Correct |
1828 ms |
10076 KB |
Output is correct |
27 |
Correct |
2025 ms |
10196 KB |
Output is correct |
28 |
Correct |
1822 ms |
10232 KB |
Output is correct |
29 |
Correct |
1553 ms |
10192 KB |
Output is correct |
30 |
Correct |
2056 ms |
10168 KB |
Output is correct |
31 |
Correct |
2104 ms |
10116 KB |
Output is correct |
32 |
Correct |
2082 ms |
10120 KB |
Output is correct |
33 |
Correct |
1788 ms |
10308 KB |
Output is correct |
34 |
Correct |
1824 ms |
10248 KB |
Output is correct |
35 |
Correct |
1825 ms |
10392 KB |
Output is correct |
36 |
Correct |
1573 ms |
10288 KB |
Output is correct |
37 |
Correct |
1479 ms |
10212 KB |
Output is correct |
38 |
Correct |
1466 ms |
10160 KB |
Output is correct |
39 |
Correct |
1312 ms |
10412 KB |
Output is correct |
40 |
Correct |
1313 ms |
10560 KB |
Output is correct |
41 |
Correct |
1314 ms |
10684 KB |
Output is correct |
42 |
Correct |
1182 ms |
9960 KB |
Output is correct |
43 |
Correct |
1159 ms |
9716 KB |
Output is correct |
44 |
Correct |
1146 ms |
9828 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 |
44 ms |
1004 KB |
Output is correct |
4 |
Correct |
21 ms |
1004 KB |
Output is correct |
5 |
Correct |
47 ms |
980 KB |
Output is correct |
6 |
Correct |
42 ms |
876 KB |
Output is correct |
7 |
Correct |
44 ms |
1004 KB |
Output is correct |
8 |
Correct |
48 ms |
876 KB |
Output is correct |
9 |
Correct |
39 ms |
876 KB |
Output is correct |
10 |
Correct |
46 ms |
876 KB |
Output is correct |
11 |
Correct |
46 ms |
876 KB |
Output is correct |
12 |
Correct |
47 ms |
876 KB |
Output is correct |
13 |
Correct |
56 ms |
876 KB |
Output is correct |
14 |
Correct |
53 ms |
984 KB |
Output is correct |
15 |
Correct |
49 ms |
876 KB |
Output is correct |
16 |
Correct |
42 ms |
1004 KB |
Output is correct |
17 |
Correct |
43 ms |
876 KB |
Output is correct |
18 |
Correct |
1747 ms |
10028 KB |
Output is correct |
19 |
Correct |
1790 ms |
10060 KB |
Output is correct |
20 |
Correct |
1775 ms |
10116 KB |
Output is correct |
21 |
Correct |
1874 ms |
10304 KB |
Output is correct |
22 |
Correct |
1918 ms |
10260 KB |
Output is correct |
23 |
Correct |
2436 ms |
10176 KB |
Output is correct |
24 |
Correct |
2441 ms |
10184 KB |
Output is correct |
25 |
Correct |
2442 ms |
10268 KB |
Output is correct |
26 |
Correct |
161 ms |
6764 KB |
Output is correct |
27 |
Correct |
1501 ms |
10148 KB |
Output is correct |
28 |
Correct |
1510 ms |
10144 KB |
Output is correct |
29 |
Correct |
1648 ms |
10480 KB |
Output is correct |
30 |
Correct |
1601 ms |
9792 KB |
Output is correct |
31 |
Correct |
1513 ms |
8652 KB |
Output is correct |
32 |
Correct |
947 ms |
6924 KB |
Output is correct |
33 |
Correct |
1500 ms |
8672 KB |
Output is correct |
34 |
Correct |
1371 ms |
8840 KB |
Output is correct |
35 |
Correct |
165 ms |
6792 KB |
Output is correct |
36 |
Correct |
1477 ms |
8656 KB |
Output is correct |
37 |
Correct |
1285 ms |
8576 KB |
Output is correct |
38 |
Correct |
1203 ms |
8812 KB |
Output is correct |
39 |
Correct |
1034 ms |
8940 KB |
Output is correct |
40 |
Correct |
1006 ms |
9000 KB |
Output is correct |
41 |
Correct |
952 ms |
8312 KB |
Output is correct |
42 |
Correct |
874 ms |
8512 KB |
Output is correct |
43 |
Correct |
2466 ms |
13712 KB |
Output is correct |
44 |
Correct |
182 ms |
6764 KB |
Output is correct |
45 |
Correct |
215 ms |
7004 KB |
Output is correct |
46 |
Correct |
199 ms |
7136 KB |
Output is correct |
47 |
Correct |
2204 ms |
13440 KB |
Output is correct |
48 |
Correct |
2468 ms |
13728 KB |
Output is correct |
49 |
Correct |
2260 ms |
13720 KB |
Output is correct |
50 |
Correct |
1197 ms |
10704 KB |
Output is correct |
51 |
Correct |
1214 ms |
10604 KB |
Output is correct |
52 |
Correct |
1183 ms |
10584 KB |
Output is correct |
53 |
Correct |
1876 ms |
12452 KB |
Output is correct |
54 |
Correct |
1884 ms |
12740 KB |
Output is correct |
55 |
Correct |
1946 ms |
12504 KB |
Output is correct |
56 |
Correct |
1968 ms |
13432 KB |
Output is correct |
57 |
Correct |
2132 ms |
13572 KB |
Output is correct |
58 |
Correct |
2605 ms |
13672 KB |
Output is correct |
59 |
Correct |
2370 ms |
13392 KB |
Output is correct |
60 |
Correct |
2389 ms |
13572 KB |
Output is correct |
61 |
Correct |
2648 ms |
13396 KB |
Output is correct |
62 |
Correct |
2025 ms |
13284 KB |
Output is correct |
63 |
Correct |
2047 ms |
13028 KB |
Output is correct |
64 |
Correct |
2313 ms |
13452 KB |
Output is correct |
65 |
Correct |
2259 ms |
12560 KB |
Output is correct |
66 |
Correct |
1828 ms |
10076 KB |
Output is correct |
67 |
Correct |
2025 ms |
10196 KB |
Output is correct |
68 |
Correct |
1822 ms |
10232 KB |
Output is correct |
69 |
Correct |
1553 ms |
10192 KB |
Output is correct |
70 |
Correct |
2056 ms |
10168 KB |
Output is correct |
71 |
Correct |
2104 ms |
10116 KB |
Output is correct |
72 |
Correct |
2082 ms |
10120 KB |
Output is correct |
73 |
Correct |
1788 ms |
10308 KB |
Output is correct |
74 |
Correct |
1824 ms |
10248 KB |
Output is correct |
75 |
Correct |
1825 ms |
10392 KB |
Output is correct |
76 |
Correct |
1573 ms |
10288 KB |
Output is correct |
77 |
Correct |
1479 ms |
10212 KB |
Output is correct |
78 |
Correct |
1466 ms |
10160 KB |
Output is correct |
79 |
Correct |
1312 ms |
10412 KB |
Output is correct |
80 |
Correct |
1313 ms |
10560 KB |
Output is correct |
81 |
Correct |
1314 ms |
10684 KB |
Output is correct |
82 |
Correct |
1182 ms |
9960 KB |
Output is correct |
83 |
Correct |
1159 ms |
9716 KB |
Output is correct |
84 |
Correct |
1146 ms |
9828 KB |
Output is correct |
85 |
Correct |
2967 ms |
13252 KB |
Output is correct |
86 |
Correct |
256 ms |
8808 KB |
Output is correct |
87 |
Correct |
187 ms |
8924 KB |
Output is correct |
88 |
Correct |
2629 ms |
15624 KB |
Output is correct |
89 |
Correct |
2833 ms |
17092 KB |
Output is correct |
90 |
Correct |
2714 ms |
15400 KB |
Output is correct |
91 |
Correct |
1922 ms |
12908 KB |
Output is correct |
92 |
Correct |
1975 ms |
13060 KB |
Output is correct |
93 |
Correct |
2399 ms |
12880 KB |
Output is correct |
94 |
Correct |
2480 ms |
15432 KB |
Output is correct |
95 |
Correct |
2418 ms |
15800 KB |
Output is correct |
96 |
Correct |
2616 ms |
15580 KB |
Output is correct |
97 |
Correct |
2397 ms |
15868 KB |
Output is correct |
98 |
Correct |
2344 ms |
15332 KB |
Output is correct |
99 |
Correct |
2916 ms |
16900 KB |
Output is correct |
100 |
Correct |
2859 ms |
16968 KB |
Output is correct |
101 |
Correct |
2967 ms |
17224 KB |
Output is correct |
102 |
Correct |
2936 ms |
16992 KB |
Output is correct |
103 |
Correct |
2846 ms |
16064 KB |
Output is correct |
104 |
Correct |
2785 ms |
15848 KB |
Output is correct |
105 |
Correct |
2229 ms |
15476 KB |
Output is correct |
106 |
Correct |
1870 ms |
15124 KB |
Output is correct |
107 |
Correct |
2308 ms |
16096 KB |
Output is correct |
108 |
Correct |
2851 ms |
16704 KB |
Output is correct |
109 |
Correct |
2772 ms |
14588 KB |
Output is correct |