oj.uz

답안 #488756

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
488756 2021-11-20T11:19:04 Z CSQ31 Inside information (BOI21_servers) C++17
15 / 100
 3500 ms 35976 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];
int dep[MAXN],val[MAXN],par[18][MAXN];
bool ic[18][MAXN],dc[18][MAXN]; //increaisng path and decreasing path


char c[250000];
int a[250000],d[250000];
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

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 6604 KB Output is correct
2 Correct 30 ms 7044 KB Output is correct
3 Correct 38 ms 7208 KB Output is correct
4 Correct 31 ms 7244 KB Output is correct
5 Correct 396 ms 7360 KB Output is correct
6 Correct 35 ms 7108 KB Output is correct

Subtask #2
0 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 6604 KB Output is correct
2 Correct 30 ms 7044 KB Output is correct
3 Correct 38 ms 7208 KB Output is correct
4 Correct 31 ms 7244 KB Output is correct
5 Correct 396 ms 7360 KB Output is correct
6 Correct 35 ms 7108 KB Output is correct
7 Incorrect 24 ms 6476 KB Extra information in the output file
8 Halted 0 ms 0 KB -

Subtask #3
2.5 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 6520 KB Output is correct
2 Correct 176 ms 22756 KB Output is correct
3 Correct 157 ms 25228 KB Output is correct

Subtask #4
0 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 6520 KB Output is correct
2 Correct 176 ms 22756 KB Output is correct
3 Correct 157 ms 25228 KB Output is correct
4 Incorrect 26 ms 7440 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 41 ms 6536 KB Output is correct
2 Correct 142 ms 31456 KB Output is correct
3 Correct 111 ms 31548 KB Output is correct
4 Execution timed out 3598 ms 34292 KB Time limit exceeded

Subtask #6
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 41 ms 6536 KB Output is correct
2 Correct 142 ms 31456 KB Output is correct
3 Correct 111 ms 31548 KB Output is correct
4 Execution timed out 3598 ms 34292 KB Time limit exceeded

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 6540 KB Output is correct
2 Correct 168 ms 22916 KB Output is correct
3 Correct 115 ms 26644 KB Output is correct

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 6540 KB Output is correct
2 Correct 168 ms 22916 KB Output is correct
3 Correct 115 ms 26644 KB Output is correct
4 Incorrect 25 ms 7376 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #9
0 / 12.5

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 6492 KB Output is correct
2 Correct 116 ms 31476 KB Output is correct
3 Correct 107 ms 31544 KB Output is correct
4 Execution timed out 3589 ms 34356 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 6492 KB Output is correct
2 Correct 116 ms 31476 KB Output is correct
3 Correct 107 ms 31544 KB Output is correct
4 Execution timed out 3589 ms 34356 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 6564 KB Output is correct
2 Correct 31 ms 7020 KB Output is correct
3 Correct 41 ms 7148 KB Output is correct
4 Correct 30 ms 7132 KB Output is correct
5 Correct 395 ms 7532 KB Output is correct
6 Correct 36 ms 7076 KB Output is correct
7 Correct 24 ms 6612 KB Output is correct
8 Correct 170 ms 22760 KB Output is correct
9 Correct 173 ms 25200 KB Output is correct
10 Correct 26 ms 7456 KB Output is correct
11 Correct 126 ms 34836 KB Output is correct
12 Correct 154 ms 34744 KB Output is correct
13 Execution timed out 3575 ms 35976 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 6564 KB Output is correct
2 Correct 31 ms 7020 KB Output is correct
3 Correct 41 ms 7148 KB Output is correct
4 Correct 30 ms 7132 KB Output is correct
5 Correct 395 ms 7532 KB Output is correct
6 Correct 36 ms 7076 KB Output is correct
7 Correct 24 ms 6612 KB Output is correct
8 Correct 170 ms 22760 KB Output is correct
9 Correct 173 ms 25200 KB Output is correct
10 Correct 26 ms 7456 KB Output is correct
11 Correct 126 ms 34836 KB Output is correct
12 Correct 154 ms 34744 KB Output is correct
13 Execution timed out 3575 ms 35976 KB Time limit exceeded
14 Halted 0 ms 0 KB -