Submission #963925

#	Time	Username	Problem	Language	Result	Execution time	Memory
963925		pcc	Inside information (BOI21_servers)	C++17	0 / 100	42 ms	20688 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;

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;
		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 = val[idx[a]];
		rv.mx = rv.mn = val[idx[b]];
		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);
	}
}

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'){
			int a,b;
			cin>>a>>b;
			req.push_back(tiii(i,a,b));
		}
		else{
			exit(0);
		}
	}
	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)cout<<"no\n";
		else cout<<"yes\n";
	}
	return 0;
}

• Subtask 1: 0 / 2.5
• Subtask 2: 0 / 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