제출 #653166

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
653166		inksamurai	Inside information (BOI21_servers)	C++17	100 / 100	534 ms	65092 KiB

servers

#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
• Subtask 2: 2.5 / 2.5
• Subtask 3: 2.5 / 2.5
• Subtask 4: 2.5 / 2.5
• Subtask 5: 5 / 5
• Subtask 6: 5 / 5
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 12.5 / 12.5
• Subtask 10: 12.5 / 12.5
• Subtask 11: 17.5 / 17.5
• Subtask 12: 17.5 / 17.5