oj.uz

Submission #489265

# Submission time Handle Problem Language Result Execution time Memory
489265 2021-11-21T19:54:13 Z CSQ31 Inside information (BOI21_servers) C++17
50 / 100
 226 ms 33488 KB 
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define sz(a) (int)(a.size())
#define owo ios_base::sync_with_stdio(0);cin.tie(0);
typedef pair<int,int> pii;
const int MAXN = 2e5;
vector<pii>adj[MAXN];
int dep[MAXN],par[18][MAXN],asc[MAXN],dsc[MAXN],val[MAXN],n,k;
char c[250000];
int a[250000],d[250000];
void dfs(int v,int u,int ww){
	for(int i=1;i<=17;i++)par[i][v] = par[i-1][par[i-1][v]];
	for(pii z:adj[v]){
		int x = z.fi;
		int w = z.se;
		if(x == u)continue;
		val[x] = w;
		asc[x] = dsc[x] = dep[v];
		if(w > ww || v==1)asc[x] = asc[v];	
		if(w < ww || v==1)dsc[x] = dsc[v];
		
		dep[x] = dep[v]+1;
		par[0][x] = v;
		dfs(x,v,w);
	}
}
int jump(int v,int d){
	for(int i=0;i<=17 && d;i++){
		if(d&1)v=par[i][v];
		d/=2;
	}
	return v;
}
int lca(int v,int u){
	if(dep[v] < dep[u])swap(v,u);
	v = jump(v,dep[v] - dep[u]);
	
	if(v==u)return v;
	for(int i=17;i>=0;i--){
		if(par[i][v] != par[i][u]){
			v = par[i][v];
			u = par[i][u];
		}
	}
	return par[0][v];
}
int main()
{
	owo
	cin>>n>>k;
	for(int i=0;i<n+k-1;i++){
		cin>>c[i]>>a[i];
		if(c[i]!='C')cin>>d[i];
		if(c[i] == 'S'){
			adj[a[i]].pb({d[i],i});
			adj[d[i]].pb({a[i],i});
		}
	}
	dfs(1,0,0);
	for(int i=0;i<n+k-1;i++){
		if(c[i]=='C'){
			cout<<42<<'\n';
			continue;
		}
		else if(c[i]=='Q'){ //this solves for Q queries now for C queries
			int v = a[i];
			int u = d[i];

			int m = lca(v,u),last = -1e9;
			if(v!=m)last = val[v];
			else if(u!=m)last = val[jump(u,dep[u]-dep[m]-1)];
			bool ok= (last<=i);
			
			if(asc[v] > dep[m] || dsc[u] > dep[m])ok = 0;
			if(v!=m && u!= m){
				v = jump(v,dep[v]-dep[m]-1);
				u = jump(u,dep[u]-dep[m]-1);
				if(val[u] > val[v])ok = 0;
			}
			if(ok)cout<<"yes"<<'\n';
			else cout<<"no"<<'\n';
		}
		
	}
}

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 28 ms 7068 KB Output is correct
2 Correct 43 ms 7896 KB Output is correct
3 Correct 33 ms 7956 KB Output is correct
4 Correct 50 ms 7908 KB Output is correct
5 Correct 38 ms 8168 KB Output is correct
6 Correct 32 ms 7620 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 28 ms 7068 KB Output is correct
2 Correct 43 ms 7896 KB Output is correct
3 Correct 33 ms 7956 KB Output is correct
4 Correct 50 ms 7908 KB Output is correct
5 Correct 38 ms 8168 KB Output is correct
6 Correct 32 ms 7620 KB Output is correct
7 Incorrect 28 ms 7044 KB Extra information in the output file
8 Halted 0 ms 0 KB -

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 25 ms 6684 KB Output is correct
2 Correct 148 ms 23672 KB Output is correct
3 Correct 135 ms 24884 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 25 ms 6684 KB Output is correct
2 Correct 148 ms 23672 KB Output is correct
3 Correct 135 ms 24884 KB Output is correct
4 Incorrect 26 ms 7328 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 6524 KB Output is correct
2 Correct 101 ms 31500 KB Output is correct
3 Correct 106 ms 31500 KB Output is correct
4 Correct 104 ms 32424 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 6524 KB Output is correct
2 Correct 101 ms 31500 KB Output is correct
3 Correct 106 ms 31500 KB Output is correct
4 Correct 104 ms 32424 KB Output is correct
5 Incorrect 27 ms 7372 KB Extra information in the output file
6 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 6544 KB Output is correct
2 Correct 113 ms 24632 KB Output is correct
3 Correct 107 ms 25436 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 6544 KB Output is correct
2 Correct 113 ms 24632 KB Output is correct
3 Correct 107 ms 25436 KB Output is correct
4 Incorrect 28 ms 7428 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 27 ms 6524 KB Output is correct
2 Correct 109 ms 31592 KB Output is correct
3 Correct 96 ms 31576 KB Output is correct
4 Correct 107 ms 32328 KB Output is correct
5 Correct 27 ms 7372 KB Output is correct
6 Correct 116 ms 24624 KB Output is correct
7 Correct 114 ms 25092 KB Output is correct
8 Correct 185 ms 25540 KB Output is correct
9 Correct 146 ms 25540 KB Output is correct
10 Correct 154 ms 29952 KB Output is correct
11 Correct 226 ms 29484 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 27 ms 6524 KB Output is correct
2 Correct 109 ms 31592 KB Output is correct
3 Correct 96 ms 31576 KB Output is correct
4 Correct 107 ms 32328 KB Output is correct
5 Correct 27 ms 7372 KB Output is correct
6 Correct 116 ms 24624 KB Output is correct
7 Correct 114 ms 25092 KB Output is correct
8 Correct 185 ms 25540 KB Output is correct
9 Correct 146 ms 25540 KB Output is correct
10 Correct 154 ms 29952 KB Output is correct
11 Correct 226 ms 29484 KB Output is correct
12 Incorrect 26 ms 7416 KB Extra information in the output file
13 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 28 ms 6460 KB Output is correct
2 Correct 41 ms 7452 KB Output is correct
3 Correct 36 ms 7424 KB Output is correct
4 Correct 50 ms 7524 KB Output is correct
5 Correct 38 ms 7680 KB Output is correct
6 Correct 32 ms 7520 KB Output is correct
7 Correct 26 ms 6852 KB Output is correct
8 Correct 134 ms 23864 KB Output is correct
9 Correct 135 ms 24536 KB Output is correct
10 Correct 29 ms 7436 KB Output is correct
11 Correct 99 ms 33488 KB Output is correct
12 Correct 98 ms 33464 KB Output is correct
13 Correct 106 ms 33396 KB Output is correct
14 Correct 27 ms 7372 KB Output is correct
15 Correct 113 ms 24736 KB Output is correct
16 Correct 109 ms 25172 KB Output is correct
17 Correct 178 ms 25560 KB Output is correct
18 Correct 148 ms 25628 KB Output is correct
19 Correct 164 ms 30052 KB Output is correct
20 Correct 211 ms 29252 KB Output is correct
21 Correct 135 ms 24608 KB Output is correct
22 Correct 140 ms 24692 KB Output is correct
23 Correct 148 ms 25116 KB Output is correct
24 Correct 145 ms 25140 KB Output is correct
25 Correct 144 ms 26812 KB Output is correct
26 Correct 121 ms 24524 KB Output is correct
27 Correct 117 ms 24516 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 28 ms 6460 KB Output is correct
2 Correct 41 ms 7452 KB Output is correct
3 Correct 36 ms 7424 KB Output is correct
4 Correct 50 ms 7524 KB Output is correct
5 Correct 38 ms 7680 KB Output is correct
6 Correct 32 ms 7520 KB Output is correct
7 Correct 26 ms 6852 KB Output is correct
8 Correct 134 ms 23864 KB Output is correct
9 Correct 135 ms 24536 KB Output is correct
10 Correct 29 ms 7436 KB Output is correct
11 Correct 99 ms 33488 KB Output is correct
12 Correct 98 ms 33464 KB Output is correct
13 Correct 106 ms 33396 KB Output is correct
14 Correct 27 ms 7372 KB Output is correct
15 Correct 113 ms 24736 KB Output is correct
16 Correct 109 ms 25172 KB Output is correct
17 Correct 178 ms 25560 KB Output is correct
18 Correct 148 ms 25628 KB Output is correct
19 Correct 164 ms 30052 KB Output is correct
20 Correct 211 ms 29252 KB Output is correct
21 Correct 135 ms 24608 KB Output is correct
22 Correct 140 ms 24692 KB Output is correct
23 Correct 148 ms 25116 KB Output is correct
24 Correct 145 ms 25140 KB Output is correct
25 Correct 144 ms 26812 KB Output is correct
26 Correct 121 ms 24524 KB Output is correct
27 Correct 117 ms 24516 KB Output is correct
28 Incorrect 30 ms 7344 KB Extra information in the output file
29 Halted 0 ms 0 KB -