제출 #581217

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
581217		WongChun1234	Inside information (BOI21_servers)	C++14	2.50 / 100	414 ms	24572 KiB

servers

#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:;
	}
}

컴파일 시 표준 에러 (stderr) 메시지

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
• Subtask 2: 0 / 2.5
• Subtask 3: 2.5 / 2.5
• Subtask 4: 0 / 2.5
• Subtask 5: 0 / 5
• Subtask 6: 0 / 5
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 12.5
• Subtask 10: 0 / 12.5
• Subtask 11: 0 / 17.5
• Subtask 12: 0 / 17.5