oj.uz

Submission #581220

# Submission time Handle Problem Language Result Execution time Memory
581220 2022-06-22T11:45:08 Z WongChun1234 Inside information (BOI21_servers) C++14
15 / 100
 3500 ms 30712 KB 
#include<bits/stdc++.h>
using namespace std;
const int N=120050,Q=240050;
int n,k,u[Q],v[Q],par[N],tme[N],lift[25][N],preord[N],postord[N],pt;
char ty[Q];
vector<int> adj[N],tmp;
void dfs(int u,int pp=1){
	preord[u]=pt++;
	par[u]=lift[0][u]=pp;
	for (int i=1;i<=20;i++) lift[i][u]=lift[i-1][lift[i-1][u]];
	for (auto i:adj[u]) if (i!=pp) dfs(i,u);
	postord[u]=pt;
}
bool isa(int a,int b){
	return (preord[a]<=preord[b]&&postord[a]>=postord[b]);
}
int lca(int a,int b){
	if (isa(a,b)) return a;
	if (isa(b,a)) return b;
	for (int i=20;i>=0;i--) if (!isa(lift[i][a],b)) a=lift[i][a];
	return lift[0][a];
}
int main(){
	cin>>n>>k;
	for (int i=1;i<n+k;i++){
		cin>>ty[i];
		if (ty[i]=='C') cin>>u[i];
		else if (ty[i]=='S'){
			cin>>u[i]>>v[i];
			adj[u[i]].push_back(v[i]);
			adj[v[i]].push_back(u[i]);
		}else{
			cin>>u[i]>>v[i];
		}
	}
	dfs(1);
	for (int i=1;i<n+k;i++){
		if (ty[i]=='Q'){
			//check path from v to u
			int lcaa=lca(u[i],v[i]),uu=u[i],vv=v[i];
			tmp.clear();
			while (vv!=lcaa){
				if (!tme[vv]){
					cout<<"no\n";
					goto skip;
				}
				if (par[vv]!=lcaa&&tme[par[vv]]<tme[vv]){
					cout<<"no\n";
					goto skip;
				}
				if (par[vv]!=lcaa) vv=par[vv];
				else break;
			}
			while (uu!=lcaa){
				if (!tme[uu]){
					cout<<"no\n";
					goto skip;
				}
				tmp.push_back(tme[uu]);
				if (par[uu]!=lcaa) uu=par[uu];
				else break;
			}
			for (int j=1;j<tmp.size();j++){
				if (tmp[j-1]<tmp[j]){
					cout<<"no\n";
					goto skip;
				}
			}
			if (tmp.size()&&vv!=lcaa&&tmp.back()<tme[vv]){
				cout<<"no\n";
				goto skip;
			}
			cout<<"yes\n";
		}else if (ty[i]=='S'){
			if (isa(u[i],v[i])){
				tme[v[i]]=i;
			}else tme[u[i]]=i;
		}else{
			cout<<"-1\n";
		}
		skip:;
	}
}

Compilation message

servers.cpp: In function 'int main()':
servers.cpp:63:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |    for (int j=1;j<tmp.size();j++){
      |                 ~^~~~~~~~~~~

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 67 ms 4556 KB Output is correct
2 Correct 101 ms 6476 KB Output is correct
3 Correct 97 ms 6548 KB Output is correct
4 Correct 96 ms 6568 KB Output is correct
5 Correct 299 ms 6780 KB Output is correct
6 Correct 97 ms 6604 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 67 ms 4556 KB Output is correct
2 Correct 101 ms 6476 KB Output is correct
3 Correct 97 ms 6548 KB Output is correct
4 Correct 96 ms 6568 KB Output is correct
5 Correct 299 ms 6780 KB Output is correct
6 Correct 97 ms 6604 KB Output is correct
7 Incorrect 64 ms 5436 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 66 ms 4688 KB Output is correct
2 Correct 356 ms 21524 KB Output is correct
3 Correct 339 ms 21600 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 66 ms 4688 KB Output is correct
2 Correct 356 ms 21524 KB Output is correct
3 Correct 339 ms 21600 KB Output is correct
4 Incorrect 61 ms 4684 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 59 ms 4584 KB Output is correct
2 Correct 204 ms 30712 KB Output is correct
3 Correct 197 ms 30512 KB Output is correct
4 Execution timed out 3562 ms 30468 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 4584 KB Output is correct
2 Correct 204 ms 30712 KB Output is correct
3 Correct 197 ms 30512 KB Output is correct
4 Execution timed out 3562 ms 30468 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 4592 KB Output is correct
2 Correct 295 ms 24408 KB Output is correct
3 Correct 253 ms 24520 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 4592 KB Output is correct
2 Correct 295 ms 24408 KB Output is correct
3 Correct 253 ms 24520 KB Output is correct
4 Incorrect 63 ms 5468 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 56 ms 4624 KB Output is correct
2 Correct 223 ms 30664 KB Output is correct
3 Correct 211 ms 30448 KB Output is correct
4 Execution timed out 3585 ms 30544 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 56 ms 4624 KB Output is correct
2 Correct 223 ms 30664 KB Output is correct
3 Correct 211 ms 30448 KB Output is correct
4 Execution timed out 3585 ms 30544 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 63 ms 4556 KB Output is correct
2 Correct 113 ms 6548 KB Output is correct
3 Correct 104 ms 6612 KB Output is correct
4 Correct 96 ms 6580 KB Output is correct
5 Correct 300 ms 6860 KB Output is correct
6 Correct 99 ms 6600 KB Output is correct
7 Correct 65 ms 5556 KB Output is correct
8 Correct 359 ms 24436 KB Output is correct
9 Correct 358 ms 24468 KB Output is correct
10 Correct 55 ms 5512 KB Output is correct
11 Correct 202 ms 30688 KB Output is correct
12 Correct 206 ms 30508 KB Output is correct
13 Execution timed out 3567 ms 30536 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 63 ms 4556 KB Output is correct
2 Correct 113 ms 6548 KB Output is correct
3 Correct 104 ms 6612 KB Output is correct
4 Correct 96 ms 6580 KB Output is correct
5 Correct 300 ms 6860 KB Output is correct
6 Correct 99 ms 6600 KB Output is correct
7 Correct 65 ms 5556 KB Output is correct
8 Correct 359 ms 24436 KB Output is correct
9 Correct 358 ms 24468 KB Output is correct
10 Correct 55 ms 5512 KB Output is correct
11 Correct 202 ms 30688 KB Output is correct
12 Correct 206 ms 30508 KB Output is correct
13 Execution timed out 3567 ms 30536 KB Time limit exceeded
14 Halted 0 ms 0 KB -