제출 #226197

#제출 시각아이디문제언어결과실행 시간메모리
226197DavidDamian늑대인간 (IOI18_werewolf)C++11
15 / 100
537 ms76632 KiB
#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) { for(int i=0;i<log_n;i++){ ancestor[i][root]=n; ancestor[i][n]=n; minPath[i][root]=INT_MAX; maxPath[i][root]=-INT_MAX; minPath[i][n]=INT_MAX; maxPath[i][n]=-INT_MAX; } dfs(root,-1,0); for(int i=1;i<=log_n;i++){ for(int u=0;u<n;u++){ ancestor[i][u]=ancestor[i-1][ancestor[i-1][u]]; minPath[i][u]=(ancestor[i][u]!=n)? min(minPath[i-1][u],minPath[i-1][ancestor[i-1][u]]) : INT_MAX; maxPath[i][u]=(ancestor[i][u]!=n)? 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 int change=1; //You can change your form if(lv[T]>lv[S]){ swap(T,S); form=1; //Wolf } while(S!=T){ int d=lv[S]-lv[T]; bool moved=false; for(int i=log_n;i>=0;i--){ if(d & (1<<i)){ if(form==0){ if(minPath[i][S]>=L){ S=ancestor[i][S]; moved=true; } } else{ if(maxPath[i][S]<=R){ S=ancestor[i][S]; moved=true; } } } } if(moved==false){ if(change==1 && L<=S && S<=R){ form=(form+1)%2; //Change form change=0; //You cannot do another change } else return 0; } } return 1; } 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].push_back(b); adjList[b].push_back(a); } int root; for(int i=0;i<m;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],T[i],L[i],R[i])); } 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:145:18: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
     buildAncestor(root);
     ~~~~~~~~~~~~~^~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...