oj.uz

Submission #698978

# Submission time Handle Problem Language Result Execution time Memory
698978 2023-02-15T06:06:02 Z jamezzz Inside information (BOI21_servers) C++17
0 / 100
 494 ms 83788 KB 
#include <bits/stdc++.h>
using namespace std;

#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;
}

struct node{
	int s,e,m,v,lz;
	node *l,*r;
	node(int _s,int _e){
		s=_s,e=_e,m=(s+e)>>1,v=0,lz=0;
		if(s!=e)l=new node(s,m),r=new node(m+1,e);
	}
	void ppo(){
		v+=lz;
		if(s!=e)l->lz+=lz,r->lz+=lz;
		lz=0;
	}
	void up(int x,int y,int nv){
		if(s==x&&e==y){lz+=nv;return;}
		if(y<=m)l->up(x,y,nv);
		else if(x>m)r->up(x,y,nv);
		else l->up(x,m,nv),r->up(m+1,y,nv);
		l->ppo(),r->ppo();
		v=l->v+r->v;
	}
	int qry(int x,int y){
		ppo();
		if(s==x&&e==y)return v;
		if(y<=m)return l->qry(x,y);
		if(x>m)return r->qry(x,y);
		return l->qry(x,m)+r->qry(m+1,y);
	}
}*rt;

#define maxn 120005

int n,k,p[20][maxn],pwt[maxn],asc[maxn],des[maxn],dep[maxn],ans[maxn],pre[maxn],pst[maxn],cnt=1;
vii AL[maxn];
vi cqry[maxn],rem[maxn];
vii qqry[maxn],qrys[maxn];

void dfs(int u,int par){
	pre[u]=cnt++;
	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]=1;
		else asc[v]=1,des[v]=des[u]+1;
		dep[v]=dep[u]+1;
		pwt[v]=w;
		dfs(v,u);
	}
	pst[u]=cnt-1;
}

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[0][a];
}

void dfs2(int u,int p){
	for(auto[t,m]:qrys[u]){
		ans[t]+=rt->qry(0,t)*m;
	}
	for(auto [v,w]:AL[u]){
		if(v==p)continue;
		rt->up(w,w,1);
		dfs2(v,u);
	}
	for(int i:rem[u])rt->up(i,i,-1);
}

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);
	
	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;
			}
		}
	}
	
	//answer c queries going down first
	vector<iii> queries;
	for(int i=1;i<=n;++i){
		if(i!=1)queries.pb({pwt[i],i,0});//update
		for(int t:cqry[i])queries.pb({t,i,1});//query
	}
	sort(all(queries));
	rt=new node(1,n);
	for(auto [t,i,type]:queries){
		if(type==0){
			if(i!=1){
				int par=p[0][i];
				rt->up(pre[par],pre[par],1);
			}
			int lim=fpar(i,des[i]);
			if(lim!=1){
				lim=p[0][lim];
				rt->up(pre[lim],pre[lim],-1);
			}
		}
		else{
			ans[t]+=rt->qry(pre[i],pst[i]);
		}
	}
	
	for(int i=1;i<=n;++i){
		for(int t:cqry[i]){
			qrys[i].pb({t,1});
			int lim=fpar(i,asc[i]),lim2=fpar(i,des[i]);
			if(i!=1)rem[lim2].pb(pwt[i]);
			qrys[lim].pb({t,-1});
		}
	}
	
	rt=new node(0,n+k);
	dfs2(1,-1);
	
	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

6 9
S 1 2
S 1 3
S 3 4
S 4 5
S 1 6
Q 2 1
Q 3 1
Q 4 1
Q 5 1
Q 6 1
Q 1 2
Q 3 2
Q 4 2
Q 5 2
Q 6 2

12 12
S 1 3
S 5 8
S 7 12
S 5 7
C 1
C 2
C 3
C 4
C 5
C 6
C 7
C 8
C 9
C 10
C 11
C 12
S 2 5
S 2 4
S 7 11
S 1 2
S 5 6
S 6 10
S 6 9

find preorder/postorder
segment tree
make into offline queries
*/

Compilation message

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

Subtask #1
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 57 ms 28084 KB Output is correct
2 Incorrect 72 ms 30728 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 57 ms 28084 KB Output is correct
2 Incorrect 72 ms 30728 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 2.5

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

Subtask #4
0 / 2.5

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

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 28060 KB Output is correct
2 Incorrect 494 ms 83720 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 28060 KB Output is correct
2 Incorrect 494 ms 83720 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 28016 KB Output is correct
2 Incorrect 307 ms 73240 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 28016 KB Output is correct
2 Incorrect 307 ms 73240 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #9
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 49 ms 28060 KB Output is correct
2 Incorrect 479 ms 83788 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 49 ms 28060 KB Output is correct
2 Incorrect 479 ms 83788 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 50 ms 28108 KB Output is correct
2 Incorrect 89 ms 30816 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 50 ms 28108 KB Output is correct
2 Incorrect 89 ms 30816 KB Output isn't correct
3 Halted 0 ms 0 KB -