Submission #798135

#TimeUsernameProblemLanguageResultExecution timeMemory
798135TheSahibWerewolf (IOI18_werewolf)C++14
100 / 100
3902 ms407320 KiB
#include "werewolf.h" #include <bits/stdc++.h> using namespace std; const int MAX = 2e5 + 5; const int BLOCK = 30; const int LOGMAX = 18; struct order{ vector<int> v; bitset<MAX> st[MAX / BLOCK + 2]; void preCalc(){ int p = 0; for (int i = 0; i < v.size(); i++) { if(i % BLOCK == 0){ p++; st[p] = st[p - 1]; } st[p][v[i]] = 1; } } bitset<MAX> query(int p){ bitset<MAX> ans = st[p / BLOCK]; for (int i = p / BLOCK * BLOCK; i <= p; i++) { ans[v[i]] = 1; } return ans; } }; int n; struct graph{ vector<int> tree[MAX]; int par[LOGMAX][MAX]; order v; int timeIn[MAX], timeOut[MAX]; void dfs(int node, int p){ par[0][node] = p; timeIn[node] = v.v.size(); v.v.push_back(node); for(int to:tree[node]){ if(to == p) continue; dfs(to, node); } timeOut[node] = v.v.size() - 1; } void preCalc(){ for (int j = 1; j < LOGMAX; j++) { for (int i = 0; i < n; i++) { par[j][i] = par[j - 1][par[j - 1][i]]; } } v.preCalc(); } int lift1(int v, int a){ for(int j = LOGMAX - 1; j >= 0; --j){ int u = par[j][v]; if(u >= a){ v = u; } } return v; } int lift2(int v, int a){ for(int j = LOGMAX - 1; j >= 0; --j){ int u = par[j][v]; if(u <= a){ v = u; } } return v; } bitset<MAX> ask(int node){ return v.query(timeOut[node]) ^ v.query(timeIn[node] - 1); } }; vector<int> g[MAX]; graph tree1, tree2; struct DSU{ int par[MAX]; bool b = 0; void init(int N, bool _b){ b = _b; memset(par, -1, sizeof(par)); } int get(int node){ if(par[node] < 0) return node; return par[node] = get(par[node]); } bool unite(int v, int u){ v = get(v); u = get(u); if(v == u) return false; if(v < u && b) swap(v, u); if(v > u && !b) swap(v, u); par[v] += par[u]; par[u] = v; return true; } }; vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) { n = N; DSU dsu; for (int i = 0; i < X.size(); i++) { g[X[i]].push_back(Y[i]); g[Y[i]].push_back(X[i]); } dsu.init(N, 0); for (int node = N - 1; node >= 0; node--) { for(int to:g[node]){ if(to < node) continue; int a = dsu.get(to); if(dsu.unite(node, to)){ tree1.tree[node].push_back(a); } } } dsu.init(N, 1); for (int node = 0; node < N; node++) { for(int to:g[node]){ if(to > node) continue; int a = dsu.get(to); if(dsu.unite(node, to)){ tree2.tree[node].push_back(a); } } } tree1.dfs(0, 0); tree2.dfs(n - 1, n - 1); tree1.preCalc(); tree2.preCalc(); vector<int> ans(S.size()); for (int i = 0; i < S.size(); i++) { int a = tree1.lift1(S[i], L[i]); int b = tree2.lift2(E[i], R[i]); ans[i] = (tree1.ask(a) & tree2.ask(b)).any(); } return ans; }

Compilation message (stderr)

werewolf.cpp: In member function 'void order::preCalc()':
werewolf.cpp:15:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |         for (int i = 0; i < v.size(); i++)
      |                         ~~^~~~~~~~~~
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:113:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |     for (int i = 0; i < X.size(); i++)
      |                     ~~^~~~~~~~~~
werewolf.cpp:146:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  146 |     for (int i = 0; i < S.size(); i++)
      |                     ~~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...