#pragma GCC optimize("O3")
#include<stdint.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/rope>
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define VIS(it,con) for(auto it=con.begin();it!=con.end();++it)
#define pob pop_back
#define pf push_front
#define pof pop_front
#define MIN(x,y) (x=min(x,(y)))
#define MAX(x,y) (x=max(x,(y)))
#define mid (l+r>>1)
#define lch (idx*2+1)
#define rch (idx*2+2)
/*****************************************************************************/
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
#define REP(i,j,k) for(register int i=(j);i<(k);++i)
#define RREP(i,j,k) for(register int i=int(j)-1;i>=(k);--i)
#define ALL(a) a.begin(),a.end()
#define pb push_back
#define F first
#define S second
#define endl '\n'
// #define __debug
#ifdef __debug
#define IOS (void)0
#define de(...) cerr<<__VA_ARGS__
#define ar(a,s,t) {REP(__i,s,t)de(a[__i]<<' ');de(endl);}
#else
#define IOS cin.tie(0),cout.tie(0),ios_base::sync_with_stdio(false)
#define de(...) (void)0
#define ar(...) (void)0
#endif
/***********************************default***********************************/
struct tup{int F,S,T;};
const int maxn=5e4+9,maxm=1e5+9,maxq=1e5+9,bl=800;
int n,m,q,fa[maxn],sz[maxn],res[maxq];
tup eds[maxm],qrs[maxq];
set<pii>st;
vector<pii>rf,rs;
vector<int>p;
bool mrk[maxm];
void init(int k){REP(i,0,k)fa[i]=i,sz[i]=1;}
int find(int x,bool c){return x==fa[x]?x:c?fa[x]=find(fa[x],c):find(fa[x],c);}
void unite(int x,int y,bool c,bool r){
x=find(x,c),y=find(y,c);
if(x==y)return;
if(sz[x]>sz[y])swap(x,y);
if(r)rf.pb({x,fa[x]}),rs.pb({y,sz[y]});
fa[x]=y,sz[y]+=sz[x];
}
void restore(){
RREP(i,rf.size(),0)fa[rf[i].F]=rf[i].S;
RREP(i,rs.size(),0)sz[rs[i].F]=rs[i].S;
}
main(){
IOS;
cin>>n>>m;
REP(i,0,m){
int u,v,w;cin>>u>>v>>w,--u,--v,w=-w;
eds[i]={u,v,w};
st.insert({w,i});
}
cin>>q;
REP(i,0,q)cin>>qrs[i].F>>qrs[i].S>>qrs[i].T,--qrs[i].S,qrs[i].T=-qrs[i].T;
for(int l=0;l<q;l+=bl){
int r=min(l+bl,q);
p.clear();
REP(i,l,r)if(qrs[i].F==2)p.pb(i);
sort(ALL(p),[](int a,int b){return qrs[a].T<qrs[b].T;});
init(n);
auto it=st.begin();
REP(i,0,p.size()){
REP(i,l,r)if(qrs[i].F==1)mrk[qrs[i].S]=1;
tup&qq=qrs[p[i]];
while(it!=st.end()&&it->F<=qq.T){
if(!mrk[it->S])unite(eds[it->S].F,eds[it->S].S,1,0);
++it;
}
rf.clear(),rs.clear();
RREP(j,p[i],l){
tup&tq=qrs[j];
if(tq.F==1&&mrk[tq.S]){
if(tq.T<=qq.T)unite(eds[tq.S].F,eds[tq.S].S,0,1);
mrk[tq.S]=0;
}
}
REP(j,p[i],r){
tup&tq=qrs[j];
if(tq.F==1&&mrk[tq.S]){
if(eds[tq.S].T<=qq.T)unite(eds[tq.S].F,eds[tq.S].S,0,1);
mrk[tq.S]=0;
}
}
res[p[i]]=sz[find(qq.S,0)];
restore();
}
REP(i,l,r){
tup&qq=qrs[i];
if(qq.F==1){
st.erase(st.find({eds[qq.S].T,qq.S}));
st.insert({eds[qq.S].T=qq.T,qq.S});
}
}
}
REP(i,0,q)if(qrs[i].F==2)cout<<res[i]<<endl;
}
Compilation message
bridges.cpp:65:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main(){
^
bridges.cpp: In function 'int main()':
bridges.cpp:21:44: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define REP(i,j,k) for(register int i=(j);i<(k);++i)
^
bridges.cpp:82:3: note: in expansion of macro 'REP'
REP(i,0,p.size()){
^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
504 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
30 ms |
760 KB |
Output is correct |
4 |
Correct |
19 ms |
760 KB |
Output is correct |
5 |
Correct |
39 ms |
760 KB |
Output is correct |
6 |
Correct |
33 ms |
760 KB |
Output is correct |
7 |
Correct |
36 ms |
632 KB |
Output is correct |
8 |
Correct |
38 ms |
760 KB |
Output is correct |
9 |
Correct |
35 ms |
636 KB |
Output is correct |
10 |
Correct |
41 ms |
840 KB |
Output is correct |
11 |
Correct |
40 ms |
760 KB |
Output is correct |
12 |
Correct |
40 ms |
760 KB |
Output is correct |
13 |
Correct |
45 ms |
760 KB |
Output is correct |
14 |
Correct |
42 ms |
760 KB |
Output is correct |
15 |
Correct |
41 ms |
760 KB |
Output is correct |
16 |
Correct |
36 ms |
632 KB |
Output is correct |
17 |
Correct |
37 ms |
632 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1594 ms |
7436 KB |
Output is correct |
2 |
Correct |
1650 ms |
7884 KB |
Output is correct |
3 |
Correct |
1578 ms |
7676 KB |
Output is correct |
4 |
Correct |
1675 ms |
7808 KB |
Output is correct |
5 |
Correct |
1660 ms |
7616 KB |
Output is correct |
6 |
Correct |
2524 ms |
8080 KB |
Output is correct |
7 |
Correct |
2556 ms |
8004 KB |
Output is correct |
8 |
Correct |
2537 ms |
8056 KB |
Output is correct |
9 |
Correct |
170 ms |
3448 KB |
Output is correct |
10 |
Correct |
1205 ms |
7356 KB |
Output is correct |
11 |
Correct |
1157 ms |
7416 KB |
Output is correct |
12 |
Correct |
1268 ms |
8312 KB |
Output is correct |
13 |
Correct |
1424 ms |
7968 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1290 ms |
6700 KB |
Output is correct |
2 |
Correct |
827 ms |
4396 KB |
Output is correct |
3 |
Correct |
1362 ms |
6748 KB |
Output is correct |
4 |
Correct |
1191 ms |
6916 KB |
Output is correct |
5 |
Correct |
170 ms |
3448 KB |
Output is correct |
6 |
Correct |
1319 ms |
6788 KB |
Output is correct |
7 |
Correct |
1080 ms |
6732 KB |
Output is correct |
8 |
Correct |
1000 ms |
6776 KB |
Output is correct |
9 |
Correct |
842 ms |
6844 KB |
Output is correct |
10 |
Correct |
800 ms |
6880 KB |
Output is correct |
11 |
Correct |
833 ms |
6532 KB |
Output is correct |
12 |
Correct |
766 ms |
6632 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1935 ms |
11380 KB |
Output is correct |
2 |
Correct |
173 ms |
3484 KB |
Output is correct |
3 |
Correct |
236 ms |
8336 KB |
Output is correct |
4 |
Correct |
126 ms |
8440 KB |
Output is correct |
5 |
Correct |
1446 ms |
11060 KB |
Output is correct |
6 |
Correct |
1951 ms |
11684 KB |
Output is correct |
7 |
Correct |
1066 ms |
11128 KB |
Output is correct |
8 |
Correct |
937 ms |
8184 KB |
Output is correct |
9 |
Correct |
863 ms |
8312 KB |
Output is correct |
10 |
Correct |
1000 ms |
8252 KB |
Output is correct |
11 |
Correct |
1438 ms |
10228 KB |
Output is correct |
12 |
Correct |
1366 ms |
10236 KB |
Output is correct |
13 |
Correct |
1325 ms |
10384 KB |
Output is correct |
14 |
Correct |
1000 ms |
11000 KB |
Output is correct |
15 |
Correct |
1055 ms |
11256 KB |
Output is correct |
16 |
Correct |
2337 ms |
11756 KB |
Output is correct |
17 |
Correct |
2092 ms |
11836 KB |
Output is correct |
18 |
Correct |
1895 ms |
10732 KB |
Output is correct |
19 |
Correct |
2080 ms |
10760 KB |
Output is correct |
20 |
Correct |
1672 ms |
10000 KB |
Output is correct |
21 |
Correct |
1515 ms |
9892 KB |
Output is correct |
22 |
Correct |
2414 ms |
10688 KB |
Output is correct |
23 |
Correct |
1392 ms |
9720 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1594 ms |
7436 KB |
Output is correct |
2 |
Correct |
1650 ms |
7884 KB |
Output is correct |
3 |
Correct |
1578 ms |
7676 KB |
Output is correct |
4 |
Correct |
1675 ms |
7808 KB |
Output is correct |
5 |
Correct |
1660 ms |
7616 KB |
Output is correct |
6 |
Correct |
2524 ms |
8080 KB |
Output is correct |
7 |
Correct |
2556 ms |
8004 KB |
Output is correct |
8 |
Correct |
2537 ms |
8056 KB |
Output is correct |
9 |
Correct |
170 ms |
3448 KB |
Output is correct |
10 |
Correct |
1205 ms |
7356 KB |
Output is correct |
11 |
Correct |
1157 ms |
7416 KB |
Output is correct |
12 |
Correct |
1268 ms |
8312 KB |
Output is correct |
13 |
Correct |
1424 ms |
7968 KB |
Output is correct |
14 |
Correct |
1290 ms |
6700 KB |
Output is correct |
15 |
Correct |
827 ms |
4396 KB |
Output is correct |
16 |
Correct |
1362 ms |
6748 KB |
Output is correct |
17 |
Correct |
1191 ms |
6916 KB |
Output is correct |
18 |
Correct |
170 ms |
3448 KB |
Output is correct |
19 |
Correct |
1319 ms |
6788 KB |
Output is correct |
20 |
Correct |
1080 ms |
6732 KB |
Output is correct |
21 |
Correct |
1000 ms |
6776 KB |
Output is correct |
22 |
Correct |
842 ms |
6844 KB |
Output is correct |
23 |
Correct |
800 ms |
6880 KB |
Output is correct |
24 |
Correct |
833 ms |
6532 KB |
Output is correct |
25 |
Correct |
766 ms |
6632 KB |
Output is correct |
26 |
Correct |
1804 ms |
8304 KB |
Output is correct |
27 |
Correct |
1925 ms |
8312 KB |
Output is correct |
28 |
Correct |
1649 ms |
8368 KB |
Output is correct |
29 |
Correct |
1246 ms |
8440 KB |
Output is correct |
30 |
Correct |
2074 ms |
8312 KB |
Output is correct |
31 |
Correct |
2041 ms |
8188 KB |
Output is correct |
32 |
Correct |
2218 ms |
8248 KB |
Output is correct |
33 |
Correct |
1796 ms |
8328 KB |
Output is correct |
34 |
Correct |
1814 ms |
8312 KB |
Output is correct |
35 |
Correct |
1968 ms |
8568 KB |
Output is correct |
36 |
Correct |
1591 ms |
8356 KB |
Output is correct |
37 |
Correct |
1351 ms |
8352 KB |
Output is correct |
38 |
Correct |
1303 ms |
8116 KB |
Output is correct |
39 |
Correct |
1018 ms |
8204 KB |
Output is correct |
40 |
Correct |
1040 ms |
8312 KB |
Output is correct |
41 |
Correct |
1024 ms |
8504 KB |
Output is correct |
42 |
Correct |
948 ms |
8252 KB |
Output is correct |
43 |
Correct |
938 ms |
8224 KB |
Output is correct |
44 |
Correct |
914 ms |
8184 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
504 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
30 ms |
760 KB |
Output is correct |
4 |
Correct |
19 ms |
760 KB |
Output is correct |
5 |
Correct |
39 ms |
760 KB |
Output is correct |
6 |
Correct |
33 ms |
760 KB |
Output is correct |
7 |
Correct |
36 ms |
632 KB |
Output is correct |
8 |
Correct |
38 ms |
760 KB |
Output is correct |
9 |
Correct |
35 ms |
636 KB |
Output is correct |
10 |
Correct |
41 ms |
840 KB |
Output is correct |
11 |
Correct |
40 ms |
760 KB |
Output is correct |
12 |
Correct |
40 ms |
760 KB |
Output is correct |
13 |
Correct |
45 ms |
760 KB |
Output is correct |
14 |
Correct |
42 ms |
760 KB |
Output is correct |
15 |
Correct |
41 ms |
760 KB |
Output is correct |
16 |
Correct |
36 ms |
632 KB |
Output is correct |
17 |
Correct |
37 ms |
632 KB |
Output is correct |
18 |
Correct |
1594 ms |
7436 KB |
Output is correct |
19 |
Correct |
1650 ms |
7884 KB |
Output is correct |
20 |
Correct |
1578 ms |
7676 KB |
Output is correct |
21 |
Correct |
1675 ms |
7808 KB |
Output is correct |
22 |
Correct |
1660 ms |
7616 KB |
Output is correct |
23 |
Correct |
2524 ms |
8080 KB |
Output is correct |
24 |
Correct |
2556 ms |
8004 KB |
Output is correct |
25 |
Correct |
2537 ms |
8056 KB |
Output is correct |
26 |
Correct |
170 ms |
3448 KB |
Output is correct |
27 |
Correct |
1205 ms |
7356 KB |
Output is correct |
28 |
Correct |
1157 ms |
7416 KB |
Output is correct |
29 |
Correct |
1268 ms |
8312 KB |
Output is correct |
30 |
Correct |
1424 ms |
7968 KB |
Output is correct |
31 |
Correct |
1290 ms |
6700 KB |
Output is correct |
32 |
Correct |
827 ms |
4396 KB |
Output is correct |
33 |
Correct |
1362 ms |
6748 KB |
Output is correct |
34 |
Correct |
1191 ms |
6916 KB |
Output is correct |
35 |
Correct |
170 ms |
3448 KB |
Output is correct |
36 |
Correct |
1319 ms |
6788 KB |
Output is correct |
37 |
Correct |
1080 ms |
6732 KB |
Output is correct |
38 |
Correct |
1000 ms |
6776 KB |
Output is correct |
39 |
Correct |
842 ms |
6844 KB |
Output is correct |
40 |
Correct |
800 ms |
6880 KB |
Output is correct |
41 |
Correct |
833 ms |
6532 KB |
Output is correct |
42 |
Correct |
766 ms |
6632 KB |
Output is correct |
43 |
Correct |
1935 ms |
11380 KB |
Output is correct |
44 |
Correct |
173 ms |
3484 KB |
Output is correct |
45 |
Correct |
236 ms |
8336 KB |
Output is correct |
46 |
Correct |
126 ms |
8440 KB |
Output is correct |
47 |
Correct |
1446 ms |
11060 KB |
Output is correct |
48 |
Correct |
1951 ms |
11684 KB |
Output is correct |
49 |
Correct |
1066 ms |
11128 KB |
Output is correct |
50 |
Correct |
937 ms |
8184 KB |
Output is correct |
51 |
Correct |
863 ms |
8312 KB |
Output is correct |
52 |
Correct |
1000 ms |
8252 KB |
Output is correct |
53 |
Correct |
1438 ms |
10228 KB |
Output is correct |
54 |
Correct |
1366 ms |
10236 KB |
Output is correct |
55 |
Correct |
1325 ms |
10384 KB |
Output is correct |
56 |
Correct |
1000 ms |
11000 KB |
Output is correct |
57 |
Correct |
1055 ms |
11256 KB |
Output is correct |
58 |
Correct |
2337 ms |
11756 KB |
Output is correct |
59 |
Correct |
2092 ms |
11836 KB |
Output is correct |
60 |
Correct |
1895 ms |
10732 KB |
Output is correct |
61 |
Correct |
2080 ms |
10760 KB |
Output is correct |
62 |
Correct |
1672 ms |
10000 KB |
Output is correct |
63 |
Correct |
1515 ms |
9892 KB |
Output is correct |
64 |
Correct |
2414 ms |
10688 KB |
Output is correct |
65 |
Correct |
1392 ms |
9720 KB |
Output is correct |
66 |
Correct |
1804 ms |
8304 KB |
Output is correct |
67 |
Correct |
1925 ms |
8312 KB |
Output is correct |
68 |
Correct |
1649 ms |
8368 KB |
Output is correct |
69 |
Correct |
1246 ms |
8440 KB |
Output is correct |
70 |
Correct |
2074 ms |
8312 KB |
Output is correct |
71 |
Correct |
2041 ms |
8188 KB |
Output is correct |
72 |
Correct |
2218 ms |
8248 KB |
Output is correct |
73 |
Correct |
1796 ms |
8328 KB |
Output is correct |
74 |
Correct |
1814 ms |
8312 KB |
Output is correct |
75 |
Correct |
1968 ms |
8568 KB |
Output is correct |
76 |
Correct |
1591 ms |
8356 KB |
Output is correct |
77 |
Correct |
1351 ms |
8352 KB |
Output is correct |
78 |
Correct |
1303 ms |
8116 KB |
Output is correct |
79 |
Correct |
1018 ms |
8204 KB |
Output is correct |
80 |
Correct |
1040 ms |
8312 KB |
Output is correct |
81 |
Correct |
1024 ms |
8504 KB |
Output is correct |
82 |
Correct |
948 ms |
8252 KB |
Output is correct |
83 |
Correct |
938 ms |
8224 KB |
Output is correct |
84 |
Correct |
914 ms |
8184 KB |
Output is correct |
85 |
Correct |
2418 ms |
10468 KB |
Output is correct |
86 |
Correct |
290 ms |
8604 KB |
Output is correct |
87 |
Correct |
108 ms |
8440 KB |
Output is correct |
88 |
Correct |
1470 ms |
10648 KB |
Output is correct |
89 |
Correct |
2316 ms |
10632 KB |
Output is correct |
90 |
Correct |
1391 ms |
10488 KB |
Output is correct |
91 |
Correct |
1842 ms |
7296 KB |
Output is correct |
92 |
Correct |
1874 ms |
7440 KB |
Output is correct |
93 |
Correct |
2812 ms |
7624 KB |
Output is correct |
94 |
Correct |
2152 ms |
9224 KB |
Output is correct |
95 |
Correct |
2092 ms |
9264 KB |
Output is correct |
96 |
Correct |
1912 ms |
9404 KB |
Output is correct |
97 |
Correct |
1313 ms |
11040 KB |
Output is correct |
98 |
Correct |
1292 ms |
10552 KB |
Output is correct |
99 |
Correct |
2891 ms |
10764 KB |
Output is correct |
100 |
Correct |
2737 ms |
12392 KB |
Output is correct |
101 |
Correct |
2668 ms |
12648 KB |
Output is correct |
102 |
Correct |
2759 ms |
12512 KB |
Output is correct |
103 |
Correct |
2114 ms |
10772 KB |
Output is correct |
104 |
Correct |
1860 ms |
11000 KB |
Output is correct |
105 |
Correct |
1806 ms |
10744 KB |
Output is correct |
106 |
Correct |
1414 ms |
10104 KB |
Output is correct |
107 |
Correct |
1845 ms |
10968 KB |
Output is correct |
108 |
Correct |
2341 ms |
11900 KB |
Output is correct |
109 |
Correct |
1589 ms |
9592 KB |
Output is correct |