Submission #434022

#TimeUsernameProblemLanguageResultExecution timeMemory
434022frodakcinWerewolf (IOI18_werewolf)C++11
49 / 100
4040 ms38836 KiB
#include "werewolf.h" #include <algorithm> #include <functional> template<typename T> bool ckmax(T& a, const T& b) {return b>a?a=b,1:0;} template<typename T> bool ckmin(T& a, const T& b) {return b<a?a=b,1:0;} const int MN = 2e5+10; const int MQ = 2e5+10; int N, M, Q; std::vector<int> a[MN], ans; struct ST { public: std::vector<int> v; int S; ST(int _S): S(_S), v(_S*4, 0) {} void build(int n, int l, int r, const std::vector<int>& line) { if(r-l>1) { int m = l+(r-l)/2; build(n<<1, l, m, line); build(n<<1|1, m, r, line); v[n]=std::min(v[n<<1], v[n<<1|1]); } else v[n]=line[l]; } void build(const std::vector<int>& line) {build(1, 0, S, line);} int qryr(int n, int l, int r, int qr, int cut) //rightmost point < cut { if(v[n]>=cut) return l-1; if(r-l>1) { int m=l+(r-l)/2, f=m-1; if(m < qr) f = qryr(n<<1|1, m, r, qr, cut); if(f == m-1) return qryr(n<<1, l, m, qr, cut); return f; } return l; } int qryr(int qr, int cut) {return qryr(1, 0, S, qr, cut);} int qryl(int n, int l, int r, int ql, int cut) //leftmost point < cut { if(v[n]>=cut) return r; if(r-l>1) { int m=l+(r-l)/2, f=m; if(ql < m) f = qryl(n<<1, l, m, ql, cut); if(f == m) return qryl(n<<1|1, m, r, ql, cut); return f; } return l; } int qryl(int ql, int cut) {return qryl(1, 0, S, ql, cut);} }; std::vector<int> check_validity(int N, std::vector<int> X, std::vector<int> Y, std::vector<int> S, std::vector<int> E, std::vector<int> L, std::vector<int> R) { ::N=N; M=X.size(); Q = S.size(); ans.assign(Q, 0); for(int i=0;i<M;++i) { a[X[i]].push_back(Y[i]); a[Y[i]].push_back(X[i]); } bool is_line = M+1 == N; for(int i=0;i<N && is_line;++i) is_line &= a[i].size() <= 2; if(is_line) { int st = -1; for(int i=0;st == -1;++i) if(a[i].size() == 1) st = i; std::vector<int> line, wh(N, -1); std::vector<char> vis(N, 0); line.push_back(st); for(int i=1;i<N;++i) { int n=line.back(); vis[n]=1; for(int x:a[n]) if(!vis[x]) line.push_back(x); } for(int i=0;i<N;++i) wh[line[i]]=i; ST hu(N), ww(N); hu.build(line); for(int& x:line) x*=-1; ww.build(line); for(int i=0;i<Q;++i) { int s=wh[S[i]], e=wh[E[i]]; if(s<e) ans[i]=hu.qryl(s, L[i]) > ww.qryr(e, -R[i])+1; else ans[i]=ww.qryl(e, -R[i]) > hu.qryr(s, L[i])+1; } return ans; } for(int i=0;i<Q;++i) { std::vector<char> vh(N, 0), vw(N, 0); std::function<void(int)> dfs=[&](int n) { vh[n]=1; for(int x:a[n]) if(!vh[x] && x >= L[i]) dfs(x); }; dfs(S[i]); dfs = [&](int n) { vw[n]=1; for(int x:a[n]) if(!vw[x] && x <= R[i]) dfs(x); }; dfs(E[i]); for(int j=0;!ans[i] && j<N;++j) { //printf("%d: %d: [%d/%d]\n", i, j, vh[j], vw[j]); ans[i] |= vh[j] && vw[j]; } } return ans; }

Compilation message (stderr)

werewolf.cpp: In constructor 'ST::ST(int)':
werewolf.cpp:18:7: warning: 'ST::S' will be initialized after [-Wreorder]
   18 |   int S;
      |       ^
werewolf.cpp:17:20: warning:   'std::vector<int> ST::v' [-Wreorder]
   17 |   std::vector<int> v;
      |                    ^
werewolf.cpp:19:3: warning:   when initialized here [-Wreorder]
   19 |   ST(int _S): S(_S), v(_S*4, 0) {}
      |   ^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...