oj.uz

답안 #581217

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
581217 2022-06-22T11:41:59 Z WongChun1234 Inside information (BOI21_servers) C++14
2.5 / 100
 414 ms 24572 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()&&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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 60 ms 4604 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Incorrect 60 ms 4604 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
2.5 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 81 ms 4684 KB Output is correct
2 Correct 414 ms 24440 KB Output is correct
3 Correct 401 ms 24572 KB Output is correct

Subtask #4
0 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 81 ms 4684 KB Output is correct
2 Correct 414 ms 24440 KB Output is correct
3 Correct 401 ms 24572 KB Output is correct
4 Incorrect 76 ms 5580 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 58 ms 4604 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 58 ms 4604 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 63 ms 4556 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 63 ms 4556 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 12.5

# 결과 실행 시간 메모리 Grader output
1 Incorrect 56 ms 4648 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# 결과 실행 시간 메모리 Grader output
1 Incorrect 56 ms 4648 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# 결과 실행 시간 메모리 Grader output
1 Incorrect 65 ms 4540 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# 결과 실행 시간 메모리 Grader output
1 Incorrect 65 ms 4540 KB Output isn't correct
2 Halted 0 ms 0 KB -