Submission #489280

#	Time	Username	Problem	Language	Result	Execution time	Memory
489280		CSQ31	Inside information (BOI21_servers)	C++17	100 / 100	521 ms	44384 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);
#define all(a) a.begin(),a.end()
typedef pair<int,int> pii;
const int MAXN = 2e5;
vector<pii>adj[MAXN];
int dep[MAXN],par[18][MAXN],asc[MAXN],dsc[MAXN],val[MAXN],n,k;
char c[250000];
int a[250000],d[250000],ans[250000];
void dfs0(int v,int u,int ww){
	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;
		asc[x] = dsc[x] = dep[v];
		if(w > ww || v==1)asc[x] = asc[v];	
		if(w < ww || v==1)dsc[x] = dsc[v];
		
		dep[x] = dep[v]+1;
		par[0][x] = v;
		dfs0(x,v,w);
	}
}
int jump(int v,int d){
	for(int i=0;i<=17 && d;i++){
		if(d&1)v=par[i][v];
		d/=2;
	}
	return v;
}
int lca(int v,int u){
	if(dep[v] < dep[u])swap(v,u);
	v = jump(v,dep[v] - dep[u]);
	
	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];
}
//want to count number of paths from i to j
//such that i->j is increasing
//and the last edge that touches j is <= t
//let c be the centroid
//call node x a start node if c->x is increasing
//call node x an end node if c->x is decreasing 

//can sweepline on their time but overcounting????
//call the join time of node x the time where x is first connected to c
//the add time of end node x the time where the first edge from path c->i is added
//contribution for start node i is number of end nodes with join time > its join time and add time <= t
//ok so sweepline backwards by join time then pick whatever sum aggre ds,fenwick should be fast enough 
vector<int>cq[MAXN];
int sub[MAXN],join[MAXN],reach[MAXN],fen[250000];
bool ded[MAXN];
void upd(int i,int x){
	for(;i<=240000;i+=i&(-i))fen[i]+=x;
}
int query(int i){
	int res = 0;
	for(;i;i-=i&(-i))res+=fen[i];
	return res;
}

void get(int v,int u){
	sub[v] = 1;
	for(auto x:adj[v]){
		if(x.fi==u ||ded[x.fi])continue;
		get(x.fi,v);
		sub[v]+=sub[x.fi];
	}
}
int cen(int v,int u,int n){
	for(auto x:adj[v]){
		if(ded[x.fi] || x.fi == u)continue;
		if(sub[x.fi] > n/2)return cen(x.fi,v,n);
	}
	return v;
}
vector<int>st,ed;
void dfs(int v,int u,int type,int ww){ //type 1 increasing,type 2 decreasing
	if(type<=1)st.pb(v);
	if(type!=1)ed.pb(v);
	
	join[v] = max(join[u],ww);
	reach[v] = min(reach[u],ww);
	for(pii z:adj[v]){
		int x = z.fi;
		int w = z.se;
		if(x==u || ded[x])continue;
		if((!type || type ==1) && ww > w)dfs(x,v,1,w);
		if((!type || type ==2) && ww < w)dfs(x,v,2,w);
	}
	
}
void solve(int v){
	get(v,0);
	v = cen(v,0,sub[v]);
	ded[v] = 1;
	join[v] = 0;
	reach[v] = 1e9;
	for(auto z:adj[v]){
		int x = z.fi;
		int w = z.se;
		if(ded[x])continue;
		dfs(x,v,0,w);
	}
	//for a st node i,want number of ed nodes j st reach[j] > join[i] and join[j] <= current ime
	//first ineq eliminate by sweep line
	//second ineq can eliminate by [insert ds]
	st.pb(v);
	sort(all(st),[&](int i,int j){return join[i] > join[j];});
	sort(all(ed),[&](int i,int j){return reach[i] > reach[j];});
	
	int ptr = 0;
	for(int i=0;i<sz(st);i++){
		while(ptr<sz(ed) && reach[ed[ptr]] > join[st[i]]){
			upd(join[ed[ptr]],1);
			ptr++;
		}
		
		for(int tim : cq[st[i]]){
			/*
			for(int j=0;j<ptr;j++){
				if(join[ed[j]] <= tim+1)ans[tim]++;
			}*/
			ans[tim]+=query(tim+1);
			if(st[i]!=v && join[st[i]] <= tim+1)ans[tim]++;
		}
	}
	for(int i=0;i<ptr;i++)upd(join[ed[i]],-1);
	st.clear();
	ed.clear();
	for(auto z:adj[v])if(!ded[z.fi])solve(z.fi);
}
int main()
{
	cin>>n>>k;
	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],i+1});
			adj[d[i]].pb({a[i],i+1});
		}
		if(c[i]=='C')cq[a[i]].pb(i);
	}
	dfs0(1,0,0);
	solve(1);
	for(int i=0;i<n+k-1;i++){
		if(c[i]=='C')cout<<ans[i]+1<<'\n';
		else if(c[i]=='Q'){ //this solves for Q queries now for C queries
			int v = a[i];
			int u = d[i];

			int m = lca(v,u),last = -1e9;
			if(v!=m)last = val[v];
			else if(u!=m)last = val[jump(u,dep[u]-dep[m]-1)];
			bool ok= (last<=i);
			
			if(asc[v] > dep[m] || dsc[u] > dep[m])ok = 0;
			if(v!=m && u!= m){
				v = jump(v,dep[v]-dep[m]-1);
				u = jump(u,dep[u]-dep[m]-1);
				if(val[u] > val[v])ok = 0;
			}
			if(ok)cout<<"yes"<<'\n';
			else cout<<"no"<<'\n';
		}
		
	}
}

• Subtask 1: 2.5 / 2.5
• Subtask 2: 2.5 / 2.5
• Subtask 3: 2.5 / 2.5
• Subtask 4: 2.5 / 2.5
• Subtask 5: 5 / 5
• Subtask 6: 5 / 5
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 12.5 / 12.5
• Subtask 10: 12.5 / 12.5
• Subtask 11: 17.5 / 17.5
• Subtask 12: 17.5 / 17.5