Submission #1179954

#	Time	Username	Problem	Language	Result	Execution time	Memory
1179954		mertbbm	Inside information (BOI21_servers)	C++20	100 / 100	587 ms	138240 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];
pii val[18][120005];
vector<int>storage[120005];
vector<pii>add;
int dep[120005];
int color[18][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, int cur2){
	if(!amos){
		storage[index].push_back(cent);
	}
	else{
		val[lvl][index].first=cur;
		add.push_back({cur,ptr});
	}
	val[lvl][index].second=cur2;
	color[lvl][index]=cent;
	pos[lvl][index]=ptr;
	//show3(lvl,lvl,index,index,cur,cur);
	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,cur2);
	}
}

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;
	dep[cent]=lvl;
	val[lvl][cent]={0,0};
	color[lvl][cent]=cent;
	visited[cent]=true;
	//show2(lvl,lvl,cent,cent);
	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,nxt.second);
			}
			else{
				//go up
				dfs3(it.first,nxt.first,cent,it.second,0,lvl,ptr,nxt.second);
			}
		}
		storage[nxt.first].push_back(cent);
		add.push_back({nxt.second,ptr});
		out[cent]=ptr;
		pos[lvl][nxt.first]=ptr++;
		val[lvl][nxt.first]={nxt.second,nxt.second};
		color[lvl][nxt.first]=cent;
	}
	
	for(auto nxt:adj[cent]){
		if(visited[nxt.first]) continue;
		build(nxt.first,lvl+1);
	}
}

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;
	map<pii,int>mp;
	for(int x=0;x<n+q-1;x++){
		cin >> temp;
		if(temp=='S'){
			cin >> a >> b;
			mp[{a,b}]=x;
			mp[{b,a}]=x;
			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);
	
	sort(add.begin(),add.end());
	
	int take=0;

	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);
				if(val[dep[it]][b].second>d) continue;
				if(color[dep[it]][a]!=color[dep[it]][b]) continue;
				//show(it,it);
				//show(val,val[dep[it]][a].first);
				
				if(val[dep[it]][a].first!=-1&&val[dep[it]][a].first<=d&&pos[dep[it]][b]<=pos[dep[it]][a]) amos=true;
				if(it==a) amos=true;
				//show(amos,amos);
			}
			//show(amos,amos);
			if(mp.find({a,b})!=mp.end()&&mp[{a,b}]<=d) amos=true;
			if(a==b) amos=true;
			if(amos) cout << "yes\n";
			else cout << "no\n";
		}
		else{
			//count
			a=it.second.first;
			//show(a,a);
			int counter=0;
			for(auto it:storage[a]){
				if(val[dep[it]][a].second>d) continue;
				//show(it,it);
				//show(val,val[dep[it]][a].second);
				counter+=query(pos[dep[it]][a]+1,out[it])+1;
			}
			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: 2 / 2
• Subtask 1-2: 3 / 3
• Subtask 2-1: 2 / 2
• Subtask 2-2: 3 / 3
• Subtask 3-1: 5 / 5
• Subtask 3-2: 5 / 5
• Subtask 4-1: 10 / 10
• Subtask 4-2: 10 / 10
• Subtask 5-1: 12 / 12
• Subtask 5-2: 13 / 13
• Subtask 6-1: 17 / 17
• Subtask 6-2: 18 / 18