이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "werewolf.h"
#include<bits/stdc++.h>
using namespace std;
///Subtask 3
///Record ancestors
///Move through the graph greedily
vector<int> adjList[200005];
int destiny;
int color[6005];
int c=0;
int n;
int l,r;
int lv[200005];
int ancestor[20][200005];
int minPath[20][200005]; //Min and max in path
int maxPath[20][200005];
void dfs(int u,int e,int depth)
{
lv[u]=depth;
for(int v: adjList[u]){
if(v==e) continue;
ancestor[0][v]=u;
minPath[0][v]=u;
maxPath[0][v]=u;
dfs(v,u,depth+1);
}
}
int dfsVisit(int u)
{
if(u==destiny) return 1;
int ans=0;
color[u]=c;
for(int v: adjList[u]){
if(ans==1) break;
if(color[v]!=c){
if(v!=u+n){
if(v<n && v>=l)
ans=dfsVisit(v);
if(v>=n && v<=r+n)
ans=dfsVisit(v);
}
if(v==u+n && l<=u && u<=r)
ans=dfsVisit(v);
}
}
return ans;
}
#define log_n 18
void buildAncestor(int root)
{
minPath[0][root]=INT_MAX;
maxPath[0][root]=-INT_MAX;
dfs(root,0,0);
for(int i=1;i<=log_n;i++){
for(int u=1;u<=n;u++){
ancestor[i][u]=ancestor[i-1][ancestor[i-1][u]];
minPath[i][u]=(ancestor[i][u]!=0)? min(minPath[i-1][u],minPath[i-1][ancestor[i-1][u]]) : INT_MAX;
maxPath[i][u]=(ancestor[i][u]!=0)? max(maxPath[i-1][u],maxPath[i-1][ancestor[i-1][u]]) : -INT_MAX;
}
}
}
#define debug(x) cout<<#x<<" = "<<x<<endl
int possible(int S,int T,int L,int R)
{
int form=0; //Human
if(lv[T]>lv[S]){
swap(T,S);
form=1; //Wolf
}
int u=S;
for(int b=log_n;b>=0;b--){
if(ancestor[b][u]==0) continue;
if(form==0){
if(minPath[b][u]>=L)
u=ancestor[b][u];
}
else{
if(maxPath[b][u]<=R)
u=ancestor[b][u];
}
}
if(lv[ ancestor[0][u] ]<=lv[T]) return 1;
if(L<=u && u<=R) form=(form+1)%2;
for(int b=log_n;b>=0;b--){
if(ancestor[b][u]==0) continue;
if(form==0){
if(minPath[b][u]>=L)
u=ancestor[b][u];
}
else{
if(maxPath[b][u]<=R)
u=ancestor[b][u];
}
}
if(lv[ ancestor[0][u] ]<=lv[T]) return 1;
else return 0;
}
vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> T, vector<int> L, vector<int> R) {
int m=X.size();
int Q=S.size();
n=N;
if(n<=3000){
for(int i=0;i<m;i++){
int a=X[i];
int b=Y[i];
adjList[a].push_back(b);
adjList[b].push_back(a);
adjList[a+n].push_back(b+n);
adjList[b+n].push_back(a+n);
}
for(int i=0;i<n;i++){
adjList[i].push_back(i+n);
}
vector<int> A;
for(int i=0;i<Q;i++){
c++;
destiny=T[i]+n;
l=L[i];
r=R[i];
A.push_back(dfsVisit(S[i]));
}
return A;
}
for(int i=0;i<m;i++){
int a=X[i];
int b=Y[i];
adjList[a+1].push_back(b+1);
adjList[b+1].push_back(a+1);
}
int root;
for(int i=1;i<=n;i++){
if(adjList[i].size()==1){
root=i;
break;
}
}
buildAncestor(root);
vector<int> A;
for(int i=0;i<Q;i++){
A.push_back(possible(S[i]+1,T[i]+1,L[i]+1,R[i]+1));
}
return A;
}
컴파일 시 표준 에러 (stderr) 메시지
werewolf.cpp: In function 'std::vector<int> check_validity(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
werewolf.cpp:137:18: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
buildAncestor(root);
~~~~~~~~~~~~~^~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |