oj.uz

Submission #528300

# Submission time Handle Problem Language Result Execution time Memory
528300 2022-02-19T20:39:49 Z codr0 Inside information (BOI21_servers) C++14
100 / 100
 1300 ms 63780 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){
		if(k==-1) return 0;
		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&&max(UD[u].S,DU[v].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&&DU[v].S<=x0.time) {
					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
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 65 ms 37220 KB Output is correct
2 Correct 106 ms 39268 KB Output is correct
3 Correct 77 ms 38128 KB Output is correct
4 Correct 109 ms 39364 KB Output is correct
5 Correct 111 ms 39268 KB Output is correct
6 Correct 79 ms 39308 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 65 ms 37220 KB Output is correct
2 Correct 106 ms 39268 KB Output is correct
3 Correct 77 ms 38128 KB Output is correct
4 Correct 109 ms 39364 KB Output is correct
5 Correct 111 ms 39268 KB Output is correct
6 Correct 79 ms 39308 KB Output is correct
7 Correct 67 ms 37372 KB Output is correct
8 Correct 121 ms 39264 KB Output is correct
9 Correct 75 ms 37288 KB Output is correct
10 Correct 121 ms 39392 KB Output is correct
11 Correct 140 ms 39176 KB Output is correct
12 Correct 70 ms 37716 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 57 ms 37340 KB Output is correct
2 Correct 298 ms 56236 KB Output is correct
3 Correct 276 ms 56220 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 57 ms 37340 KB Output is correct
2 Correct 298 ms 56236 KB Output is correct
3 Correct 276 ms 56220 KB Output is correct
4 Correct 68 ms 36796 KB Output is correct
5 Correct 265 ms 58404 KB Output is correct
6 Correct 192 ms 56196 KB Output is correct
7 Correct 193 ms 56400 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 37224 KB Output is correct
2 Correct 923 ms 59828 KB Output is correct
3 Correct 928 ms 59972 KB Output is correct
4 Correct 532 ms 63680 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 37224 KB Output is correct
2 Correct 923 ms 59828 KB Output is correct
3 Correct 928 ms 59972 KB Output is correct
4 Correct 532 ms 63680 KB Output is correct
5 Correct 66 ms 37388 KB Output is correct
6 Correct 956 ms 59460 KB Output is correct
7 Correct 571 ms 62948 KB Output is correct
8 Correct 890 ms 58904 KB Output is correct
9 Correct 953 ms 58900 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 37220 KB Output is correct
2 Correct 485 ms 53832 KB Output is correct
3 Correct 616 ms 50156 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 37220 KB Output is correct
2 Correct 485 ms 53832 KB Output is correct
3 Correct 616 ms 50156 KB Output is correct
4 Correct 71 ms 37388 KB Output is correct
5 Correct 525 ms 53540 KB Output is correct
6 Correct 661 ms 49760 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 65 ms 37236 KB Output is correct
2 Correct 908 ms 59888 KB Output is correct
3 Correct 921 ms 59876 KB Output is correct
4 Correct 519 ms 63780 KB Output is correct
5 Correct 87 ms 37996 KB Output is correct
6 Correct 484 ms 53964 KB Output is correct
7 Correct 639 ms 50204 KB Output is correct
8 Correct 710 ms 50588 KB Output is correct
9 Correct 744 ms 51568 KB Output is correct
10 Correct 963 ms 55724 KB Output is correct
11 Correct 945 ms 55204 KB Output is correct

Subtask #10
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 65 ms 37236 KB Output is correct
2 Correct 908 ms 59888 KB Output is correct
3 Correct 921 ms 59876 KB Output is correct
4 Correct 519 ms 63780 KB Output is correct
5 Correct 87 ms 37996 KB Output is correct
6 Correct 484 ms 53964 KB Output is correct
7 Correct 639 ms 50204 KB Output is correct
8 Correct 710 ms 50588 KB Output is correct
9 Correct 744 ms 51568 KB Output is correct
10 Correct 963 ms 55724 KB Output is correct
11 Correct 945 ms 55204 KB Output is correct
12 Correct 65 ms 37348 KB Output is correct
13 Correct 900 ms 59384 KB Output is correct
14 Correct 558 ms 62848 KB Output is correct
15 Correct 902 ms 59028 KB Output is correct
16 Correct 915 ms 58940 KB Output is correct
17 Correct 70 ms 37360 KB Output is correct
18 Correct 538 ms 53648 KB Output is correct
19 Correct 676 ms 49812 KB Output is correct
20 Correct 766 ms 50612 KB Output is correct
21 Correct 762 ms 51080 KB Output is correct
22 Correct 977 ms 54860 KB Output is correct
23 Correct 1196 ms 55916 KB Output is correct
24 Correct 1154 ms 57528 KB Output is correct

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 60 ms 37216 KB Output is correct
2 Correct 91 ms 39284 KB Output is correct
3 Correct 81 ms 38140 KB Output is correct
4 Correct 109 ms 39324 KB Output is correct
5 Correct 108 ms 39196 KB Output is correct
6 Correct 69 ms 39328 KB Output is correct
7 Correct 61 ms 38020 KB Output is correct
8 Correct 261 ms 58900 KB Output is correct
9 Correct 320 ms 58904 KB Output is correct
10 Correct 65 ms 37988 KB Output is correct
11 Correct 1012 ms 59780 KB Output is correct
12 Correct 931 ms 59880 KB Output is correct
13 Correct 568 ms 63732 KB Output is correct
14 Correct 64 ms 38008 KB Output is correct
15 Correct 498 ms 53912 KB Output is correct
16 Correct 671 ms 50220 KB Output is correct
17 Correct 802 ms 50572 KB Output is correct
18 Correct 747 ms 51544 KB Output is correct
19 Correct 1047 ms 55640 KB Output is correct
20 Correct 975 ms 55252 KB Output is correct
21 Correct 345 ms 58720 KB Output is correct
22 Correct 327 ms 55684 KB Output is correct
23 Correct 544 ms 52036 KB Output is correct
24 Correct 550 ms 52056 KB Output is correct
25 Correct 950 ms 63316 KB Output is correct
26 Correct 580 ms 50756 KB Output is correct
27 Correct 531 ms 51960 KB Output is correct

Subtask #12
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 60 ms 37216 KB Output is correct
2 Correct 91 ms 39284 KB Output is correct
3 Correct 81 ms 38140 KB Output is correct
4 Correct 109 ms 39324 KB Output is correct
5 Correct 108 ms 39196 KB Output is correct
6 Correct 69 ms 39328 KB Output is correct
7 Correct 61 ms 38020 KB Output is correct
8 Correct 261 ms 58900 KB Output is correct
9 Correct 320 ms 58904 KB Output is correct
10 Correct 65 ms 37988 KB Output is correct
11 Correct 1012 ms 59780 KB Output is correct
12 Correct 931 ms 59880 KB Output is correct
13 Correct 568 ms 63732 KB Output is correct
14 Correct 64 ms 38008 KB Output is correct
15 Correct 498 ms 53912 KB Output is correct
16 Correct 671 ms 50220 KB Output is correct
17 Correct 802 ms 50572 KB Output is correct
18 Correct 747 ms 51544 KB Output is correct
19 Correct 1047 ms 55640 KB Output is correct
20 Correct 975 ms 55252 KB Output is correct
21 Correct 345 ms 58720 KB Output is correct
22 Correct 327 ms 55684 KB Output is correct
23 Correct 544 ms 52036 KB Output is correct
24 Correct 550 ms 52056 KB Output is correct
25 Correct 950 ms 63316 KB Output is correct
26 Correct 580 ms 50756 KB Output is correct
27 Correct 531 ms 51960 KB Output is correct
28 Correct 78 ms 37464 KB Output is correct
29 Correct 105 ms 39308 KB Output is correct
30 Correct 76 ms 37308 KB Output is correct
31 Correct 136 ms 39468 KB Output is correct
32 Correct 129 ms 39152 KB Output is correct
33 Correct 68 ms 37656 KB Output is correct
34 Correct 65 ms 37512 KB Output is correct
35 Correct 307 ms 58500 KB Output is correct
36 Correct 178 ms 56280 KB Output is correct
37 Correct 198 ms 56500 KB Output is correct
38 Correct 69 ms 37392 KB Output is correct
39 Correct 955 ms 59316 KB Output is correct
40 Correct 595 ms 62960 KB Output is correct
41 Correct 952 ms 58972 KB Output is correct
42 Correct 951 ms 59048 KB Output is correct
43 Correct 68 ms 37360 KB Output is correct
44 Correct 591 ms 53512 KB Output is correct
45 Correct 693 ms 49960 KB Output is correct
46 Correct 800 ms 50584 KB Output is correct
47 Correct 843 ms 51120 KB Output is correct
48 Correct 1105 ms 54828 KB Output is correct
49 Correct 1300 ms 55836 KB Output is correct
50 Correct 1133 ms 57524 KB Output is correct
51 Correct 231 ms 57444 KB Output is correct
52 Correct 203 ms 58536 KB Output is correct
53 Correct 192 ms 56912 KB Output is correct
54 Correct 215 ms 57468 KB Output is correct
55 Correct 210 ms 53316 KB Output is correct
56 Correct 502 ms 51224 KB Output is correct
57 Correct 724 ms 61528 KB Output is correct
58 Correct 855 ms 49636 KB Output is correct
59 Correct 552 ms 51920 KB Output is correct