oj.uz

Submission #581215

# Submission time Handle Problem Language Result Execution time Memory
581215 2022-06-22T11:39:07 Z WongChun1234 Inside information (BOI21_servers) C++14
0 / 100
 65 ms 9440 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.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
0 / 2.5

# Verdict Execution time Memory Grader output
1 Runtime error 56 ms 9388 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Runtime error 56 ms 9388 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 2.5

# Verdict Execution time Memory Grader output
1 Runtime error 56 ms 9428 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Runtime error 56 ms 9428 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 52 ms 9440 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 52 ms 9440 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 65 ms 9412 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 65 ms 9412 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #9
0 / 12.5

# Verdict Execution time Memory Grader output
1 Runtime error 59 ms 9388 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Runtime error 59 ms 9388 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Runtime error 62 ms 9324 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Runtime error 62 ms 9324 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -