oj.uz

Submission #653166

# Submission time Handle Problem Language Result Execution time Memory
653166 2022-10-25T23:06:32 Z inksamurai Inside information (BOI21_servers) C++17
100 / 100
 534 ms 65092 KB 
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define rng(i,c,n) for(int i=c;i<n;i++)
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define vec(...) vector<__VA_ARGS__>
#define _3D2ZDxo ios::sync_with_stdio(0),cin.tie(0)
typedef long long ll;
using pii=pair<int,int>;
using vi=vector<int>;
void print(){cout<<'\n';}
template<class h,class...t>
void print(const h&v,const t&...u){cout<<v<<' ',print(u...);}

#define all(a) a.begin(),a.end()

template<class E>
struct treelca{
	int n;
	int timer=0;
	vec(vec(E)) adj;
	vi tin,tout,tour,tourid;
	vi segtree;
	vi depth;
	treelca(int m,int root,vec(vec(E)) neadj){
		init(m,root,neadj);
	}
	void init(int m,int root,vec(vec(E)) neadj){
		n=m;
		tin.clear();
		tout.clear();
		tour.clear();
		tourid.clear();
		depth.clear();
		tin.resize(n,0);
		tout.resize(n,0);
		tourid.resize(n,0);
		depth.resize(n,0);
		adj=neadj;
		dfs(root,-1);
		segtree.resize(4*sz(tour));
		build(1,0,sz(tour)-1);
	}
	void dfs(int v,int par){
		tour.pb(v);
		tourid[v]=sz(tour)-1;
		tin[v]=timer++;
		for(auto e:adj[v]){
			int u=e.to;
			if(u==par) continue;
			depth[u]=depth[v]+1;
			dfs(u,v);
			tour.pb(v);
		}
		tout[v]=timer++;
	}
	void build(int node,int l,int r){
		if(l==r){
			segtree[node]=tour[l];
		}else{
			int m=(l+r)>>1;
			build(node*2,l,m);
			build(node*2+1,m+1,r);
			segtree[node]=(tin[segtree[node*2]]<tin[segtree[node*2+1]]?segtree[node*2]:segtree[node*2+1]);
		}
	}
	int query(int node,int l,int r,int _l,int _r){
		if(l>_r or r<_l) return -1;
		if(l>=_l and r<=_r) return segtree[node];
		int m=(l+r)>>1;
		int vl=query(node*2,l,m,_l,_r);
		int vr=query(node*2+1,m+1,r,_l,_r);
		if(min(vl,vr)==-1) return max(vl,vr);
		return (tin[vl]<tin[vr]?vl:vr);
	}
	int ancestor(int from,int to){
		int tinfrom=tin[from],tinto=tin[to];
		if(tinfrom>tinto) swap(tinfrom,tinto);
		return query(1,0,sz(tour)-1,tinfrom,tinto);
	}
	int dist(int u,int v){
		return depth[u]+depth[v]-depth[ancestor(u,v)]*2;
	}
};

struct fenwick{
	int n;
	vector <int> bit;
	fenwick(int m){
		init(m);
	}
	void init(int m){
		n=m;
		bit.resize(n,0);
	}
	int get(int i){
		int s=0;
		while(i){
			s+=bit[i];
			i-=i&-i;
		}
		return s;
	}
	void add(int i,int x){
		while(i<=n){
			bit[i]+=x;
			i+=i&-i;
		}
	}
};

struct E{
	int to,w;
	E(int _to=0,int _w=0):
	to(_to),w(_w){}
	bool operator<(const E&a)const{
		return pii(w,to)<pii(a.w,to);
	}
};

const int inf=1e9;

signed main(){
_3D2ZDxo;
	int n,q;
	cin>>n>>q;
	q+=n-1;
	vec(vec(E)) adj(n);
	vec(vi) qry1(n);
	vec(vec(pii)) qry(n);
	vi pns(q,-1);
	vi reb(q,0);
	rep(i,q){
		char ch;
		cin>>ch;
		if(ch=='S'){
			int u,v;
			cin>>u>>v;
			u-=1,v-=1;
			adj[u].pb(E(v,i));
			adj[v].pb(E(u,i));
		}else if(ch=='Q'){
			int u,v;
			cin>>u>>v;
			u-=1,v-=1;
			reb[i]=1;
			qry[v].pb({u,i});
		}else{
			int v;
			cin>>v;
			v-=1;
			pns[i]=0;
			qry1[v].pb(i);
		}
	}
	// answering first query
	{
		vi leb(n); // last node where increasing seq broke
		vi bel(n); // last node where decreasing seq broke
		vi par(n);
		vi par_wit(n);
		auto dfs=[&](auto self,int v,int _lst)->void{
			for(auto [u,w]:adj[v]){
				if(u==par[v]) continue;
				if(_lst>=w){
					leb[u]=v;
				}else{
					leb[u]=leb[v];
				}
				if(_lst<=w){
					bel[u]=v;
				}else{
					bel[u]=bel[v];
				}
				par[u]=v;
				par_wit[u]=w;
				self(self,u,w);
			}
		};
		dfs(dfs,0,0);
		vec(vi) afup(20,vi(n)); // affine up
		afup[0]=par;
		rng(j,1,20){
			rep(v,n){
				int up=afup[j-1][v];
				afup[j][v]=afup[j-1][up];
			}
		}
		treelca<E> lca(n,0,adj);
		auto move_down=[&](int v,int up)->int{
			int dist=lca.dist(v,up)-1;
			per(j,20){
				if(dist>>j&1){
					v=afup[j][v];
				}
			}
			return v;
		};
		rep(v,n){
			for(auto p:qry[v]){
				int u=p.fi;
				int j=p.se;
				bool pok=0;
				if(u==v){
					pok=1;
				}else{
					int up=lca.ancestor(u,v);
					if(up==v){
						if(lca.depth[leb[u]]<=lca.depth[up]){
							pok=par_wit[u]<=j;
						}
					}else if(up==u){
						if(lca.depth[bel[v]]<=lca.depth[up]){
							pok=par_wit[move_down(v,u)]<=j;
						}
					}else{
						if(lca.depth[leb[u]]<=lca.depth[up] and lca.depth[bel[v]]<=lca.depth[up]){
							int lov=move_down(v,up);
							int lou=move_down(u,up);
							pok=par_wit[lov]<=par_wit[lou] and par_wit[u]<=j;
						}
					}
				}
				pns[j]=pok;
			}
		}
	}
	// answering second query
	{
		rep(v,n){
			sort(all(adj[v]));
		}
		int num=0;
		vi usd(n);
		vi chs(n);
		auto refill=[&](auto self,int v,int par)->void{
			num+=1;
			chs[v]=1;
			for(auto [to,w]:adj[v]){
				if(to==par or usd[to]) continue;
				self(self,to,v);
				chs[v]+=chs[to];
			}
		};
		auto find_centroid=[&](auto self,int v,int par)->int{
			for(auto [to,w]:adj[v]){
				if(to==par or usd[to]) continue;
				if(chs[to]*2>num){
					return self(self,to,v);
				}
			}
			return v;
		};
		fenwick bit(q+1);
		auto ask=[&](auto self,int v,int par,int _lst,int __lst)->void{
			for(auto j:qry1[v]){
				pns[j]+=bit.get(j+1)+(j>=__lst);
				// print(pns[j],j,bit.get(j+1));
			}
			for(auto [to,w]:adj[v]){
				if(to==par or usd[to]) continue;
				if(w>_lst) continue;
				self(self,to,v,w,__lst);
			}
		};
		auto add=[&](auto self,int v,int par,int _lst,int x)->void{
			bit.add(_lst+1,x);
			// print(v,_lst+1);
			for(auto [to,w]:adj[v]){
				if(to==par or usd[to]) continue;
				if(w<_lst) continue;
				self(self,to,v,w,x); 
			}
		};
		auto dfs=[&](auto self,int v,int par)->void{
			num=0;
			refill(refill,v,par);
			int rt=find_centroid(find_centroid,v,par);
			usd[rt]=1;
			per(i,sz(adj[rt])){
				auto [to,w]=adj[rt][i];
				if(to==par or usd[to]) continue;
				ask(ask,to,rt,w,w);
				add(add,to,rt,w,1);
			}
			for(auto j:qry1[rt]){
				pns[j]+=bit.get(j+1);
			}
			per(i,sz(adj[rt])){
				auto [to,w]=adj[rt][i];
				if(to==par or usd[to]) continue;
				add(add,to,rt,w,-1);	
			}
			rep(i,sz(adj[rt])){
				auto [to,w]=adj[rt][i];
				if(to==par or usd[to]) continue;
				self(self,to,rt);
			}
		};
		dfs(dfs,0,-1);
	}
	rep(i,q){
		if(pns[i]==-1) continue;
		if(reb[i]){
			cout<<(pns[i]?"yes":"no")<<"\n";
		}else{
			cout<<pns[i]+1<<"\n";
		}
	}
}

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 35 ms 3532 KB Output is correct
2 Correct 70 ms 4912 KB Output is correct
3 Correct 76 ms 5044 KB Output is correct
4 Correct 61 ms 4956 KB Output is correct
5 Correct 63 ms 5100 KB Output is correct
6 Correct 87 ms 5212 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 35 ms 3532 KB Output is correct
2 Correct 70 ms 4912 KB Output is correct
3 Correct 76 ms 5044 KB Output is correct
4 Correct 61 ms 4956 KB Output is correct
5 Correct 63 ms 5100 KB Output is correct
6 Correct 87 ms 5212 KB Output is correct
7 Correct 35 ms 3460 KB Output is correct
8 Correct 58 ms 5472 KB Output is correct
9 Correct 58 ms 5600 KB Output is correct
10 Correct 54 ms 5520 KB Output is correct
11 Correct 51 ms 5648 KB Output is correct
12 Correct 64 ms 5648 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 49 ms 3544 KB Output is correct
2 Correct 305 ms 58308 KB Output is correct
3 Correct 291 ms 58324 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 49 ms 3544 KB Output is correct
2 Correct 305 ms 58308 KB Output is correct
3 Correct 291 ms 58324 KB Output is correct
4 Correct 46 ms 3468 KB Output is correct
5 Correct 309 ms 60624 KB Output is correct
6 Correct 137 ms 57932 KB Output is correct
7 Correct 152 ms 58372 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 3440 KB Output is correct
2 Correct 327 ms 61876 KB Output is correct
3 Correct 296 ms 61772 KB Output is correct
4 Correct 290 ms 61580 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 3440 KB Output is correct
2 Correct 327 ms 61876 KB Output is correct
3 Correct 296 ms 61772 KB Output is correct
4 Correct 290 ms 61580 KB Output is correct
5 Correct 28 ms 3444 KB Output is correct
6 Correct 319 ms 64944 KB Output is correct
7 Correct 327 ms 64880 KB Output is correct
8 Correct 309 ms 64240 KB Output is correct
9 Correct 355 ms 64236 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 3432 KB Output is correct
2 Correct 257 ms 56240 KB Output is correct
3 Correct 300 ms 56348 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 3432 KB Output is correct
2 Correct 257 ms 56240 KB Output is correct
3 Correct 300 ms 56348 KB Output is correct
4 Correct 36 ms 3532 KB Output is correct
5 Correct 315 ms 59328 KB Output is correct
6 Correct 274 ms 59296 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 30 ms 3496 KB Output is correct
2 Correct 296 ms 61724 KB Output is correct
3 Correct 310 ms 61780 KB Output is correct
4 Correct 258 ms 61668 KB Output is correct
5 Correct 31 ms 3420 KB Output is correct
6 Correct 294 ms 56568 KB Output is correct
7 Correct 302 ms 56432 KB Output is correct
8 Correct 340 ms 58856 KB Output is correct
9 Correct 313 ms 58620 KB Output is correct
10 Correct 352 ms 59016 KB Output is correct
11 Correct 392 ms 58748 KB Output is correct

Subtask #10
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 30 ms 3496 KB Output is correct
2 Correct 296 ms 61724 KB Output is correct
3 Correct 310 ms 61780 KB Output is correct
4 Correct 258 ms 61668 KB Output is correct
5 Correct 31 ms 3420 KB Output is correct
6 Correct 294 ms 56568 KB Output is correct
7 Correct 302 ms 56432 KB Output is correct
8 Correct 340 ms 58856 KB Output is correct
9 Correct 313 ms 58620 KB Output is correct
10 Correct 352 ms 59016 KB Output is correct
11 Correct 392 ms 58748 KB Output is correct
12 Correct 28 ms 3592 KB Output is correct
13 Correct 331 ms 64968 KB Output is correct
14 Correct 292 ms 65044 KB Output is correct
15 Correct 285 ms 64316 KB Output is correct
16 Correct 322 ms 64288 KB Output is correct
17 Correct 30 ms 4040 KB Output is correct
18 Correct 300 ms 59376 KB Output is correct
19 Correct 285 ms 59256 KB Output is correct
20 Correct 295 ms 61592 KB Output is correct
21 Correct 341 ms 61556 KB Output is correct
22 Correct 390 ms 60672 KB Output is correct
23 Correct 517 ms 62116 KB Output is correct
24 Correct 464 ms 61764 KB Output is correct

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 37 ms 3444 KB Output is correct
2 Correct 62 ms 4900 KB Output is correct
3 Correct 76 ms 5156 KB Output is correct
4 Correct 64 ms 5008 KB Output is correct
5 Correct 61 ms 5180 KB Output is correct
6 Correct 99 ms 5220 KB Output is correct
7 Correct 49 ms 3532 KB Output is correct
8 Correct 294 ms 58752 KB Output is correct
9 Correct 332 ms 58704 KB Output is correct
10 Correct 28 ms 3824 KB Output is correct
11 Correct 340 ms 62140 KB Output is correct
12 Correct 300 ms 62240 KB Output is correct
13 Correct 273 ms 62044 KB Output is correct
14 Correct 31 ms 3908 KB Output is correct
15 Correct 257 ms 56648 KB Output is correct
16 Correct 288 ms 56424 KB Output is correct
17 Correct 318 ms 58848 KB Output is correct
18 Correct 340 ms 58628 KB Output is correct
19 Correct 392 ms 59108 KB Output is correct
20 Correct 377 ms 58608 KB Output is correct
21 Correct 304 ms 59176 KB Output is correct
22 Correct 315 ms 59168 KB Output is correct
23 Correct 334 ms 59672 KB Output is correct
24 Correct 297 ms 59680 KB Output is correct
25 Correct 392 ms 59312 KB Output is correct
26 Correct 305 ms 56560 KB Output is correct
27 Correct 291 ms 56400 KB Output is correct

Subtask #12
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 37 ms 3444 KB Output is correct
2 Correct 62 ms 4900 KB Output is correct
3 Correct 76 ms 5156 KB Output is correct
4 Correct 64 ms 5008 KB Output is correct
5 Correct 61 ms 5180 KB Output is correct
6 Correct 99 ms 5220 KB Output is correct
7 Correct 49 ms 3532 KB Output is correct
8 Correct 294 ms 58752 KB Output is correct
9 Correct 332 ms 58704 KB Output is correct
10 Correct 28 ms 3824 KB Output is correct
11 Correct 340 ms 62140 KB Output is correct
12 Correct 300 ms 62240 KB Output is correct
13 Correct 273 ms 62044 KB Output is correct
14 Correct 31 ms 3908 KB Output is correct
15 Correct 257 ms 56648 KB Output is correct
16 Correct 288 ms 56424 KB Output is correct
17 Correct 318 ms 58848 KB Output is correct
18 Correct 340 ms 58628 KB Output is correct
19 Correct 392 ms 59108 KB Output is correct
20 Correct 377 ms 58608 KB Output is correct
21 Correct 304 ms 59176 KB Output is correct
22 Correct 315 ms 59168 KB Output is correct
23 Correct 334 ms 59672 KB Output is correct
24 Correct 297 ms 59680 KB Output is correct
25 Correct 392 ms 59312 KB Output is correct
26 Correct 305 ms 56560 KB Output is correct
27 Correct 291 ms 56400 KB Output is correct
28 Correct 54 ms 3596 KB Output is correct
29 Correct 54 ms 5420 KB Output is correct
30 Correct 61 ms 5612 KB Output is correct
31 Correct 71 ms 5516 KB Output is correct
32 Correct 54 ms 5652 KB Output is correct
33 Correct 61 ms 5568 KB Output is correct
34 Correct 45 ms 4088 KB Output is correct
35 Correct 267 ms 60604 KB Output is correct
36 Correct 143 ms 57924 KB Output is correct
37 Correct 163 ms 58264 KB Output is correct
38 Correct 39 ms 4100 KB Output is correct
39 Correct 338 ms 65092 KB Output is correct
40 Correct 352 ms 64880 KB Output is correct
41 Correct 295 ms 64220 KB Output is correct
42 Correct 333 ms 64280 KB Output is correct
43 Correct 37 ms 4140 KB Output is correct
44 Correct 271 ms 59420 KB Output is correct
45 Correct 302 ms 59292 KB Output is correct
46 Correct 286 ms 61612 KB Output is correct
47 Correct 312 ms 61492 KB Output is correct
48 Correct 400 ms 60656 KB Output is correct
49 Correct 534 ms 62132 KB Output is correct
50 Correct 502 ms 61720 KB Output is correct
51 Correct 162 ms 59744 KB Output is correct
52 Correct 139 ms 59064 KB Output is correct
53 Correct 187 ms 58708 KB Output is correct
54 Correct 148 ms 59156 KB Output is correct
55 Correct 151 ms 59320 KB Output is correct
56 Correct 276 ms 61244 KB Output is correct
57 Correct 314 ms 59352 KB Output is correct
58 Correct 390 ms 59716 KB Output is correct
59 Correct 289 ms 59260 KB Output is correct