Submission #835286

#	Time	Username	Problem	Language	Result	Execution time	Memory
835286		Johann	Werewolf (IOI18_werewolf)	C++14	100 / 100	795 ms	180532 KiB

werewolf

#include "werewolf.h"
#include "bits/stdc++.h"
using namespace std;

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
typedef vector<vpii> vvpii;
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()

int N, Q, M;
vi S, E, L, R;
vvi adj;
vvi Eadj, Sadj;
vi Ein, Eout, Sin, Sout;
vvi Elift, Slift;
vi depth;
int idx;

struct unionfind
{
  vi arr;
  void init(int size)
  {
    arr.resize(size);
    iota(all(arr), 0);
  }
  int find(int i) { return arr[i] = (arr[i] == i) ? i : find(arr[i]); }
  void combine(int a, int b)
  {
    // a is the one it gets merged to
    a = find(a), b = find(b);
    arr[b] = a;
  }
};
unionfind uf;

void dfs(vvi &A, int v, int p, vi &in, vi &out, vvi &lift)
{
  in[v] = idx++;
  lift[v][0] = p;
  for (int j = 1; j < sz(lift[v]); ++j)
    lift[v][j] = lift[lift[v][j - 1]][j - 1];
  for (int u : A[v])
    if (u != p)
      dfs(A, u, v, in, out, lift);
  out[v] = idx++;
}
bool is_vorg(int a, int b, vi &in, vi &out)
{
  return in[a] <= in[b] && out[b] <= out[a];
}

vvpii tocheck;          // [e] := list of s values with whom the subtree comparison should work
vector<set<int>> nodes; // [e] := set of all invalues my nodes have in S
vi A;                   // the answer
void answer(int v, int p)
{
  // going through e per definition
  nodes[v].insert(Sin[v]);
  for (int u : Eadj[v])
    if (u != p)
    {
      answer(u, v);
      if (sz(nodes[u]) > sz(nodes[v]))
        swap(nodes[u], nodes[v]);
      for (int x : nodes[u])
        nodes[v].insert(x);
    }

  for (pii tmp : tocheck[v])
  {
    int s, q;
    tie(s, q) = tmp;
    auto it = nodes[v].lower_bound(Sin[s]);
    if (it == nodes[v].end())
      A[q] = 0;
    else
    {
      int lb = *it;
      assert(lb >= Sin[s]);
      A[q] = (lb < Sout[s]);
    }
  }
}

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, Q = sz(_S), M = sz(X);
  S = _S, E = _E, L = _L, R = _R;

  adj.assign(N, vi());
  for (int i = 0; i < M; ++i)
    adj[X[i]].push_back(Y[i]), adj[Y[i]].push_back(X[i]);

  Eadj.assign(N, vi());
  uf.init(N);
  for (int v = 0; v < N; ++v)
  {
    for (int u : adj[v])
      if (u < v)
      {
        u = uf.find(u);
        if (u != v)
          Eadj[v].push_back(u), uf.combine(v, u);
      }
  }
  idx = 0;
  Ein.resize(N), Eout.resize(N);
  Elift.assign(N, vi(ceil(log2(N))));
  dfs(Eadj, N - 1, N - 1, Ein, Eout, Elift);

  Sadj.assign(N, vi());
  uf.init(N);
  for (int v = N - 1; v >= 0; --v)
  {
    for (int u : adj[v])
      if (u > v)
      {
        u = uf.find(u);
        if (u != v)
          Sadj[v].push_back(u), uf.combine(v, u);
      }
  }
  idx = 0;
  Sin.resize(N), Sout.resize(N);
  Slift.assign(N, vi(ceil(log2(N))));
  dfs(Sadj, 0, 0, Sin, Sout, Slift);

  tocheck.assign(N, vpii());
  for (int q = 0; q < Q; ++q)
  {
    int Enode = E[q];
    for (int j = sz(Elift[Enode]) - 1; j >= 0; --j)
      if (Elift[Enode][j] <= R[q])
        Enode = Elift[Enode][j];

    int Snode = S[q];
    for (int j = sz(Slift[Snode]) - 1; j >= 0; --j)
      if (Slift[Snode][j] >= L[q])
        Snode = Slift[Snode][j];

    tocheck[Enode].push_back({Snode, q});
  }

  A.assign(Q, 0);
  nodes.assign(N, set<int>());
  answer(N - 1, N - 1);

  return A;
}

• Subtask 1: 7 / 7
• Subtask 2: 8 / 8
• Subtask 3: 34 / 34
• Subtask 4: 51 / 51