Submission #902210

#	Time	Username	Problem	Language	Result	Execution time	Memory
902210		rxlfd314	Werewolf (IOI18_werewolf)	C++17	100 / 100	817 ms	132036 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
using ari2 = array<int, 2>;

#define vt vector
#define size(x) (int((x).size()))
#define all(x) begin(x), end(x)

#define REP(a, b, c, d) for (int a = (b); (d) > 0 ? a <= (c) : a >= (c); a += (d))
#define FOR(a, b, c) REP(a, b, c, 1)
#define ROF(a, b, c) REP(a, b, c, -1)

vt<int> check_validity(int N, vt<int> X, vt<int> Y, vt<int> S, vt<int> E, vt<int> L, vt<int> R) {
  vt<int> adj[N];
  FOR(i, 0, size(X)-1) {
    adj[X[i]].push_back(Y[i]);
    adj[Y[i]].push_back(X[i]);
  }
  auto gen_tree = [&](int mul) {
    int uf[N], mx[N];
    memset(uf, -1, sizeof(uf));
    FOR(i, 0, N-1)
      mx[i] = i * mul;
    function<int(int)> find = [&](int i) {
      return uf[i] < 0 ? i : uf[i] = find(uf[i]);
    };
    vt<vt<int>> tree(N);
    auto unite = [&](int a, int b) {
      if ((a = find(a)) == (b = find(b)))
        return false;
      if (uf[a] > uf[b])
        swap(a, b);
      tree[mul * max(mx[a], mx[b])].push_back(mul * min(mx[a], mx[b]));
      uf[a] += uf[b];
      uf[b] = a;
      mx[a] = max(mx[a], mx[b]);
      return true;
    };
    REP(i, ~mul ? 0 : N-1, ~mul ? N-1 : 0, mul)
      for (int j : adj[i])
        if (j * mul < i * mul)
          unite(i, j);
    return tree;
  };
  
  vt<vt<int>> wt = gen_tree(1); // root is N-1
  vt<vt<int>> ht = gen_tree(-1); // root is 0
  
  int tin[N], tout[N], lift_ht[N][18], lift_wt[N][18], timer = 0;
  function<void(int, int)> dfs_ht = [&](int i, int p) {
    tin[i] = timer++;
    lift_ht[i][0] = p;
    for (int j : ht[i])
      dfs_ht(j, i);
    tout[i] = timer - 1;
  };
  function<void(int, int)> dfs_wt = [&](int i, int p) {
    lift_wt[i][0] = p;
    for (int j : wt[i])
      dfs_wt(j, i);
  };
  dfs_ht(0, 0); 
  dfs_wt(N-1, N-1);
  FOR(j, 1, 17)
    FOR(i, 0, N-1) {
      lift_wt[i][j] = lift_wt[lift_wt[i][j-1]][j-1];
      lift_ht[i][j] = lift_ht[lift_ht[i][j-1]][j-1];
    }
  
  // S in ht
  // E in wt
  vt<ari2> Q[N];
  FOR(i, 0, size(S)-1) {
    // find maximum ancestor of E[i]
    int a = E[i];
    ROF(j, 17, 0)
      if (lift_wt[a][j] <= R[i])
        a = lift_wt[a][j];
    // find minimum ancestor of S[i]
    int b = S[i];
    ROF(j, 17, 0)
      if (lift_ht[b][j] >= L[i])
        b = lift_ht[b][j];
    Q[a].push_back({b, i});
  }
  
  vt<int> ans(size(S));
  set<int> ss[N];
  function<void(int)> dfs = [&](int i) {
    ss[i].insert(tin[i]);
    for (int j : wt[i]) {
      dfs(j);
      if (size(ss[j]) > size(ss[i]))
        swap(ss[j], ss[i]);
      for (int v : ss[j])
        ss[i].insert(v);
      ss[j].clear();
    }
    for (auto [j, q] : Q[i])
      ans[q] = ss[i].lower_bound(tin[j]) != ss[i].upper_bound(tout[j]);
  };
  dfs(N-1);
  
  return ans;
}

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