Submission #1163952

#	Time	Username	Problem	Language	Result	Execution time	Memory
1163952		iah	Werewolf (IOI18_werewolf)	C++20	100 / 100	490 ms	82684 KiB

werewolf

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

#define NAME ""
#define ll long long
#define pii pair < int , int >
#define fi first
#define se second
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i ++)
#define FORD(i, a, b) for (int i = (a), _b = (b); i >= _b; i --)
#define REP(i, n) for (int i = 0, _n = (n); i < _n; i ++)
#define bit(x, i) (((x) >> (i)) & 1ll)
#define mask(x) (1ll << (x))
#define mem(f, x) memset(f, x, sizeof(f))
#define sz(x) (int32_t) (x.size())

const int nmax = 2e5;
int timer = 0, in[2][nmax + 4], out[2][nmax + 4], top[2][nmax + 4], rev[nmax + 4];
vector < int > g[nmax + 4], adj[nmax + 4], ql[nmax + 4], qr[nmax + 4], op[nmax + 4], cl[nmax + 4];

struct DSU {
  int par[nmax + 4];

  void init(int n) {
    iota(par, par + n, 0);
  }

  int find_par(int i) {
    return (par[i] == i ? i : par[i] = find_par(par[i]));
  }

  bool unite(int u, int v) {
    u = find_par(u);
    v = find_par(v);

    if (u == v) {
      return 0;
    }

    par[v] = u;
    adj[u].push_back(v);
    return 1;
  }
}dsu;

void dfs(int type, int i, int j) {
  ++ timer;
  in[type][i] = timer;
  for (auto x: adj[i]) {
//    cout << i << " " << x << "\n";

    if (x == j) {
      continue;
    }

    dfs(type, x, i);
  }

  out[type][i] = timer;
}

struct SegTree {
  int n, b[nmax * 4 + 4];

  void init(int _n) {
    n = _n;
  }

  void update(int id, int l, int r, int pos, int val) {
    if (l == r) {
      b[id] = val;
      return;
    }

    int mid = l + r >> 1;

    if (mid >= pos) {
      update(id << 1, l, mid, pos, val);
    }
    else {
      update(id << 1 | 1, mid + 1, r, pos, val);
    }

    b[id] = b[id << 1] + b[id << 1 | 1];
  }

  void update(int pos, int val) {
    update(1, 1, n, pos, val);
  }

  int get(int id, int l, int r, int u, int v) {
    if (l > v || u > r) {
      return 0;
    }

    if (u <= l && r <= v) {
      return b[id];
    }

    int mid = (l + r) >> 1;

    return get(id << 1, l, mid, u, v) + get(id << 1 | 1, mid + 1, r, u, v);
  }

  int get(int l, int r) {
    return get(1, 1, n, l, r);
  }
}seg;

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) {
  int m = sz(x), q = sz(s);
  seg.init(n);

  vector < int > ans(q, 0);

  REP(i, m) {
    g[x[i]].push_back(y[i]);
    g[y[i]].push_back(x[i]);
  }

  REP(i, q) {
    ql[l[i]].push_back(i);
    qr[r[i]].push_back(i);
  }

  dsu.init(n);
  REP(i, n) {
    for (auto x: g[i]) {
      if (x < i) {
        dsu.unite(i, x);
      }
    }

    for (auto x: qr[i]) {
      top[0][x] = dsu.find_par(e[x]);
    }
  }
  dfs(0, n - 1, -1);

  dsu.init(n);
  REP(i, n) {
    vector < int > ().swap(adj[i]);
  }
  FORD(i, n - 1, 0) {
    for (auto x: g[i]) {
      if (x > i) {
        dsu.unite(i, x);
      }
    }

    for (auto x: ql[i]) {
      top[1][x] = dsu.find_par(s[x]);
    }
  }
  timer = 0;
  dfs(1, 0, -1);

//  REP(i, n) {
//    cout << i << ": " << in[0][i] << " " << in[1][i] << "\n";
//  }
//
//  REP(i, q) {
//    cout << i << " -> " << top[0][i] << " " << top[1][i] << "\n";
//  }

  REP(i, q) {
    int j = top[0][i];
    op[in[0][j] - 1].push_back(i);
    cl[out[0][j]].push_back(i);

//    cout << in[0][j] - 1 << " " << out[0][j] << "\n";
  }

  REP(i, n) {
    rev[in[0][i]] = i;
  }

  FOR(i, 1, n) {
    int j = rev[i];
    seg.update(in[1][j], 1);

    for (auto x: op[i]) {
      int j = top[1][x];
      ans[x] -= seg.get(in[1][j], out[1][j]);
    }

    for (auto x: cl[i]) {
      int j = top[1][x];
      ans[x] += seg.get(in[1][j], out[1][j]);
    }
  }

  REP(i, q) {
    if (s[i] < l[i]) {
      ans[i] = 0;
    }

    if (e[i] > r[i]) {
      ans[i] = 0;
    }

    ans[i] = min(ans[i], 1);
  }

  return ans;
}

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