Submission #580801

#TimeUsernameProblemLanguageResultExecution timeMemory
580801definitelynotmeeWerewolf (IOI18_werewolf)C++17
15 / 100
4099 ms62072 KiB
#include "werewolf.h" #include<bits/stdc++.h> using namespace std; #define ff first #define ss second #define all(x) x.begin(), x.end() using ll = long long; using pii = pair<int,int>; using pll = pair<ll,ll>; template<typename T> using matrix = vector<vector<T>>; 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) { matrix<int> g(N); for(int i = 0; i < X.size(); i++){ g[X[i]].push_back(Y[i]); g[Y[i]].push_back(X[i]); } int Q = S.size(); std::vector<int> ans(Q); if(N <= 3000){ vector<int> c1(N), c2(N); auto dfs =[&](int id, int l, int r,vector<int>&check, auto dfs)->void{ check[id] = 1; for(int i : g[id]){ if(check[i] || i > r || i < l) continue; dfs(i,l,r,check,dfs); } }; for(int i = 0; i < Q; i++){ fill(all(c1),0); fill(all(c2),0); dfs(S[i],L[i],N,c1,dfs); dfs(E[i],0,R[i],c2,dfs); for(int j = 0; j < N; j++){ ans[i]|=c1[j]&&c2[j]; } } } else { vector<int> v; v.reserve(N); auto dfs =[&](int id, int last, auto dfs)->void{ for(int i : g[id]) if(i != last) dfs(i,id,dfs); v.push_back(id); }; for(int i = 0; i < N; i++){ if(g[i].size() == 1){ dfs(i,-1,dfs); break; } } vector<int> inv(N); for(int i = 0; i < N; i++) inv[v[i]] = i; matrix<int> smin(20,vector<int>(N)), smax(20,vector<int>(N)); for(int i = 0; i < N; i++) smin[0][i] = v[i], smax[0][i] = v[i]; for(int i = 1; i < 20; i++){ for(int j = 0; j+(1<<i) <= N; i++){ smin[i][j] = min(smin[i-1][j],smin[i-1][j+(1<<i-1)]); smax[i][j] = max(smax[i-1][j],smax[i-1][j+(1<<i-1)]); } } auto qmin =[&](int l, int r){ int logg = log2(r-l+1); return min(smin[logg][l],smin[logg][r-(1<<logg)+1]); }; auto qmax =[&](int l, int r){ int logg = log2(r-l+1); return max(smax[logg][l],smax[logg][r-(1<<logg)+1]); }; for(int i = 0; i < Q; i++){ int a = inv[S[i]], b = inv[E[i]]; if(a < b){ int ini = a, fim = b; while(ini!=fim){ int m = (ini+fim+1)>>1; if(qmin(a,m) >= L[i]) ini = m; else fim = m-1; } ans[i] = qmax(ini,b) <= R[i]; } else { int ini = a, fim = b; while(ini!=fim){ int m = (ini+fim)>>1; if(qmin(m,a) >= L[i]) fim = m; else ini = m+1; } ans[i] = qmax(b,ini) <= R[i]; } } } return ans; }

Compilation message (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:18:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |     for(int i = 0; i < X.size(); i++){
      |                    ~~^~~~~~~~~~
werewolf.cpp:70:64: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   70 |                 smin[i][j] = min(smin[i-1][j],smin[i-1][j+(1<<i-1)]);
      |                                                               ~^~
werewolf.cpp:71:64: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   71 |                 smax[i][j] = max(smax[i-1][j],smax[i-1][j+(1<<i-1)]);
      |                                                               ~^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...