# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
550178 |
2022-04-17T13:19:42 Z |
zaneyu |
Bridges (APIO19_bridges) |
C++14 |
|
2433 ms |
137112 KB |
/*input
7 8
1 2 5
1 6 5
2 3 5
2 7 5
3 4 5
4 5 5
5 6 5
6 7 5
12
2 1 6
1 1 1
2 1 2
1 2 3
2 2 2
1 5 2
1 3 1
2 2 4
2 4 2
1 8 1
2 1 1
2 1 3
*/
#include<bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<long long,null_type,less_equal<long long>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;
#pragma GCC optimize("Ofast")
//#pragma GCC target("avx2")
//order_of_key #of elements less than x
// find_by_order kth element
using ll=long long;
using ld=long double;
using pii=pair<int,int>;
#define f first
#define s second
#define pb push_back
#define REP(i,n) for(int i=0;i<n;i++)
#define REP1(i,n) for(int i=1;i<=n;i++)
#define FILL(n,x) memset(n,x,sizeof(n))
#define ALL(_a) _a.begin(),_a.end()
#define sz(x) (int)x.size()
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()),c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
const ll maxn=1e5+5;
const ll maxlg=__lg(maxn)+2;
const ll INF64=4e18;
const int INF=0x3f3f3f3f;
int MOD=998244353;
const ld PI=acos(-1);
const ld eps=1e-9;
#define lowb(x) x&(-x)
#define MNTO(x,y) x=min(x,(__typeof__(x))y)
#define MXTO(x,y) x=max(x,(__typeof__(x))y)
template<typename T1,typename T2>
ostream& operator<<(ostream& out,pair<T1,T2> P){
out<<P.f+1<<' '<<P.s+1;
return out;
}
template<typename T>
ostream& operator<<(ostream& out,vector<T> V){
REP(i,sz(V)) out<<V[i]<<((i!=sz(V)-1)?" ":"\n");
return out;
}
ll mult(ll a,ll b){
return a*b%MOD;
}
ll mult(ll a,ll b,ll mod){
ll res=0;
while(b){
if(b&1) res=(res+a)%mod;
a=(a+a)%mod;
b>>=1;
}
return res;
}
ll mypow(ll a,ll b,ll mod){
if(b<=0) return 1;
a%=mod;
ll res=1LL;
while(b){
if(b&1) res=(res*a)%mod;
a=(a*a)%mod;
b>>=1;
}
return res;
}
ll mypow(ll a,ll b){
a%=MOD;
if(a==0) return 0;
if(b<=0) return 1;
ll res=1LL;
while(b){
if(b&1) res=(res*a)%MOD;
a=(a*a)%MOD;
b>>=1;
}
return res;
}
vector<pair<int,pii>> ed;
pair<pii,int> qq[maxn];
const int blk=800;
int par[maxn],rank1[maxn];
int cm=0;
vector<pii> rb;
inline void init(int n){
REP1(i,n) par[i]=i,rank1[i]=1;
cm=n;
}
inline int find(int u){
if(par[u]==u) return u;
return find(par[u]);
}
inline void merge(int a,int b){
a=find(a),b=find(b);
if(a==b){
rb.pb({a,a});
return;
}
if(rank1[a]>rank1[b]) swap(a,b);
--cm;
par[a]=b;
rank1[b]+=rank1[a];
rb.pb({a,b});
}
inline void roll(){
pii z=rb.back();
int a=z.f,b=z.s;
rb.pop_back();
if(a==b) return;
++cm;
par[a]=a;
rank1[b]-=rank1[a];
}
bool in[maxn];
int ans[maxn];
bool vis[maxn];
int main(){
ios::sync_with_stdio(false),cin.tie(0);
int n,m;
cin>>n>>m;
REP(i,m){
int a,b,c;
cin>>a>>b>>c;
c=-c;
ed.pb({c,{a,b}});
}
int q;
cin>>q;
REP(i,q) ans[i]=-1;
REP(i,q/blk+1){
int sz=min(blk,q-i*blk);
vector<pair<pii,int>> qr;
vector<pair<int,pii>> ed1;
REP(j,sz){
int x,y,z;
cin>>x>>y>>z;
z=-z;
if(x==1) --y,in[y]=1,ed1.pb({i*blk+j,{y,z}});
else qr.pb({{z,y},i*blk+j});
qq[j]={{x,y},z};
}
reverse(ALL(ed1));
vector<pair<int,pii>> ed2;
REP(i,m){
if(!in[i]) ed2.pb(ed[i]);
else ed1.pb({-1,{i,ed[i].f}});
}
sort(ALL(ed2));
sort(ALL(qr));
init(n);
int p=0;
for(auto x:qr){
while(p<sz(ed2) and ed2[p].f<=x.f.f){
merge(ed2[p].s.f,ed2[p].s.s);
++p;
}
int cnt=0;
for(auto z:ed1){
if(z.f<=x.s and z.s.s<=x.f.f and !vis[z.s.f]) merge(ed[z.s.f].s.f,ed[z.s.f].s.s),++cnt;
if(z.f<=x.s) vis[z.s.f]=1;
}
for(auto z:ed1) vis[z.s.f]=0;
ans[x.s]=rank1[find(x.f.s)];
REP(j,cnt) roll();
}
REP(j,sz){
if(qq[j].f.f==1){
ed[qq[j].f.s].f=qq[j].s;
in[qq[j].f.s]=0;
}
}
}
REP(i,q) if(ans[i]!=-1) cout<<ans[i]<<'\n';
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
332 KB |
Output is correct |
3 |
Correct |
38 ms |
808 KB |
Output is correct |
4 |
Correct |
4 ms |
560 KB |
Output is correct |
5 |
Correct |
27 ms |
596 KB |
Output is correct |
6 |
Correct |
25 ms |
468 KB |
Output is correct |
7 |
Correct |
24 ms |
476 KB |
Output is correct |
8 |
Correct |
24 ms |
576 KB |
Output is correct |
9 |
Correct |
29 ms |
484 KB |
Output is correct |
10 |
Correct |
22 ms |
472 KB |
Output is correct |
11 |
Correct |
24 ms |
468 KB |
Output is correct |
12 |
Correct |
25 ms |
516 KB |
Output is correct |
13 |
Correct |
31 ms |
580 KB |
Output is correct |
14 |
Correct |
28 ms |
584 KB |
Output is correct |
15 |
Correct |
25 ms |
572 KB |
Output is correct |
16 |
Correct |
25 ms |
480 KB |
Output is correct |
17 |
Correct |
25 ms |
596 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1324 ms |
70060 KB |
Output is correct |
2 |
Correct |
1348 ms |
69628 KB |
Output is correct |
3 |
Correct |
1364 ms |
69544 KB |
Output is correct |
4 |
Correct |
1367 ms |
69664 KB |
Output is correct |
5 |
Correct |
1395 ms |
69576 KB |
Output is correct |
6 |
Correct |
1804 ms |
69592 KB |
Output is correct |
7 |
Correct |
1824 ms |
69468 KB |
Output is correct |
8 |
Correct |
1801 ms |
69868 KB |
Output is correct |
9 |
Correct |
34 ms |
1632 KB |
Output is correct |
10 |
Correct |
1311 ms |
69604 KB |
Output is correct |
11 |
Correct |
1341 ms |
69480 KB |
Output is correct |
12 |
Correct |
1115 ms |
69584 KB |
Output is correct |
13 |
Correct |
1181 ms |
69668 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1041 ms |
36156 KB |
Output is correct |
2 |
Correct |
758 ms |
9928 KB |
Output is correct |
3 |
Correct |
1168 ms |
35736 KB |
Output is correct |
4 |
Correct |
1049 ms |
35588 KB |
Output is correct |
5 |
Correct |
36 ms |
1640 KB |
Output is correct |
6 |
Correct |
1125 ms |
35832 KB |
Output is correct |
7 |
Correct |
985 ms |
35720 KB |
Output is correct |
8 |
Correct |
915 ms |
35840 KB |
Output is correct |
9 |
Correct |
696 ms |
35704 KB |
Output is correct |
10 |
Correct |
633 ms |
35644 KB |
Output is correct |
11 |
Correct |
740 ms |
35640 KB |
Output is correct |
12 |
Correct |
646 ms |
35588 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1599 ms |
137112 KB |
Output is correct |
2 |
Correct |
35 ms |
1484 KB |
Output is correct |
3 |
Correct |
171 ms |
21256 KB |
Output is correct |
4 |
Correct |
199 ms |
21308 KB |
Output is correct |
5 |
Correct |
1842 ms |
137032 KB |
Output is correct |
6 |
Correct |
1530 ms |
136928 KB |
Output is correct |
7 |
Correct |
1809 ms |
137088 KB |
Output is correct |
8 |
Correct |
772 ms |
69384 KB |
Output is correct |
9 |
Correct |
726 ms |
69356 KB |
Output is correct |
10 |
Correct |
771 ms |
69352 KB |
Output is correct |
11 |
Correct |
1176 ms |
136416 KB |
Output is correct |
12 |
Correct |
1184 ms |
136388 KB |
Output is correct |
13 |
Correct |
1237 ms |
136372 KB |
Output is correct |
14 |
Correct |
1810 ms |
137112 KB |
Output is correct |
15 |
Correct |
1804 ms |
137044 KB |
Output is correct |
16 |
Correct |
1551 ms |
137000 KB |
Output is correct |
17 |
Correct |
1592 ms |
137000 KB |
Output is correct |
18 |
Correct |
1557 ms |
137004 KB |
Output is correct |
19 |
Correct |
1550 ms |
136868 KB |
Output is correct |
20 |
Correct |
1304 ms |
136504 KB |
Output is correct |
21 |
Correct |
1353 ms |
136616 KB |
Output is correct |
22 |
Correct |
1522 ms |
136756 KB |
Output is correct |
23 |
Correct |
1443 ms |
136312 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1324 ms |
70060 KB |
Output is correct |
2 |
Correct |
1348 ms |
69628 KB |
Output is correct |
3 |
Correct |
1364 ms |
69544 KB |
Output is correct |
4 |
Correct |
1367 ms |
69664 KB |
Output is correct |
5 |
Correct |
1395 ms |
69576 KB |
Output is correct |
6 |
Correct |
1804 ms |
69592 KB |
Output is correct |
7 |
Correct |
1824 ms |
69468 KB |
Output is correct |
8 |
Correct |
1801 ms |
69868 KB |
Output is correct |
9 |
Correct |
34 ms |
1632 KB |
Output is correct |
10 |
Correct |
1311 ms |
69604 KB |
Output is correct |
11 |
Correct |
1341 ms |
69480 KB |
Output is correct |
12 |
Correct |
1115 ms |
69584 KB |
Output is correct |
13 |
Correct |
1181 ms |
69668 KB |
Output is correct |
14 |
Correct |
1041 ms |
36156 KB |
Output is correct |
15 |
Correct |
758 ms |
9928 KB |
Output is correct |
16 |
Correct |
1168 ms |
35736 KB |
Output is correct |
17 |
Correct |
1049 ms |
35588 KB |
Output is correct |
18 |
Correct |
36 ms |
1640 KB |
Output is correct |
19 |
Correct |
1125 ms |
35832 KB |
Output is correct |
20 |
Correct |
985 ms |
35720 KB |
Output is correct |
21 |
Correct |
915 ms |
35840 KB |
Output is correct |
22 |
Correct |
696 ms |
35704 KB |
Output is correct |
23 |
Correct |
633 ms |
35644 KB |
Output is correct |
24 |
Correct |
740 ms |
35640 KB |
Output is correct |
25 |
Correct |
646 ms |
35588 KB |
Output is correct |
26 |
Correct |
1397 ms |
69380 KB |
Output is correct |
27 |
Correct |
1552 ms |
69316 KB |
Output is correct |
28 |
Correct |
1429 ms |
69436 KB |
Output is correct |
29 |
Correct |
1096 ms |
69436 KB |
Output is correct |
30 |
Correct |
1551 ms |
69344 KB |
Output is correct |
31 |
Correct |
1573 ms |
69484 KB |
Output is correct |
32 |
Correct |
1607 ms |
69348 KB |
Output is correct |
33 |
Correct |
1375 ms |
69408 KB |
Output is correct |
34 |
Correct |
1384 ms |
69356 KB |
Output is correct |
35 |
Correct |
1385 ms |
69384 KB |
Output is correct |
36 |
Correct |
1153 ms |
69404 KB |
Output is correct |
37 |
Correct |
1148 ms |
69352 KB |
Output is correct |
38 |
Correct |
1137 ms |
69376 KB |
Output is correct |
39 |
Correct |
890 ms |
69380 KB |
Output is correct |
40 |
Correct |
897 ms |
69388 KB |
Output is correct |
41 |
Correct |
879 ms |
69444 KB |
Output is correct |
42 |
Correct |
874 ms |
69316 KB |
Output is correct |
43 |
Correct |
890 ms |
69400 KB |
Output is correct |
44 |
Correct |
876 ms |
69364 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
332 KB |
Output is correct |
3 |
Correct |
38 ms |
808 KB |
Output is correct |
4 |
Correct |
4 ms |
560 KB |
Output is correct |
5 |
Correct |
27 ms |
596 KB |
Output is correct |
6 |
Correct |
25 ms |
468 KB |
Output is correct |
7 |
Correct |
24 ms |
476 KB |
Output is correct |
8 |
Correct |
24 ms |
576 KB |
Output is correct |
9 |
Correct |
29 ms |
484 KB |
Output is correct |
10 |
Correct |
22 ms |
472 KB |
Output is correct |
11 |
Correct |
24 ms |
468 KB |
Output is correct |
12 |
Correct |
25 ms |
516 KB |
Output is correct |
13 |
Correct |
31 ms |
580 KB |
Output is correct |
14 |
Correct |
28 ms |
584 KB |
Output is correct |
15 |
Correct |
25 ms |
572 KB |
Output is correct |
16 |
Correct |
25 ms |
480 KB |
Output is correct |
17 |
Correct |
25 ms |
596 KB |
Output is correct |
18 |
Correct |
1324 ms |
70060 KB |
Output is correct |
19 |
Correct |
1348 ms |
69628 KB |
Output is correct |
20 |
Correct |
1364 ms |
69544 KB |
Output is correct |
21 |
Correct |
1367 ms |
69664 KB |
Output is correct |
22 |
Correct |
1395 ms |
69576 KB |
Output is correct |
23 |
Correct |
1804 ms |
69592 KB |
Output is correct |
24 |
Correct |
1824 ms |
69468 KB |
Output is correct |
25 |
Correct |
1801 ms |
69868 KB |
Output is correct |
26 |
Correct |
34 ms |
1632 KB |
Output is correct |
27 |
Correct |
1311 ms |
69604 KB |
Output is correct |
28 |
Correct |
1341 ms |
69480 KB |
Output is correct |
29 |
Correct |
1115 ms |
69584 KB |
Output is correct |
30 |
Correct |
1181 ms |
69668 KB |
Output is correct |
31 |
Correct |
1041 ms |
36156 KB |
Output is correct |
32 |
Correct |
758 ms |
9928 KB |
Output is correct |
33 |
Correct |
1168 ms |
35736 KB |
Output is correct |
34 |
Correct |
1049 ms |
35588 KB |
Output is correct |
35 |
Correct |
36 ms |
1640 KB |
Output is correct |
36 |
Correct |
1125 ms |
35832 KB |
Output is correct |
37 |
Correct |
985 ms |
35720 KB |
Output is correct |
38 |
Correct |
915 ms |
35840 KB |
Output is correct |
39 |
Correct |
696 ms |
35704 KB |
Output is correct |
40 |
Correct |
633 ms |
35644 KB |
Output is correct |
41 |
Correct |
740 ms |
35640 KB |
Output is correct |
42 |
Correct |
646 ms |
35588 KB |
Output is correct |
43 |
Correct |
1599 ms |
137112 KB |
Output is correct |
44 |
Correct |
35 ms |
1484 KB |
Output is correct |
45 |
Correct |
171 ms |
21256 KB |
Output is correct |
46 |
Correct |
199 ms |
21308 KB |
Output is correct |
47 |
Correct |
1842 ms |
137032 KB |
Output is correct |
48 |
Correct |
1530 ms |
136928 KB |
Output is correct |
49 |
Correct |
1809 ms |
137088 KB |
Output is correct |
50 |
Correct |
772 ms |
69384 KB |
Output is correct |
51 |
Correct |
726 ms |
69356 KB |
Output is correct |
52 |
Correct |
771 ms |
69352 KB |
Output is correct |
53 |
Correct |
1176 ms |
136416 KB |
Output is correct |
54 |
Correct |
1184 ms |
136388 KB |
Output is correct |
55 |
Correct |
1237 ms |
136372 KB |
Output is correct |
56 |
Correct |
1810 ms |
137112 KB |
Output is correct |
57 |
Correct |
1804 ms |
137044 KB |
Output is correct |
58 |
Correct |
1551 ms |
137000 KB |
Output is correct |
59 |
Correct |
1592 ms |
137000 KB |
Output is correct |
60 |
Correct |
1557 ms |
137004 KB |
Output is correct |
61 |
Correct |
1550 ms |
136868 KB |
Output is correct |
62 |
Correct |
1304 ms |
136504 KB |
Output is correct |
63 |
Correct |
1353 ms |
136616 KB |
Output is correct |
64 |
Correct |
1522 ms |
136756 KB |
Output is correct |
65 |
Correct |
1443 ms |
136312 KB |
Output is correct |
66 |
Correct |
1397 ms |
69380 KB |
Output is correct |
67 |
Correct |
1552 ms |
69316 KB |
Output is correct |
68 |
Correct |
1429 ms |
69436 KB |
Output is correct |
69 |
Correct |
1096 ms |
69436 KB |
Output is correct |
70 |
Correct |
1551 ms |
69344 KB |
Output is correct |
71 |
Correct |
1573 ms |
69484 KB |
Output is correct |
72 |
Correct |
1607 ms |
69348 KB |
Output is correct |
73 |
Correct |
1375 ms |
69408 KB |
Output is correct |
74 |
Correct |
1384 ms |
69356 KB |
Output is correct |
75 |
Correct |
1385 ms |
69384 KB |
Output is correct |
76 |
Correct |
1153 ms |
69404 KB |
Output is correct |
77 |
Correct |
1148 ms |
69352 KB |
Output is correct |
78 |
Correct |
1137 ms |
69376 KB |
Output is correct |
79 |
Correct |
890 ms |
69380 KB |
Output is correct |
80 |
Correct |
897 ms |
69388 KB |
Output is correct |
81 |
Correct |
879 ms |
69444 KB |
Output is correct |
82 |
Correct |
874 ms |
69316 KB |
Output is correct |
83 |
Correct |
890 ms |
69400 KB |
Output is correct |
84 |
Correct |
876 ms |
69364 KB |
Output is correct |
85 |
Correct |
2196 ms |
136924 KB |
Output is correct |
86 |
Correct |
236 ms |
21284 KB |
Output is correct |
87 |
Correct |
216 ms |
21204 KB |
Output is correct |
88 |
Correct |
2433 ms |
137012 KB |
Output is correct |
89 |
Correct |
2115 ms |
136888 KB |
Output is correct |
90 |
Correct |
2384 ms |
136752 KB |
Output is correct |
91 |
Correct |
1444 ms |
69236 KB |
Output is correct |
92 |
Correct |
1445 ms |
69200 KB |
Output is correct |
93 |
Correct |
1902 ms |
69288 KB |
Output is correct |
94 |
Correct |
1885 ms |
136344 KB |
Output is correct |
95 |
Correct |
1827 ms |
136532 KB |
Output is correct |
96 |
Correct |
2087 ms |
136296 KB |
Output is correct |
97 |
Correct |
1981 ms |
136968 KB |
Output is correct |
98 |
Correct |
2084 ms |
136768 KB |
Output is correct |
99 |
Correct |
2165 ms |
136824 KB |
Output is correct |
100 |
Correct |
2170 ms |
136716 KB |
Output is correct |
101 |
Correct |
2223 ms |
136864 KB |
Output is correct |
102 |
Correct |
2182 ms |
136932 KB |
Output is correct |
103 |
Correct |
2201 ms |
136356 KB |
Output is correct |
104 |
Correct |
2214 ms |
136392 KB |
Output is correct |
105 |
Correct |
1654 ms |
136384 KB |
Output is correct |
106 |
Correct |
1394 ms |
136152 KB |
Output is correct |
107 |
Correct |
1600 ms |
136388 KB |
Output is correct |
108 |
Correct |
2180 ms |
136584 KB |
Output is correct |
109 |
Correct |
2151 ms |
136184 KB |
Output is correct |