oj.uz

Submission #488753

# Submission time Handle Problem Language Result Execution time Memory
488753 2021-11-20T11:17:13 Z CSQ31 Inside information (BOI21_servers) C++17
2.5 / 100
 404 ms 24772 KB 
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define owo ios_base::sync_with_stdio(0);cin.tie(0);
typedef pair<int,int> pii;
const int MAXN = 2e5;
vector<pii>adj[MAXN];
char c[MAXN];
int a[MAXN],d[MAXN],dep[MAXN],val[MAXN],par[18][MAXN];
bool ic[18][MAXN],dc[18][MAXN]; //increaisng path and decreasing path
void dfs(int v,int u){
	if(par[0][v]){
		ic[0][v] = dc[0][v] = 1;
		int last = val[v];
		for(int i=1;i<=17;i++){
			int mid = par[i-1][v];
			par[i][v] = par[i-1][mid];
			if(val[mid]){
				if(ic[i-1][v] && ic[i-1][mid] && val[mid] > last)ic[i][v] = 1;
				if(dc[i-1][v] && dc[i-1][mid] && val[mid] < last)dc[i][v] = 1;
			}
			
			last = val[mid];
		}
	}
	for(pii z:adj[v]){
		int x = z.fi;
		int w = z.se;
		if(x == u)continue;
		val[x] = w;
		dep[x] = dep[v]+1;
		par[0][x] = v;
		dfs(x,v);
	}
}
int lca(int v,int u){
	if(dep[v] < dep[u])swap(v,u);
	int d = dep[v] - dep[u];
	for(int i=0;i<=17;i++){
		if(d&(1<<i))v = par[i][v];
	}
	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
	int n,k;
	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);
	for(int i=0;i<n+k-1;i++){
		if(c[i] == 'S')unite(a[i],d[i]);
		else if(c[i]=='C')cout<<1<<'\n';
		else{
			int v = a[i];
			int u = d[i];
			if(find(v) != find(u)){
				cout<<"no"<<'\n';
				continue;
			}
			int m = lca(v,u);
			/*
			int d = dep[v] - dep[m]-1;
			bool ok = 1;
			int last = 1e9;
			for(int i=0;i<=17 && d>=0;i++){
				if(d&1){
					if(!dc[i][v] || last < val[v])ok = 0;
					v = par[i][v];
					last = val[v];
				}
				d/=2;
			} 
			if(v!=m && last < val[v])ok = 0;
			//v->lca is decreasing
			
			
			d = dep[u] - dep[m]-1;
			last = 0;
			for(int i=0;i<=17 && d>=0;i++){
				if(d&1){
					//cout<<i<<" "<<u<<" "<<ic[i][u]<<" "<<last<<" "<<val[u]<<'\n';
					if(!ic[i][u] || last > val[u])ok = 0;
					u = par[i][u];
					last = val[u];
				}
				d/=2;
			} 
			if(u!=m && last > val[u])ok = 0;
			if(v!=m && u!=m && val[v] < val[u])ok = 0;
			//u->lca is increasing
			*/
			bool ok = 1;
			int last = 1e9;

			while(v!=m){
				if(last < val[v])ok = 0;
				last = val[v];
				v = par[0][v];
			}
			int last2 = 0;
			while(u!=m){
				if(last2  > val[u])ok = 0;
				last2 = val[u];
				u = par[0][u];
			}
			if(last < last2)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 27 ms 6604 KB Output is correct
2 Correct 30 ms 7104 KB Output is correct
3 Correct 38 ms 7192 KB Output is correct
4 Correct 29 ms 7216 KB Output is correct
5 Correct 404 ms 7308 KB Output is correct
6 Correct 36 ms 7116 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 27 ms 6604 KB Output is correct
2 Correct 30 ms 7104 KB Output is correct
3 Correct 38 ms 7192 KB Output is correct
4 Correct 29 ms 7216 KB Output is correct
5 Correct 404 ms 7308 KB Output is correct
6 Correct 36 ms 7116 KB Output is correct
7 Incorrect 24 ms 6552 KB Extra information in the output file
8 Halted 0 ms 0 KB -

Subtask #3
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 25 ms 6616 KB Output is correct
2 Runtime error 56 ms 22436 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 25 ms 6616 KB Output is correct
2 Runtime error 56 ms 22436 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 6628 KB Output is correct
2 Runtime error 66 ms 21900 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 6628 KB Output is correct
2 Runtime error 66 ms 21900 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 6468 KB Output is correct
2 Runtime error 90 ms 24772 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 6468 KB Output is correct
2 Runtime error 90 ms 24772 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #9
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 27 ms 6532 KB Output is correct
2 Runtime error 67 ms 21848 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 27 ms 6532 KB Output is correct
2 Runtime error 67 ms 21848 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 26 ms 6588 KB Output is correct
2 Correct 30 ms 7064 KB Output is correct
3 Correct 49 ms 7096 KB Output is correct
4 Correct 29 ms 7132 KB Output is correct
5 Correct 394 ms 7368 KB Output is correct
6 Correct 47 ms 7148 KB Output is correct
7 Correct 25 ms 6600 KB Output is correct
8 Runtime error 49 ms 22400 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 26 ms 6588 KB Output is correct
2 Correct 30 ms 7064 KB Output is correct
3 Correct 49 ms 7096 KB Output is correct
4 Correct 29 ms 7132 KB Output is correct
5 Correct 394 ms 7368 KB Output is correct
6 Correct 47 ms 7148 KB Output is correct
7 Correct 25 ms 6600 KB Output is correct
8 Runtime error 49 ms 22400 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -