Submission #488756

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
488756	2021-11-20T11:19:04 Z	CSQ31	Inside information (BOI21_servers)	C++17	15 / 100	3500 ms	35976 KB

servers

#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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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	-

Submission #488756

Compilation message