oj.uz

Submission #699025

# Submission time Handle Problem Language Result Execution time Memory
699025 2023-02-15T10:42:33 Z jamezzz Inside information (BOI21_servers) C++17
100 / 100
 747 ms 104500 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 240005

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){
		int lim=fpar(i,des[i]);
		if(i!=1)rem[lim].pb(pwt[i]);
		for(int t:cqry[i]){
			qrys[i].pb({t,1});
			int lim=fpar(i,asc[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
S 2 5
S 2 4
S 7 11
S 1 2
S 5 6
S 6 10
S 6 9
C 1
C 2
C 3
C 4
C 5
C 6
C 7
C 8
C 9
C 10
C 11
C 12

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
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 59 ms 42948 KB Output is correct
2 Correct 78 ms 44924 KB Output is correct
3 Correct 78 ms 44896 KB Output is correct
4 Correct 86 ms 45044 KB Output is correct
5 Correct 72 ms 45236 KB Output is correct
6 Correct 78 ms 44860 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 59 ms 42948 KB Output is correct
2 Correct 78 ms 44924 KB Output is correct
3 Correct 78 ms 44896 KB Output is correct
4 Correct 86 ms 45044 KB Output is correct
5 Correct 72 ms 45236 KB Output is correct
6 Correct 78 ms 44860 KB Output is correct
7 Correct 66 ms 43252 KB Output is correct
8 Correct 143 ms 46408 KB Output is correct
9 Correct 141 ms 46008 KB Output is correct
10 Correct 148 ms 46456 KB Output is correct
11 Correct 143 ms 46700 KB Output is correct
12 Correct 121 ms 46056 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 62 ms 42940 KB Output is correct
2 Correct 396 ms 87744 KB Output is correct
3 Correct 387 ms 87792 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 62 ms 42940 KB Output is correct
2 Correct 396 ms 87744 KB Output is correct
3 Correct 387 ms 87792 KB Output is correct
4 Correct 66 ms 43212 KB Output is correct
5 Correct 407 ms 88104 KB Output is correct
6 Correct 375 ms 88284 KB Output is correct
7 Correct 393 ms 88416 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 42884 KB Output is correct
2 Correct 560 ms 100116 KB Output is correct
3 Correct 556 ms 100128 KB Output is correct
4 Correct 303 ms 98360 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 42884 KB Output is correct
2 Correct 560 ms 100116 KB Output is correct
3 Correct 556 ms 100128 KB Output is correct
4 Correct 303 ms 98360 KB Output is correct
5 Correct 58 ms 43292 KB Output is correct
6 Correct 657 ms 103228 KB Output is correct
7 Correct 455 ms 104440 KB Output is correct
8 Correct 723 ms 104440 KB Output is correct
9 Correct 724 ms 104368 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 42924 KB Output is correct
2 Correct 334 ms 89152 KB Output is correct
3 Correct 497 ms 89152 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 42924 KB Output is correct
2 Correct 334 ms 89152 KB Output is correct
3 Correct 497 ms 89152 KB Output is correct
4 Correct 62 ms 43296 KB Output is correct
5 Correct 425 ms 92088 KB Output is correct
6 Correct 581 ms 92300 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 54 ms 42972 KB Output is correct
2 Correct 555 ms 100016 KB Output is correct
3 Correct 568 ms 100016 KB Output is correct
4 Correct 322 ms 98444 KB Output is correct
5 Correct 56 ms 42968 KB Output is correct
6 Correct 333 ms 89064 KB Output is correct
7 Correct 497 ms 89060 KB Output is correct
8 Correct 519 ms 89728 KB Output is correct
9 Correct 540 ms 89408 KB Output is correct
10 Correct 475 ms 94068 KB Output is correct
11 Correct 510 ms 93240 KB Output is correct

Subtask #10
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 54 ms 42972 KB Output is correct
2 Correct 555 ms 100016 KB Output is correct
3 Correct 568 ms 100016 KB Output is correct
4 Correct 322 ms 98444 KB Output is correct
5 Correct 56 ms 42968 KB Output is correct
6 Correct 333 ms 89064 KB Output is correct
7 Correct 497 ms 89060 KB Output is correct
8 Correct 519 ms 89728 KB Output is correct
9 Correct 540 ms 89408 KB Output is correct
10 Correct 475 ms 94068 KB Output is correct
11 Correct 510 ms 93240 KB Output is correct
12 Correct 59 ms 43216 KB Output is correct
13 Correct 638 ms 103128 KB Output is correct
14 Correct 458 ms 104252 KB Output is correct
15 Correct 726 ms 104500 KB Output is correct
16 Correct 747 ms 104404 KB Output is correct
17 Correct 62 ms 43212 KB Output is correct
18 Correct 425 ms 92088 KB Output is correct
19 Correct 579 ms 92264 KB Output is correct
20 Correct 633 ms 92688 KB Output is correct
21 Correct 632 ms 92660 KB Output is correct
22 Correct 670 ms 97020 KB Output is correct
23 Correct 593 ms 97168 KB Output is correct
24 Correct 480 ms 94652 KB Output is correct

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 57 ms 42956 KB Output is correct
2 Correct 78 ms 44840 KB Output is correct
3 Correct 74 ms 44916 KB Output is correct
4 Correct 90 ms 45040 KB Output is correct
5 Correct 73 ms 45200 KB Output is correct
6 Correct 81 ms 44876 KB Output is correct
7 Correct 62 ms 42956 KB Output is correct
8 Correct 420 ms 87616 KB Output is correct
9 Correct 401 ms 87612 KB Output is correct
10 Correct 53 ms 42968 KB Output is correct
11 Correct 550 ms 100080 KB Output is correct
12 Correct 573 ms 99972 KB Output is correct
13 Correct 316 ms 98388 KB Output is correct
14 Correct 57 ms 42960 KB Output is correct
15 Correct 339 ms 89020 KB Output is correct
16 Correct 493 ms 89052 KB Output is correct
17 Correct 518 ms 89832 KB Output is correct
18 Correct 537 ms 89404 KB Output is correct
19 Correct 469 ms 94128 KB Output is correct
20 Correct 502 ms 93268 KB Output is correct
21 Correct 417 ms 88244 KB Output is correct
22 Correct 410 ms 88236 KB Output is correct
23 Correct 482 ms 88652 KB Output is correct
24 Correct 509 ms 88708 KB Output is correct
25 Correct 582 ms 91660 KB Output is correct
26 Correct 431 ms 88916 KB Output is correct
27 Correct 408 ms 88676 KB Output is correct

Subtask #12
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 57 ms 42956 KB Output is correct
2 Correct 78 ms 44840 KB Output is correct
3 Correct 74 ms 44916 KB Output is correct
4 Correct 90 ms 45040 KB Output is correct
5 Correct 73 ms 45200 KB Output is correct
6 Correct 81 ms 44876 KB Output is correct
7 Correct 62 ms 42956 KB Output is correct
8 Correct 420 ms 87616 KB Output is correct
9 Correct 401 ms 87612 KB Output is correct
10 Correct 53 ms 42968 KB Output is correct
11 Correct 550 ms 100080 KB Output is correct
12 Correct 573 ms 99972 KB Output is correct
13 Correct 316 ms 98388 KB Output is correct
14 Correct 57 ms 42960 KB Output is correct
15 Correct 339 ms 89020 KB Output is correct
16 Correct 493 ms 89052 KB Output is correct
17 Correct 518 ms 89832 KB Output is correct
18 Correct 537 ms 89404 KB Output is correct
19 Correct 469 ms 94128 KB Output is correct
20 Correct 502 ms 93268 KB Output is correct
21 Correct 417 ms 88244 KB Output is correct
22 Correct 410 ms 88236 KB Output is correct
23 Correct 482 ms 88652 KB Output is correct
24 Correct 509 ms 88708 KB Output is correct
25 Correct 582 ms 91660 KB Output is correct
26 Correct 431 ms 88916 KB Output is correct
27 Correct 408 ms 88676 KB Output is correct
28 Correct 61 ms 43212 KB Output is correct
29 Correct 139 ms 46396 KB Output is correct
30 Correct 129 ms 46016 KB Output is correct
31 Correct 147 ms 46536 KB Output is correct
32 Correct 135 ms 46752 KB Output is correct
33 Correct 120 ms 46136 KB Output is correct
34 Correct 72 ms 43196 KB Output is correct
35 Correct 415 ms 88044 KB Output is correct
36 Correct 375 ms 88276 KB Output is correct
37 Correct 407 ms 88480 KB Output is correct
38 Correct 60 ms 43272 KB Output is correct
39 Correct 645 ms 103284 KB Output is correct
40 Correct 453 ms 104324 KB Output is correct
41 Correct 746 ms 104404 KB Output is correct
42 Correct 722 ms 104408 KB Output is correct
43 Correct 61 ms 43208 KB Output is correct
44 Correct 429 ms 92080 KB Output is correct
45 Correct 593 ms 92184 KB Output is correct
46 Correct 623 ms 92728 KB Output is correct
47 Correct 644 ms 92644 KB Output is correct
48 Correct 694 ms 96976 KB Output is correct
49 Correct 611 ms 97156 KB Output is correct
50 Correct 489 ms 94636 KB Output is correct
51 Correct 474 ms 89652 KB Output is correct
52 Correct 418 ms 89488 KB Output is correct
53 Correct 433 ms 89088 KB Output is correct
54 Correct 423 ms 89756 KB Output is correct
55 Correct 456 ms 89384 KB Output is correct
56 Correct 526 ms 89404 KB Output is correct
57 Correct 538 ms 92216 KB Output is correct
58 Correct 628 ms 93492 KB Output is correct
59 Correct 443 ms 89476 KB Output is correct