제출 #488860

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
488860		CSQ31	Inside information (BOI21_servers)	C++17	0 / 100	114 ms	57500 KiB

servers

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define sz(a) (int)(a.size())
#define owo ios_base::sync_with_stdio(0);cin.tie(0);
typedef pair<int,int> pii;
const int MAXN = 2e5;
vector<pii>adj[MAXN];
int dep[MAXN],val[MAXN],par[18][MAXN],dd[MAXN],add,n,k;
bool ic[18][MAXN],dc[18][MAXN]; //increaisng path and decreasing path


char c[250000];
int a[250000],d[250000];
void dfs(int v,int u){
	if(v<=n && sz(adj[v])==1)adj[v].pb({++add,0});
	for(int i=1;i<=17;i++)par[i][v] = par[i-1][par[i-1][v]];
	for(pii z:adj[v]){
		int x = z.fi;
		int w = z.se;
		if(x == u)continue;
		val[x] = w;
		dd[v] = x;
		dep[x] = dep[v]+1;
		par[0][x] = v;
		dfs(x,v);
	}
}
void dfs2(int v,int u){
	if(v<=n){
		dc[0][v] = ic[0][v] = 1;
		for(int i=1;i<=17;i++){
			int x = par[i-1][dd[v]];
			int y = par[i-1][v];
			if(val[x] > val[y] && dc[i-1][v])dc[i][v] = 1;
			if(val[x] < val[y] && ic[i-1][v])ic[i][v] = 1;
		}
	}
	for(pii z:adj[v]){
		if(z.fi == u)continue;
		dfs2(z.fi,v);
	}
	
}
int lca(int v,int u){
	if(dep[v] < dep[u])swap(v,u);
	int d = dep[v] - dep[u];
	for(int i=0;i<=17;i++){
		if(d&(1<<i))v = par[i][v];
	}
	if(v==u)return v;
	for(int i=17;i>=0;i--){
		if(par[i][v] != par[i][u]){
			v = par[i][v];
			u = par[i][u];
		}
	}
	return par[0][v];
}
int p[MAXN];
int find(int x){
	if(x==p[x])return x;
	else return p[x] = find(p[x]);
}
bool unite(int a,int b){
	a = find(a);
	b = find(b);
	if(a==b)return 0;
	p[a] = b;
	return 1;
}
int main()
{
	owo
	cin>>n>>k;
	add = n;
	int cnt = 0;
	for(int i=1;i<=n;i++)p[i] = i;
	for(int i=0;i<n+k-1;i++){
		cin>>c[i]>>a[i];
		if(c[i]!='C')cin>>d[i];
		if(c[i] == 'S'){
			adj[a[i]].pb({d[i],++cnt});
			adj[d[i]].pb({a[i],cnt});
		}
	}
	dfs(1,0);
	dfs2(1,0);
	for(int i=0;i<n+k-1;i++){
		if(c[i] == 'S')unite(a[i],d[i]);
		else if(c[i]=='C'){
			cout<<42<<'\n';
			continue;
		}
		else{
			int v = a[i];
			int u = d[i];
			if(find(v) != find(u)){
				cout<<"no"<<'\n';
				continue;
			}
			bool ok =1;
			int last0 = 1e9,last1 = -1e9;
			int m = lca(v,u);
			if(v!=m){
				int x = dd[v];
				int y = v;
				int d = dep[v]-dep[m];
				for(int i=0;i<=17 && d;i++){
					if(d&1){
						//cout<<i<<" "<<y<<" "<<dc[i][y]<<'\n';
						if(!dc[i][y])ok = 0;
						x = par[i][x];
						y = par[i][y];
						//cout<<y<<" "<<x<<" "<<val[y]<<" "<<val[x]<<'\n';
						if(y!=m && val[y] > val[x])ok = 0;
					}
					d/=2;
				}
				last0 = val[x];
			}
			if(u!=m){
				int x = dd[u];
				int y = u;
				int d = dep[u]-dep[m];
				for(int i=0;i<=17 && d;i++){
					if(d&1){
						if(!ic[i][y])ok = 0;
						x = par[i][x];
						y = par[i][y];
						if(y!=m && val[y] < val[x])ok = 0;
					}
					d/=2;
				}
				last1 = val[x];
			}
			//cout<<last0<<" "<<last1<<'\n';
			if(last0 < last1)ok = 0;
			if(ok)cout<<"yes"<<'\n';
			else cout<<"no"<<'\n';
		}
		
	}
}

• 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