Submission #1179895

#	Time	Username	Problem	Language	Result	Execution time	Memory
1179895		mertbbm	Inside information (BOI21_servers)	C++20	0 / 100	29 ms	44280 KiB

servers

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

#define int long long 
#define ld long double
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << "  " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << "  " << j << " " << #i << "  " << q << " " << #p << endl;
#define show4(x,y) for(auto it:y) cout << it << " "; cout << #x << endl;
typedef pair<int,int>pii;
mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());

vector<pii>adj[120005];

bool visited[120005];
int sz[120005];
int out[120005];
int pos[18][120005];
int val[18][120005];
vector<int>storage[120005];
vector<pii>add;
int dep[120005];

void dfs(int index, int par){
	sz[index]=1;
	for(auto it:adj[index]){
		if(it.first==par) continue;
		if(visited[it.first]) continue;
		dfs(it.first,index);
		sz[index]+=sz[it.first];
	}
}

int dfs2(int index, int par, int n){
	for(auto it:adj[index]){
		if(it.first==par) continue;
		if(visited[it.first]) continue;
		if(sz[it.first]>n/2) return dfs2(it.first,index,n);
	}
	return index;
}

void dfs3(int index, int par, int cent, int cur, bool amos, int lvl, int ptr){
	//show2(index,index,amos,amos);
	if(!amos){
		storage[index].push_back(cent);
	}
	else{
		val[lvl][index]=cur;
		add.push_back({cur,ptr});
		//show3(index,index,ptr,ptr,cent,cent);
	}
	pos[lvl][index]=ptr;
	//show3(lvl,lvl,index,index,ptr,ptr);
	for(auto it:adj[index]){
		if(it.first==par) continue;
		if(visited[it.first]) continue;
		if(amos&&it.second<cur) continue;
		if(!amos&&it.second>cur) continue;
		dfs3(it.first,index,cent,it.second,amos,lvl,ptr);
	}
}

int ptr=2;

void build(int index, int lvl){
	dfs(index,-1);
	int hold=sz[index];
	int cent=dfs2(index,-1,hold);
	storage[cent].push_back(cent);
	pos[lvl][cent]=ptr-1;
	//cout << lvl << " " << cent << " " << pos[lvl][cent] << "\n";
	dep[cent]=lvl;
	visited[cent]=true;
	//show2(cent,cent,lvl,lvl);
	for(auto nxt:adj[cent]){
		if(visited[nxt.first]) continue;
		for(auto it:adj[nxt.first]){
			if(visited[it.first]) continue;
			if(it.second>nxt.second){
				//go down
				dfs3(it.first,nxt.first,cent,it.second,1,lvl,ptr);
			}
			else{
				//go up
				dfs3(it.first,nxt.first,cent,it.second,0,lvl,ptr);
			}
		}
		storage[nxt.first].push_back(cent);
		add.push_back({nxt.second,ptr});
		//show3(nxt.second,nxt.second,ptr,ptr,cent,cent);
		out[cent]=ptr;
		pos[lvl][nxt.first]=ptr++;
		val[lvl][nxt.first]=nxt.second;
	}
	
	for(auto nxt:adj[cent]){
		if(visited[nxt.first]) continue;
		build(nxt.first,lvl+1);
	}
	//out[cent]=ptr-1;
	//show(out,cent);
}

bool cmp(const pii &a, const pii &b){
	return a.second < b.second;
}

int fw[250005];

void upd(int x, int y){
	while(x<250005){
		fw[x]+=y;
		x+=x&(-x);
	}
}

int sum(int x){
	int counter=0;
	while(x>0){
		counter+=fw[x];
		x-=x&(-x);
	}
	return counter;
}

int query(int x, int y){
	if(x>y) return 0;
	return sum(y)-sum(x-1);
}

void solve(){
	int n,q;
	cin >> n >> q;
	
	memset(pos,-1,sizeof(pos));
	memset(val,-1,sizeof(val));
	
	char temp;
	int a,b;
	vector<pair<pii,pii>>que;
	for(int x=0;x<n+q-1;x++){
		cin >> temp;
		if(temp=='S'){
			cin >> a >> b;
			adj[a].push_back({b,x});
			adj[b].push_back({a,x});
		}
		else if(temp=='Q'){
			cin >> a >> b;
			que.push_back({{0,x},{a,b}});
		}
		else{
			cin >> a;
			que.push_back({{1,x},{a,a}});
		}
	}
	
	for(int x=1;x<=n;x++){
		sort(adj[x].begin(),adj[x].end(),cmp);
	}
	
	build(1,0);
	
	//show(done,1);
	
	sort(add.begin(),add.end());
	
	int take=0;
	
	//for(auto it:add){
		//show2(it.first,it.first,it.second,it.second);
	//}
	
	for(auto it:que){
		int d=it.first.second;
		while(take<(int)add.size()&&add[take].first<=d){
			upd(add[take].second,1);
			take++;
		}
		if(it.first.first==0){
			//bool
			a=it.second.first;
			b=it.second.second;
			
			bool amos=false;
			for(auto it:storage[b]){
				//show(it,it);
				//show(dep[it],dep[it]);
				//show2(pos[dep[it]][b],pos[dep[it]][b],pos[dep[it]][a],pos[dep[it]][a]);
				if(val[dep[it]][a]!=-1&&val[dep[it]][a]<=d&&(pos[dep[it]][b]<=pos[dep[it]][a])) amos=true;
			}
			
			if(amos) cout << "yes\n";
			else cout << "no\n";
		}
		else{
			//count
			a=it.second.first;
			
			int counter=0;
			for(auto it:storage[a]){
				//show(it,it);
				//show(out[it],out[it]);
				counter+=query(pos[dep[it]][a]+1,out[it])+1;
				//show(counter,counter);
			}
			cout << counter << "\n";
		}
	}
}
																   
int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int t=1;
	//cin >> t;
	while(t--){
		solve();
	}
}

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