Submission #963973

#	Time	Username	Problem	Language	Result	Execution time	Memory
963973		pcc	Inside information (BOI21_servers)	C++17	5 / 100	3531 ms	83036 KiB

servers

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>
#define tiii tuple<int,int,int>

const int mxn = 2e5+10;
vector<pii> tree[mxn];
int N,Q;
vector<tiii> req,req2;
int ans[mxn];
int isask[mxn];

namespace HLD{
	int sz[mxn],idx[mxn],link_top[mxn],par[mxn],bs[mxn],dep[mxn],cnt,val[mxn];
	struct node{
		bool inc,dec;
		int mx,mn;
		node(){
			inc = dec = 1;
			mx = mn = 0;
		}
	};
	node pull(node a,node b){
		node re;
		if(a.mx == -1)return b;
		if(b.mx == -1)return a;
		re.inc = a.inc&&b.inc&&(a.mx<=b.mn);
		re.dec = a.dec&&b.dec&&(a.mn>=b.mx);
		re.mx = max(a.mx,b.mx);
		re.mn = min(a.mn,b.mn);
		return re;
	}

	struct SEG{
#define mid ((l+r)>>1)
#define ls now*2+1
#define rs now*2+2
		node seg[mxn*4];
		void build(int now,int l,int r){
			if(l == r){
				seg[now].mx = seg[now].mn = val[l];
				seg[now].dec = seg[now].inc = 1;
				return;
			}
			build(ls,l,mid);
			build(rs,mid+1,r);
			seg[now] = pull(seg[ls],seg[rs]);
			return;
		}
		node getval(int now,int l,int r,int s,int e){
			assert(s<=e);
			if(l>=s&&e>=r)return seg[now];
			if(mid>=e)return getval(ls,l,mid,s,e);
			else if(mid<s)return getval(rs,mid+1,r,s,e);
			else return pull(getval(ls,l,mid,s,e),getval(rs,mid+1,r,s,e));
		}
#undef ls
#undef rs
#undef mid
	};

	SEG seg;
	void dfs(int now){
		sz[now] = 1;
		for(auto nxt:tree[now]){
			if(nxt.fs == par[now])continue;
			par[nxt.fs] = now;
			dep[nxt.fs] = dep[now]+1;
			dfs(nxt.fs);
			sz[now] += sz[nxt.fs];
			if(!bs[now]||sz[bs[now]]<=sz[nxt.fs])bs[now] = nxt.fs;
		}
		return;
	}
	void dfs2(int now,int top){
		link_top[now] = top;
		idx[now] = ++cnt;
		if(bs[now])dfs2(bs[now],top);
		for(auto nxt:tree[now]){
			if(nxt.fs == par[now])continue;
			if(nxt.fs != bs[now])dfs2(nxt.fs,nxt.fs);
			val[idx[nxt.fs]] = nxt.sc;
		}
		return;
	}
	void GO(){
		dfs(1);
		dfs2(1,1);
		seg.build(0,1,N);
	}
	node LCA(int a,int b){
		int ta = link_top[a],tb = link_top[b];
		node lv,rv;
		lv.mx = lv.mn = rv.mx = rv.mn = -1;
		while(ta != tb){
			if(dep[ta]>dep[tb]){
				lv = pull(seg.getval(0,1,N,idx[ta],idx[a]),lv);
				a = par[ta];
				ta = link_top[a];
			}
			else{
				rv = pull(seg.getval(0,1,N,idx[tb],idx[b]),rv);
				b = par[tb];
				tb = link_top[b];
			}
		}
		if(dep[a]>dep[b]){
			lv = pull(seg.getval(0,1,N,idx[b]+1,idx[a]),lv);
		}
		else if(dep[a]<dep[b]){
			rv = pull(seg.getval(0,1,N,idx[a]+1,idx[b]),rv);
		}
		//cout<<lv.mx<<' '<<lv.mn<<' '<<lv.dec<<' '<<lv.inc<<';'<<rv.mx<<' '<<rv.mn<<' '<<rv.dec<<' '<<rv.inc<<endl;
		swap(rv.inc,rv.dec);
		return pull(rv,lv);
	}
}

namespace CD{
	struct BIT{
		int bit[mxn];
		void modify(int p,int v){
			for(;p<mxn;p+=p&-p)bit[p] += v;
			return;
		}
		int getval(int s,int e){
			int re = 0;
			for(;e>0;e-= e&-e)re += bit[e];
			s--;
			for(;s>0;s-= s&-s)re -= bit[s];
			return re;
		}
		BIT(){
			memset(bit,0,sizeof(bit));
		}
	};
	BIT bit;
	int sz[mxn];
	bitset<mxn> del;
	vector<int> ask[mxn];

	int szdfs(int now,int par){
		sz[now] = 1;
		for(auto [nxt,w]:tree[now]){
			if(del[nxt]||nxt == par)continue;
			sz[now] += szdfs(nxt,now);
		}
		return sz[now];
	}
	int find_centroid(int now,int par,int tar){
		for(auto [nxt,w]:tree[now]){
			if(del[nxt]||nxt == par)continue;
			if(sz[nxt]>tar)return find_centroid(nxt,now,tar);
		}
		return now;
	}

	void dfs1(int now,int par,int mx,int mn){
		for(auto &i:ask[now]){
			if(i<mx)continue;
			ans[i] += bit.getval(mx,i);
		}
		for(auto [nxt,w]:tree[now]){
			if(nxt == par||del[nxt]||mn<w)continue;
			dfs1(nxt,now,mx,w);
		}
		return;
	}

	void dfs2(int now,int par,int mx,int mn){
		bit.modify(mx,1);
		for(auto [nxt,w]:tree[now]){
			if(nxt == par||del[nxt]||mx>w)continue;
			dfs2(nxt,now,w,mn);
		}
		return;
	}

	void dfs3(int now,int par){
		for(auto [nxt,w]:tree[now]){
			if(nxt == par||del[nxt])continue;
			bit.modify(w,-bit.getval(w,w));
			dfs3(nxt,now);
		}
		return;
	}

	void cendfs(int now){
		now = find_centroid(now,now,(szdfs(now,now)-1)>>1);
		for(auto [nxt,w]:tree[now]){
			if(del[nxt])continue;
			bit.modify(w,1);
			dfs1(nxt,now,w,w);
			dfs2(nxt,now,w,w);
			bit.modify(w,-1);
		}
		for(auto &i:ask[now]){
			ans[i] += bit.getval(0,i);
		}
		del[now] = true;
		dfs3(now,now);
		for(auto [nxt,w]:tree[now]){
			if(!del[nxt])cendfs(nxt);
		}
		return;
	}

	void GO(){
		for(auto &[id,pt,__]:req2){
			ask[pt].push_back(id);
		}
		for(int i = 1;i<=N;i++)sort(tree[i].begin(),tree[i].end(),[](pii a,pii b){return a.sc>b.sc;});
		cendfs(1);
	}
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>N>>Q;
	for(int i = 1;i<N+Q;i++){
		char c;
		cin>>c;
		if(c == 'S'){
			int a,b;
			cin>>a>>b;
			tree[a].push_back(pii(b,i));
			tree[b].push_back(pii(a,i));
		}
		else if(c == 'Q'){
			isask[i] = 1;
			int a,b;
			cin>>a>>b;
			req.push_back(tiii(i,a,b));
		}
		else{
			int k;
			cin>>k;
			isask[i] = 2;
			req2.push_back(tiii(i,k,k));
		}
	}
	HLD::GO();
	for(auto &[w,s,e]:req){
		auto re = HLD::LCA(s,e);
		//cout<<w<<' '<<s<<' '<<e<<":"<<re.inc<<' '<<re.dec<<' '<<re.mx<<' '<<re.mn<<endl;
		if(!re.inc||re.mx>w)ans[w] = false;
		else ans[w] = true;
	}
	CD::GO();
	for(int i = 1;i<N+Q;i++){
		if(isask[i] == 1)cout<<(ans[i]?"yes\n":"no\n");
		else if(isask[i] == 2)cout<<ans[i]+1<<'\n';
	}
	return 0;
}

• Subtask 1: 2.5 / 2.5
• Subtask 2: 2.5 / 2.5
• Subtask 3: 0 / 2.5
• Subtask 4: 0 / 2.5
• Subtask 5: 0 / 5
• Subtask 6: 0 / 5
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 12.5
• Subtask 10: 0 / 12.5
• Subtask 11: 0 / 17.5
• Subtask 12: 0 / 17.5