Submission #1187414

#	Time	Username	Problem	Language	Result	Execution time	Memory
1187414		kl0989e	Inside information (BOI21_servers)	C++17	53 / 100	576 ms	85888 KiB

servers

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

#define ll long long
#define fi first
#define se second
#define pb push_back
#define vi vector<int>
#define vl vector<ll>
#define pi pair<int, int>
#define pl pair<ll,ll>
#define all(x) (x).begin(),(x).end()

const int maxn=120000+10;
const int logg=ceil(log2(maxn));

vector<vector<pi>> graph(maxn);
vi depth(maxn,-1);
vi tin(maxn,-1);
vi tout(maxn,-1);
int timer=0;
vector<vi> up(maxn,vi(logg+1,0));
vector<vi> mx(maxn,vi(logg+1,0)),mn(maxn,vi(logg+1,0));
vector<vi> okup(maxn,vi(logg+1,1)),okdown(maxn,vi(logg+1,1));

void dfs(int cur, int prev, int val) {
	depth[cur]=depth[prev]+1;
	tin[cur]=timer++;
	up[cur][0]=prev;
	mx[cur][0]=val;
	mn[cur][0]=val;
	for (int i=1; i<=logg; i++) {
		up[cur][i]=up[up[cur][i-1]][i-1];
		mx[cur][i]=max(mx[cur][i-1],mx[up[cur][i-1]][i-1]);
		mn[cur][i]=min(mn[cur][i-1],mn[up[cur][i-1]][i-1]);
		okup[cur][i]=okup[cur][i-1]&okup[up[cur][i-1]][i-1]&(mx[cur][i-1]<mn[up[cur][i-1]][i-1]);
		okdown[cur][i]=okdown[cur][i-1]&okdown[up[cur][i-1]][i-1]&(mn[cur][i-1]>mx[up[cur][i-1]][i-1]);
	}
	for (auto [to,w]:graph[cur]) {
		if (to==prev) {
			continue;
		}
		dfs(to,cur,w);
	}
	tout[cur]=timer;
}

bool is_anchestor(int a, int b) {
	return (tin[a]<=tin[b] && tout[a]>=tout[b]);
}

int lca(int a, int b) {
	if (is_anchestor(a,b)) {
		return a;
	}
	if (is_anchestor(b,a)) {
		return b;
	}
	for (int i=logg; i>=0; i--) {
		if (!is_anchestor(up[a][i],b)) {
			a=up[a][i];
		}
	}
	return up[a][0];
}

int check_up(int a, int b) {
	if (a==b) {
		return -1;
	}
	int mxx=-1;
	for (int i=logg; i>=0; i--) {
		if (!is_anchestor(up[a][i],b)) {
			if (!okup[a][i]) {
				return -2;
			}
			if (mxx>=mn[a][i]) {
				return -2;
			}
			mxx=mx[a][i];
			a=up[a][i];
		}
	}
	if (!okup[a][0]) {
		return -2;
	}
	if (mxx>=mn[a][0]) {
		return -2;
	}
	mxx=mx[a][0];
	return mxx;
}

int check_down(int a, int b) {
	if (a==b) {
		return 1e9;
	}
	int mnn=1e9;
	for (int i=logg; i>=0; i--) {
		if (!is_anchestor(up[a][i],b)) {
			if (!okdown[a][i]) {
				return -2;
			}
			if (mnn<=mx[a][i]) {
				return -2;
			}
			mnn=mn[a][i];
			a=up[a][i];
		}
	}
	if (!okup[a][0]) {
		return -2;
	}
	if (mnn<=mx[a][0]) {
		return -2;
	}
	mnn=mn[a][0];
	return mnn;
}

bool has(int a, int b, int t) {
	int c=lca(a,b);
	int mxx=check_up(b,c);
	int mnn=check_down(a,c);
	if (mxx!=-2 && mnn!=-2 && mxx<mnn && ((a!=c && mx[a][0]<t) || (a==c && mxx<t))) {
		return 1;
	}
	return 0;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
	int n,q;
	cin >> n >> q;
	char c;
	int a,b;
	int t=0;
	vector<vi> que;
	for (int i=0; i<n-1+q; i++) {
		cin >> c;
		if (c=='S') {
			cin >> a >> b;
			graph[--a].pb({--b,t});
			graph[b].pb({a,t++});
		}
		else if (c=='Q') {
			cin >> a >> b;
			que.pb({a-1,b-1,t});
		}
		else {
			cin >> a;
			que.pb({a-1,t});
		}
	}
	dfs(0,0,0);
	for (int i=0; i<q; i++) {
		if (que[i].size()==2) {
			int tl=que[i][0],tr=que[i][0];
			int l=0,r=que[i][0];
			while (l<=r) {
				int m=l+(r-l)/2;
				if (has(m,que[i][0],que[i][1])) {
					tl=m;
					r=m-1;
				}
				else {
					l=m+1;
				}
			}
			l=que[i][0];
			r=n-1;
			while (l<=r) {
				int m=l+(r-l)/2;
				if (has(m,que[i][0],que[i][1])) {
					tr=m;
					l=m+1;
				}
				else {
					r=m-1;
				}
			}
			cout << tr-tl+1 << '\n';
		}
		else {
			if (has(que[i][0],que[i][1],que[i][2])) {
				cout << "yes\n";
			}
			else {
				cout << "no\n";
			}
		}
	}
	return 0;
}

• Subtask 1-1: 2 / 2
• Subtask 1-2: 0 / 3
• Subtask 2-1: 2 / 2
• Subtask 2-2: 0 / 3
• Subtask 3-1: 5 / 5
• Subtask 3-2: 5 / 5
• Subtask 4-1: 10 / 10
• Subtask 4-2: 0 / 10
• Subtask 5-1: 12 / 12
• Subtask 5-2: 0 / 13
• Subtask 6-1: 17 / 17
• Subtask 6-2: 0 / 18