제출 #1181888

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1181888		WH8	Inside information (BOI21_servers)	C++20	5 / 100	290 ms	77440 KiB

servers

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
using namespace std;
using namespace __gnu_pbds;
#define g0(x) get<0>(x)
#define g1(x) get<1>(x)
#define g2(x) get<2>(x)
#define mt make_tuple
#define pb push_back
#define int long long 
#define f first
#define s second
#define pll pair<long long, long long>
const int maxn=120005;
int par[maxn],sub[maxn],m[maxn],twok[maxn][21],depth[maxn];
vector<int> lvl(maxn,-1);
int n,k;
vector<vector<pair<int,int>>> al(maxn),cnt(maxn);
vector<vector<int>> alcent(maxn);
vector<vector<tuple<int,int,int>>> incf(maxn), decf(maxn);

int kpar(int x, int k){ // this is built on the centroid tree 
	for(int i=0;i<21;i++)if ((1 << i) & k) x = twok[x][i];
	return x;
}
int lca(int a, int b){ // this is built on the centroid tree 
	if (depth[a] < depth[b]) swap(a, b);
	int c;
	a = kpar(a, depth[a] - depth[b]);
	if (a == b) {
		c = a;
	}
	else {
		for (int i = 20; i >= 0; i--){
			if (twok[a][i] != twok[b][i]){
				a = twok[a][i], b=twok[b][i];
			}
		}
		c = twok[a][0];
	}
	return c;
}
int dfs_size(int u, int p, int l) { // to find subtree size in original graph
	sub[u] = 1; // Subtree size is 1
	for (auto [v,w] : al[u]) {
		if (lvl[v] != -1){
			//printf("already added, skipping\n");
			continue; // Already added to centroid tree
		}
		if (v == p) continue;
		sub[u] += dfs_size(v, u, l); // Increase size of subtree
	}
	return sub[u];
}
int get_centroid(int u, int p, int n) { // to find centroid (after dfs_size)
	for (auto [v,w] : al[u]) {
		if (lvl[v] != -1) continue; // Already added to centroid tree
		if (v != p && sub[v] > n / 2) {
			return get_centroid(v, u, n); // DFS to that node
		}
	}
	return u; // No child has size more than n/2, hence you are the centroid
}

// Building from node u, with a parent p and level l
int build(int u, int p, int l) {
	int n = dfs_size(u, p, l); // Find the size of each subtree
	int cent = get_centroid(u, p, n); // Find the centroid
	if (p == -1) p = -1; // Parent of root is -1 / can also set to yourself = cent
	//debug(cent); debug(p);
	par[cent] = p; // Set the parent of centroid to the previous centroid
	if(p!=-1){
		alcent[cent].pb(p);
		alcent[p].pb(cent);
	}
	lvl[cent] = l;
	for (auto [v,w] : al[cent]) {
		if (lvl[v] != -1) continue;
		// If we have already added to centroid then we ignore
		build(v, cent, l + 1); // Recursively build each subtree
	}
	return cent;
}

//To construct the centroid tree, call build(root, -1, 0);

void dfs_depth(int x, int p){
	for (auto [it,w] : al[x]){
		if (it == p) continue;
		depth[it] = depth[x] + 1;
		twok[it][0] = x;
		dfs_depth(it, x);
	}
}

void dfs_incf(int x, int p, int prv, int st, int ori){
	for(auto [u,t]:al[x]){
		if(lvl[u]<=lvl[ori] or u==p)continue; // we only look at nodes in the centroid subtree of ori
		if(t <= prv) continue; // inc 
		int go=st;
		if(st==-1)go=t;
		incf[ori].push_back({u,go,t});
		dfs_incf(u, x, t, go, ori);
	}
}

void dfs_decf(int x, int p, int prv, int st, int ori){
	for(auto [u,t]:al[x]){
		if(lvl[u]<=lvl[ori] or u==p)continue; // we only look at nodes in the centroid subtree of ori
		if(t >= prv) continue; // dec.
		int go=st;
		if(st==-1)go=t; 
		decf[ori].push_back({u,go,t});
		dfs_decf(u, x, t,go, ori);
	}
}

void dfs_cnt(int x, int p){
	for(auto u:alcent[x]){
		if(u==p)continue; // we only look at nodes in the centroid subtree of ori
		dfs_cnt(u,x);
		for(auto it:cnt[u]){
			cnt[x].pb(it);
		}
	}
}

signed main(){
	vector<tuple<int,int,int>> query;
	cin>>n>>k;
	vector<int> type(n+k-1,-1), ans(n+k-1,0);
	for(int i=0;i<n+k-1;i++){
		char ins;int a,b;cin>>ins>>a;
		if(ins=='S'){
			cin>>b;
			type[i]=0;
			al[a].pb({b,i});
			al[b].pb({a,i});
		}
		else if(ins=='Q'){
			type[i]=1;
			cin>>b;
			query.pb({a,b,i});
		}
		else {
			type[i]=2;
			cnt[a].pb({a,i});
		}
	}
	int cent=build(1,-1,0); // this is the root of the centroid tree.
	dfs_depth(cent,-1);
	for (int i=1;i<21;i++){
		for(int j=1;j<=n;j++){
			twok[j][i] = twok[twok[j][i-1]][i-1];
		}
	}
	
	//~ for(int i=1;i<=n;i++){
		//~ cout<<"node "<<i<<endl;
		//~ for(auto it:alcent[i])cout<<it<<", ";
		//~ cout<<endl;
		//~ printf("node %lld has level %lld in centroid has parent %lld\n",i,lvl[i],par[i]);
	//~ }
	//~ return 0;
	for(int i=1;i<=n;i++){
		dfs_incf(i,-1,-1,-1, i);
		dfs_decf(i,-1,1e15,-1,i);
		incf[i].pb({i,1e15,-1});
		decf[i].pb({i,-1,-2});
	}
	dfs_cnt(cent,-1);
	//~ for(int i=1;i<=n;i++){
		//~ printf("node %lld ------------------------\n",i);
		//~ cout<<"incf: ";
		//~ for(auto [u,st,t]:incf[i]){
			//~ printf("u %lld, st %lld, t %lld\n",u,st,t);
		//~ }
		//~ cout<<"\n";
		//~ cout<<"decf: ";
		//~ for(auto [u,st,t]:decf[i]){
			//~ printf("u %lld, st %lld, t %lld\n",u,st,t);
		//~ }
		//~ cout<<"\n";
		//~ cout<<"cnt: ";
		//~ for(auto [a,b]:cnt[i]){
			//~ printf("from a %lld at time %lld\n",a,b);
		//~ }
		//~ cout<<"---------------------\n";
	//~ }
	for(int i=1;i<=n;i++){
		sort(decf[i].begin(),decf[i].end());
		sort(incf[i].begin(),incf[i].end(),[&](auto a, auto b){
			return get<1>(a)<get<1>(b);
		});
		vector<tuple<int,int,int>> abs;
		int ptr=incf[i].size()-1;
		for(auto [from, time] : cnt[i]){
			//~ printf("i=%lld, checking validity of from %lld, time %lld\n",i,from,time);
			auto it=lower_bound(decf[i].begin(),decf[i].end(),mt(from,LLONG_MIN,LLONG_MIN));
			//~ if(it!=decf[i].end()){
				//~ printf("from is actually %lld\n", get<0>(*it));
			//~ }
			if(it==decf[i].end() 
			or get<0>(*it)!=from // path is not increasing to parent even.
			or get<1>(*it)>time// path cannot even be taken.
			)continue; 
			abs.push_back({get<1>(*it),get<2>(*it),time});
			//~ printf("added\n");
		}
		sort(abs.begin(),abs.end(),greater<tuple<int,int,int>>());
		ordered_set oset;
		for(auto [a,b, time] : abs){
			
			while(ptr>=0 and get<1>(incf[i][ptr])>a){
				oset.insert(get<2>(incf[i][ptr]));
				ptr--;
			}
			int cont=oset.order_of_key(time);
			ans[time]+=cont;
			//~ printf("anc %lld, a %lld, b %lld, time %lld, cont %lld\n",i,a,b,time,cont);
		}
	}
	for(int i=1;i<=n;i++){
		sort(incf[i].begin(),incf[i].end());
	}
	for(auto [a,b,time]:query){
		// b is in dec from anc, a is in inc from anc
		if(a==b){
			ans[time]=1;
		}
		else{
			int anc=lca(a,b);
			auto it1=lower_bound(decf[anc].begin(),decf[anc].end(),mt(b,LLONG_MIN,LLONG_MIN));
			auto it2=lower_bound(incf[anc].begin(),incf[anc].end(),mt(a,LLONG_MIN,LLONG_MIN));
			if(it1==decf[anc].end() or it2==incf[anc].end() 
			or get<0>(*it1)!=b or get<0>(*it2)!=a 
			or get<1>(*it2)<get<1>(*it1) or get<2>(*it2)>time
			or get<1>(*it1)>time
			){
				ans[time]=0;
			}
			else {
				ans[time]=1;
				//~ printf("a %lld, b %lld, time %lld, endtime %lld\n",a,b,time,get<2>(*it2));
			}
		}
	}
	for(int i=0;i<n+k-1;i++){
		if(type[i]==0)continue;
		else if(type[i]==1){
			if(ans[i])cout<<"yes\n";
			else cout<<"no\n";
		}
		else{
			cout<<ans[i]<<"\n";
		}
	}
	
}

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