Submission #697594

#	Time	Username	Problem	Language	Result	Execution time	Memory
697594		jamezzz	Inside information (BOI21_servers)	C++17	0 / 100	50 ms	22740 KiB

servers

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

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

typedef tree<long long, null_type, less<long long>,
rb_tree_tag, tree_order_statistics_node_update> pbds;
//less_equal for identical elements

#ifdef DEBUG
#define dbg(...) printf(__VA_ARGS__);
#define getchar_unlocked getchar
#else
#define dbg(...)
#endif
#define sf scanf
#define pf printf
#define fi first
#define se second
#define pb push_back
#define psf push_front
#define ppb pop_back
#define ppf pop_front
#define sz(x) (int)x.size()
#define mnto(x,y) x=min(x,(__typeof__(x))y)
#define mxto(x,y) x=max(x,(__typeof__(x))y)
#define INF 1023456789
#define LINF 1023456789123456789
#define all(x) x.begin(),x.end()
#define lb(x,v) (lower_bound(all(x),v)-x.begin())
#define ub(x,v) (upper_bound(all(x),v)-x.begin())
#define disc(x) sort(all(x));x.resize(unique(all(x))-x.begin());
typedef long long ll;
typedef long double ld;
typedef pair<int,int> ii;
typedef pair<ll,ll> pll;
typedef tuple<int,int,int> iii;
typedef tuple<int,int,int,int> iiii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;
mt19937 rng(time(0));

#define mod 1000000007

inline int add(int a,int b){
	int r=a+b;
	while(r>=mod)r-=mod;
	while(r<0)r+=mod;
	return r;
}

inline int mult(int a,int b){
	return (int)(((ll)(a*b))%mod);
}

inline int rd(){
	int x=0;
	char ch=getchar_unlocked();
	while(!(ch&16))ch=getchar();//keep reading while current character is whitespace
    while(ch&16){//this will break when ‘\n’ or ‘ ‘ is encountered
		x=(x<<3)+(x<<1)+(ch&15);
		ch=getchar_unlocked();
	}
	return x;
}

#define maxn 120005

int n,k,p[20][maxn],pwt[maxn],asc[maxn],des[maxn],dep[maxn],ans[maxn];
vii AL[maxn];
vi cqry[maxn];
vii qqry[maxn];

void dfs(int u,int par){
	for(auto[v,w]:AL[u]){
		if(v==par)continue;
		p[0][v]=u;
		if(pwt[u]==-1)asc[v]=des[v]=1;
		else if(w<pwt[u])asc[v]=asc[u]+1,des[v]=des[u];
		else asc[v]=asc[u],des[v]=des[u]+1;
		dep[v]=dep[u]+1;
		pwt[v]=w;
		dfs(v,u);
	}
}

int fpar(int x,int k){
	for(int i=19;i>=0;--i){
		if((1<<i)<=k)x=p[i][x],k-=(1<<i);
	}
	return x;
}

int lca(int a,int b){
	if(dep[a]<dep[b])swap(a,b);
	for(int k=19;k>=0;--k){
		if(p[k][a]!=-1&&dep[p[k][a]]>=dep[b])a=p[k][a];
	}
	if(a==b)return a;
	for(int k=19;k>=0;--k){
		if(p[k][a]!=p[k][b])a=p[k][a],b=p[k][b];
	}
	return p[a][0];
}

pbds* dfs2(int u,int p,pbds *pset){
	/*
	pf("dfs2: %d %d {",u,p);
	for(int i:*pset)pf("%d ",i);
	pf("}\n");
	*/
	pbds *cset=new pbds();
	for(int t:cqry[u])ans[t]+=(*pset).order_of_key(t);
	pbds *torem=new pbds();
	for(auto[v,w]:AL[u]){
		if(v==p)continue;
		if(w<pwt[u]){
			(*pset).insert(w);
			pbds *rset=dfs2(v,u,pset);
			for(int x:*rset)(*pset).insert(x);
			(*rset).insert(w);
			for(int t:cqry[u])ans[t]+=(*rset).order_of_key(t);
			if(sz((*rset))>sz((*torem)))swap(*torem,*rset);
			for(int i:*rset)(*torem).insert(i);
		}
		else{
			pbds *s=new pbds();
			(*s).insert(w);
			pbds *rset=dfs2(v,u,s);
			(*rset).insert(w);
			for(int x:*rset)(*pset).insert(x);
			for(int t:cqry[u])ans[t]+=(*rset).order_of_key(t);
			if(sz((*rset))>sz((*cset)))swap(*rset,*cset);
			for(int i:*rset)(*cset).insert(i);
		}
	}
	for(int i:*torem)(*pset).erase(i);
	/*
	pf("pset %d: {",u);
	for(int i:*pset)pf("%d ",i);
	pf("}\n");
	pf("cset %d: {",u);
	for(int i:*cset)pf("%d ",i);
	pf("}\n");
	*/
	return cset;
}

int main(){
	sf("%d%d",&n,&k);
	for(int i=0;i<n+k-1;++i){
		char c;sf(" %c",&c);
		if(c=='S'){
			int a,b;sf("%d%d",&a,&b);
			AL[a].pb({b,i});
			AL[b].pb({a,i});
			ans[i]=-3;
		}
		else if(c=='Q'){
			int a,b;sf("%d%d",&a,&b);
			qqry[b].pb({a,i});
		}
		else{
			int a;sf("%d",&a);
			cqry[a].pb(i);
		}
	}
	for(int i=1;i<=n;++i)sort(all(AL[i]),[](ii &a,ii &b){return a.se>b.se;});
	
	p[0][1]=-1;
	asc[1]=des[1]=0;
	pwt[1]=-1;
	dfs(1,0);
	
	#ifdef DEBUG
	for(int i=1;i<=n;++i){
		pf("%d: asc %d, dec %d\n",i,asc[i],des[i]);
	}
	#endif
	
	for(int k=0;k<19;++k){
		for(int i=1;i<=n;++i){
			if(p[k][i]!=-1)p[k+1][i]=p[k][p[k][i]];
			else p[k+1][i]=-1;
		}
	}
	
	//x --asc--> u --w1--> lca
	//y --w3--> smt --dec--> v --w2--> lca
	//w1 < w2
	//w3 < t
	for(int x=1;x<=n;++x){
		for(auto[y,t]:qqry[x]){
			if(x==y){
				ans[t]=-1;
				continue;
			}
			int l=lca(x,y);
			if(l==y){
				int jmp=dep[x]-dep[y];
				if(asc[x]>=jmp&&pwt[fpar(x,jmp-1)]<t)ans[t]=-1;
				else ans[t]=-2;
			}
			else if(l==x){
				int jmp=dep[y]-dep[x];
				if(des[y]>=jmp&&pwt[y]<t)ans[t]=-1;
				else ans[t]=-2;
			}
			else{
				int jmpx=dep[x]-dep[l],jmpy=dep[y]-dep[l];
				if(asc[x]<jmpx||des[y]<jmpy)ans[t]=-2;
				else if(pwt[fpar(x,jmpx-1)]>=pwt[fpar(y,jmpy-1)])ans[t]=-2;
				else if(pwt[y]>t)ans[t]=-2;
				else ans[t]=-1;
			}
		}
	}
	
	pwt[1]=INF;
	pbds *s=new pbds();
	dfs2(1,-1,s);
	
	for(int i=0;i<n+k-1;++i){
		if(ans[i]==-1)pf("yes\n");
		else if(ans[i]==-2)pf("no\n");
		else if(ans[i]!=-3)pf("%d\n",ans[i]+1);
	}
}

/*
6 9
S 1 2
S 1 3
S 3 4
Q 5 1
S 4 5
S 1 6
Q 5 1
Q 1 5
C 1
C 2
C 3
C 4
C 5
C 6
*/

Compilation message (stderr)

servers.cpp: In function 'int main()':
servers.cpp:153:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  153 |  sf("%d%d",&n,&k);
      |    ^
servers.cpp:155:12: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  155 |   char c;sf(" %c",&c);
      |            ^
servers.cpp:157:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  157 |    int a,b;sf("%d%d",&a,&b);
      |              ^
servers.cpp:163:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  163 |    int a,b;sf("%d%d",&a,&b);
      |              ^
servers.cpp:167:12: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  167 |    int a;sf("%d",&a);
      |            ^

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