Submission #600835

#	Time	Username	Problem	Language	Result	Execution time	Memory
600835		Mamedov	Werewolf (IOI18_werewolf)	C++17	100 / 100	1084 ms	154864 KiB

werewolf

#pragma GCC optimize ("O3")
#include "werewolf.h"
#include <bits/stdc++.h>
#define pii pair<int, int>
#define piii pair<pii, int>
#define vi vector<int>
#define vvi vector<vi>
#define vpii vector<pii>
#define vvpii vector<vpii>
#define f first
#define s second
#define oo 1000000001
#define eb emplace_back
#define pb push_back
#define mpr make_pair
#define size(v) (int)v.size()
#define ln '\n'
#define ull unsigned long long
#define ll long long
#define all(v) v.begin(), v.end()

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

struct DSU {
  int components;
  vector<int>par;
  DSU(int n) {
    par.assign(n, -1);
    components = n;
  }
  int Find(int u) {
    if (par[u] < 0) return u;
    else return par[u] = Find(par[u]);
  }
  bool Union(int u, int v) {
    u = Find(u);
    v = Find(v);
    if (u != v) {
      par[u] += par[v];
      par[v] = u;
      --components;
      return true;
    } else {
      return false;
    }
  }
};

void dfs1(int node, vvi &tree, int &tmr, vi &tin, vi &tout) {
  tin[node] = ++tmr;
  for (int to : tree[node]) {
    dfs1(to, tree, tmr, tin, tout);
  }
  tout[node] = tmr;
}

void dfs2(int node, vvi &tree, vi &tin, vi &tout, vvpii &group, vector<set<int>> &subTree, vi &res) {
  int maxChild = -1;
  for (int to : tree[node]) {
    dfs2(to, tree, tin, tout, group, subTree, res);
    if (maxChild == -1 || size(subTree[to]) > size(subTree[maxChild])) {
      maxChild = to;
    }
  }
  if (maxChild != -1) {
    swap(subTree[node], subTree[maxChild]);
    ///subTree[node] = subTree[maxChild];
    for (int to : tree[node]) {
      if (to != maxChild) {
        subTree[node].insert(all(subTree[to]));
      }
    }
  }
  subTree[node].insert(tin[node]);
  for (auto [v, i] : group[node]) {
    auto itr = subTree[node].lower_bound(tin[v]);
    if (itr != subTree[node].end() && (*itr) <= tout[v]) {
      res[i] = 1;
    }
  }
}

vi check_validity(int N, vi X, vi Y, vi S, vi E, vi L, vi R) {
  int M = size(X);
  vvi g(N);
  for (int i = 0; i < M; ++i) {
    g[X[i]].eb(Y[i]);
    g[Y[i]].eb(X[i]);
  }

  DSU dsu1(N), dsu2(N);
  vvi treeHuman(N), treeWolf(N);
  vector<vvi>up(2, vvi(19, vi(N)));

  up[0][0][0] = 0;
  for (int i = N - 1; i >= 0; --i) {
    for (int to : g[i]) {
      if (to > i && dsu1.Find(to) != i) {
        treeHuman[i].eb(dsu1.Find(to));
        up[0][0][dsu1.Find(to)] = i;
        dsu1.Union(i, to);
      }
    }
  }
  up[1][0][N - 1] = N - 1;
  for (int i = 0; i < N; ++i) {
    for (int to : g[i]) {
      if (to < i && dsu2.Find(to) != i) {
        treeWolf[i].eb(dsu2.Find(to));
        up[1][0][dsu2.Find(to)] = i;
        dsu2.Union(i, to);
      }
    }
  }
  for (int k = 0; k < 2; ++k) {
    for (int i = 1; i < 19; ++i) {
      for (int j = 0; j < N; ++j) {
        up[k][i][j] = up[k][i - 1][up[k][i - 1][j]];
      }
    }
  }
  int Q = size(S);
  vvpii group(N);
  for (int i = 0; i < Q; ++i) {
    for (int j = 18; j >= 0; --j) {
      if (up[0][j][S[i]] >= L[i]) {
        S[i] = up[0][j][S[i]];
      }
      if (up[1][j][E[i]] <= R[i]) {
        E[i] = up[1][j][E[i]];
      }
    }
    group[E[i]].eb(mpr(S[i], i));
  }

  int tmr = -1;
  vi tin(N), tout(N);
  dfs1(0, treeHuman, tmr, tin, tout);

  vi res(Q, 0);
  vector<set<int>>subTree(N);
  dfs2(N - 1, treeWolf, tin, tout, group, subTree, res);
  return res;
}

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