oj.uz

Submission #488873

# Submission time Handle Problem Language Result Execution time Memory
488873 2021-11-20T17:40:54 Z CSQ31 Inside information (BOI21_servers) C++17
50 / 100
 244 ms 34832 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 p[MAXN];
int find(int x){
	if(x==p[x])return x;
	else return p[x] = find(p[x]);
}
bool unite(int a,int b){
	a = find(a);
	b = find(b);
	if(a==b)return 0;
	p[a] = b;
	return 1;
}
int main()
{
	owo
	cin>>n>>k;
	int cnt = 0;
	for(int i=1;i<=n;i++)p[i] = i;
	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],++cnt});
			adj[d[i]].pb({a[i],cnt});
		}
	}
	dfs(1,0,0);
	for(int i=0;i<n+k-1;i++){
		if(c[i] == 'S')unite(a[i],d[i]);
		else if(c[i]=='C'){
			cout<<42<<'\n';
			continue;
		}
		else{
			int v = a[i];
			int u = d[i];
			if(find(v) != find(u)){
				cout<<"no"<<'\n';
				continue;
			}
			int m = lca(v,u);
			bool ok=1;
			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 23 ms 6468 KB Output is correct
2 Correct 30 ms 8492 KB Output is correct
3 Correct 36 ms 8540 KB Output is correct
4 Correct 29 ms 8512 KB Output is correct
5 Correct 36 ms 8744 KB Output is correct
6 Correct 39 ms 8516 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 23 ms 6468 KB Output is correct
2 Correct 30 ms 8492 KB Output is correct
3 Correct 36 ms 8540 KB Output is correct
4 Correct 29 ms 8512 KB Output is correct
5 Correct 36 ms 8744 KB Output is correct
6 Correct 39 ms 8516 KB Output is correct
7 Incorrect 24 ms 7388 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 24 ms 6636 KB Output is correct
2 Correct 164 ms 23132 KB Output is correct
3 Correct 171 ms 24516 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 24 ms 6636 KB Output is correct
2 Correct 164 ms 23132 KB Output is correct
3 Correct 171 ms 24516 KB Output is correct
4 Incorrect 24 ms 7424 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 23 ms 6484 KB Output is correct
2 Correct 107 ms 33140 KB Output is correct
3 Correct 119 ms 33208 KB Output is correct
4 Correct 101 ms 34820 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 6484 KB Output is correct
2 Correct 107 ms 33140 KB Output is correct
3 Correct 119 ms 33208 KB Output is correct
4 Correct 101 ms 34820 KB Output is correct
5 Incorrect 23 ms 7464 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 25 ms 6568 KB Output is correct
2 Correct 126 ms 25196 KB Output is correct
3 Correct 121 ms 25668 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 6568 KB Output is correct
2 Correct 126 ms 25196 KB Output is correct
3 Correct 121 ms 25668 KB Output is correct
4 Incorrect 24 ms 7364 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 22 ms 6476 KB Output is correct
2 Correct 108 ms 33148 KB Output is correct
3 Correct 126 ms 33168 KB Output is correct
4 Correct 101 ms 34832 KB Output is correct
5 Correct 24 ms 7544 KB Output is correct
6 Correct 121 ms 26384 KB Output is correct
7 Correct 125 ms 26952 KB Output is correct
8 Correct 192 ms 27396 KB Output is correct
9 Correct 153 ms 27252 KB Output is correct
10 Correct 160 ms 31764 KB Output is correct
11 Correct 244 ms 31104 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 22 ms 6476 KB Output is correct
2 Correct 108 ms 33148 KB Output is correct
3 Correct 126 ms 33168 KB Output is correct
4 Correct 101 ms 34832 KB Output is correct
5 Correct 24 ms 7544 KB Output is correct
6 Correct 121 ms 26384 KB Output is correct
7 Correct 125 ms 26952 KB Output is correct
8 Correct 192 ms 27396 KB Output is correct
9 Correct 153 ms 27252 KB Output is correct
10 Correct 160 ms 31764 KB Output is correct
11 Correct 244 ms 31104 KB Output is correct
12 Incorrect 23 ms 7376 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 23 ms 6532 KB Output is correct
2 Correct 31 ms 8436 KB Output is correct
3 Correct 34 ms 8448 KB Output is correct
4 Correct 30 ms 8508 KB Output is correct
5 Correct 36 ms 8772 KB Output is correct
6 Correct 34 ms 8516 KB Output is correct
7 Correct 24 ms 7492 KB Output is correct
8 Correct 160 ms 25956 KB Output is correct
9 Correct 162 ms 25080 KB Output is correct
10 Correct 23 ms 7464 KB Output is correct
11 Correct 114 ms 33556 KB Output is correct
12 Correct 107 ms 33620 KB Output is correct
13 Correct 103 ms 33616 KB Output is correct
14 Correct 24 ms 7364 KB Output is correct
15 Correct 130 ms 26328 KB Output is correct
16 Correct 117 ms 26980 KB Output is correct
17 Correct 192 ms 27212 KB Output is correct
18 Correct 153 ms 27208 KB Output is correct
19 Correct 168 ms 31744 KB Output is correct
20 Correct 226 ms 31176 KB Output is correct
21 Correct 161 ms 26420 KB Output is correct
22 Correct 167 ms 26480 KB Output is correct
23 Correct 171 ms 26832 KB Output is correct
24 Correct 162 ms 26920 KB Output is correct
25 Correct 157 ms 28652 KB Output is correct
26 Correct 136 ms 26396 KB Output is correct
27 Correct 140 ms 26340 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 23 ms 6532 KB Output is correct
2 Correct 31 ms 8436 KB Output is correct
3 Correct 34 ms 8448 KB Output is correct
4 Correct 30 ms 8508 KB Output is correct
5 Correct 36 ms 8772 KB Output is correct
6 Correct 34 ms 8516 KB Output is correct
7 Correct 24 ms 7492 KB Output is correct
8 Correct 160 ms 25956 KB Output is correct
9 Correct 162 ms 25080 KB Output is correct
10 Correct 23 ms 7464 KB Output is correct
11 Correct 114 ms 33556 KB Output is correct
12 Correct 107 ms 33620 KB Output is correct
13 Correct 103 ms 33616 KB Output is correct
14 Correct 24 ms 7364 KB Output is correct
15 Correct 130 ms 26328 KB Output is correct
16 Correct 117 ms 26980 KB Output is correct
17 Correct 192 ms 27212 KB Output is correct
18 Correct 153 ms 27208 KB Output is correct
19 Correct 168 ms 31744 KB Output is correct
20 Correct 226 ms 31176 KB Output is correct
21 Correct 161 ms 26420 KB Output is correct
22 Correct 167 ms 26480 KB Output is correct
23 Correct 171 ms 26832 KB Output is correct
24 Correct 162 ms 26920 KB Output is correct
25 Correct 157 ms 28652 KB Output is correct
26 Correct 136 ms 26396 KB Output is correct
27 Correct 140 ms 26340 KB Output is correct
28 Incorrect 23 ms 7360 KB Extra information in the output file
29 Halted 0 ms 0 KB -