oj.uz

Submission #528234

# Submission time Handle Problem Language Result Execution time Memory
528234 2022-02-19T18:00:38 Z codr0 Inside information (BOI21_servers) C++14
0 / 100
 83 ms 38048 KB 
// Code by Parsa Eslami
 
#include <bits/stdc++.h>
#define pii pair<int,int>
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORR(i,a,b) for(int i=a;i>=b;i--)
#define S second
#define F first
#define pb push_back
#define SZ(x) (int)x.size()
#define all(x) x.begin(),x.end()
#define err(x) cout<<#x<<": "<<x<<'\n';
 
using namespace std;
const int N=3e5+4;
struct query{
	string id;
	int v,u,time;
};
struct fenwick{
	int fen[N];
	vector<pii> past;//id val
	int ps0;
	void add(int k,int x){
		past.pb({k,x});
		if(k==0){
			ps0+=x;
			return;
		}
		while(k<N){
			fen[k]+=x;
			k+=(k&(-k));
		}
	}
	int get(int k){
		int rt=0;
		while(k){
			rt+=fen[k];
			k-=(k&(-k));
		}
		return (rt+ps0);
	}
	void clear(){
		for(pii x0:past) add(x0.F,-x0.S);
		past.clear();
	}
};fenwick fen;
vector<int> adj[N];
vector<int> W[N];
int S[N];
bool hide[N];
int ans[N];
pii UD[N],DU[N];
int mark[N];
vector<query> q[N];
vector<query> ot;

	void plant(int v,int p){
		S[v]=1;
		for(int u:adj[v]) if(!hide[u]&&u!=p) plant(u,v),S[v]+=S[u];
	}

	int find_centroid(int v,int p,int _n){
		for(int u:adj[v]) if(u!=p&&!hide[u]&&2*S[u]>_n) return find_centroid(u,v,_n);
		return v;
	}

	void set_UD(int v,int p,int UDmn,int UDmx,int DUmn,int DUmx,int mrk){
		mark[v]=mrk;

		if(UDmn!=-1){
			UD[v]={UDmn,UDmx};
		}else UD[v]={-1,-1};

		if(DUmn!=-1){
			DU[v]={DUmn,DUmx};
		}else DU[v]={-1,-1};

		FOR(i,0,SZ(adj[v])-1){
			int u=adj[v][i];
			int w=W[v][i];
			if(!hide[u]&&u!=p){
				pii ud={-1,-1};
				if(UDmn!=-1&&UDmx<w){
					ud.F=UDmn;
					ud.S=w;
				}

				pii du={-1,-1};
				if(DUmn!=-1&&DUmn>w){
					du.F=w;
					du.S=DUmx;
				}
				set_UD(u,v,ud.F,ud.S,du.F,du.S,mrk);
			}
		}

	}

	void solveQ(int v,int p){
		for(auto x0:q[v]){
			if(x0.id=="Q"){
				int u=x0.u;
				if(mark[u]&&mark[v]&&mark[u]!=mark[v]&&DU[v].F!=-1&&UD[u].F!=-1&&DU[v].S<UD[u].F&&UD[u].S<=x0.time) ans[x0.time]=1;
			}
		}
		for(int u:adj[v]) if(!hide[u]&&u!=p) solveQ(u,v);
	}

	void set_fen(int v,int p){
		if(UD[v].F!=-1){
			fen.add(UD[v].S,1);
		}
		for(int u:adj[v]) if(!hide[u]&&u!=p) set_fen(u,v);
	}

	void er(int v,int p){
		if(UD[v].F!=-1){
			fen.add(UD[v].S,-1);
		}
		for(int u:adj[v]) if(!hide[u]&&u!=p) er(u,v);
	}

	void solveC(int v,int p){
		for(auto x0:q[v]){
			if(x0.id=="C"){
				if(DU[v].F!=-1) ans[x0.time]+=fen.get(x0.time);
			}
		}
		for(int u:adj[v]) if(u!=p&&!hide[u]) solveC(u,v);
	}

	void set0(int v,int p){
		mark[v]=0;
		for(int u:adj[v]) if(!hide[u]&&u!=p) set0(u,v);
	}

	void decompose(int v){
		plant(v,v);
		v=find_centroid(v,v,S[v]);
		mark[v]=SZ(adj[v])+1;
		hide[v]=1;
		DU[v]=UD[v]={1e9,0};
		FOR(i,0,SZ(adj[v])-1){
			int u=adj[v][i];
			int w=W[v][i];
			if(!hide[u]){
				set_UD(u,v,w,w,w,w,i+1);
			}
		}
		solveQ(v,v);
		set_fen(v,v);
		for(auto x0:q[v]){
			if(x0.id=="C"){
				ans[x0.time]+=fen.get(x0.time);
			}
		}
		FOR(i,0,SZ(adj[v])-1){
			int u=adj[v][i];
			if(!hide[u]){
				er(u,u);
				solveC(u,u);
			}
		}
		fen.clear();
		set0(v,v);
		for(int u:adj[v]) if(!hide[u]) decompose(u);
	}

	int32_t main(){
	ios_base::sync_with_stdio(0); cin.tie(0);

	int n,k; cin>>n>>k;
	FOR(i,1,n+k-1){
		query x0;
		cin>>x0.id;
		if(x0.id=="S"){
			int u,v; cin>>u>>v;
			adj[u].pb(v);
			adj[v].pb(u);
			W[u].pb(i);
			W[v].pb(i);
		}else{
			if(x0.id=="C"){
				cin>>x0.v;
			}else{
				cin>>x0.u>>x0.v;
			}
			x0.time=i;
			q[x0.v].pb(x0);
			ot.pb(x0);
		}
	}
	decompose(1);
	for(auto x0:ot){
		if(x0.id=="C"){
			cout<<ans[x0.time]<<'\n';
		}else cout<<((ans[x0.time]==0&&x0.u!=x0.v)?"no\n":"yes\n");
	}

	return 0;
	}

Subtask #1
0 / 2.5

# Verdict Execution time Memory Grader output
1 Incorrect 83 ms 38000 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Incorrect 83 ms 38000 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 2.5

# Verdict Execution time Memory Grader output
1 Incorrect 56 ms 38012 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Incorrect 56 ms 38012 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 70 ms 38048 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 70 ms 38048 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 71 ms 38008 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 71 ms 38008 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 12.5

# Verdict Execution time Memory Grader output
1 Incorrect 63 ms 37988 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Incorrect 63 ms 37988 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Incorrect 63 ms 38004 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Incorrect 63 ms 38004 KB Output isn't correct
2 Halted 0 ms 0 KB -