Submission #124051

#	Time	Username	Problem	Language	Result	Execution time	Memory
124051		RockyB	Werewolf (IOI18_werewolf)	C++17	100 / 100	828 ms	148984 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>

#define f first
#define s second

#define pb push_back
#define pp pop_back
#define mp make_pair

#define sz(x) (int)x.size()
#define sqr(x) ((x) * 1ll * (x))
#define all(x) x.begin(), x.end()

#define rep(i, l, r) for (int i = (l); i < (r); i++)
#define per(i, l, r) for (int i = (l); i >= (r); i--)

#define Kazakhstan ios_base :: sync_with_stdio(0), cin.tie(0), cout.tie(0);

#define nl '\n'
#define ioi exit(0);

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

const int MAXN = (int)5e5 + 7;
const int inf = (int)1e9 + 7;
const int mod = (int)1e9 + 7;
const ll linf = (ll)1e18 + 7;

const int dx[] = {-1, 0, 1, 0, 1, -1, -1, 1};
const int dy[] = {0, 1, 0, -1, 1, -1, 1, -1};

using namespace std;

int n;
vector <int> X, Y, L, R, S, E;
vector <int> g[MAXN], adj[2][MAXN];

bool was[MAXN];

struct dsu {
  int p[MAXN];
  int get(int i) {
    return p[i] == i ? i : p[i] = get(p[i]);
  }
} d;

struct fenwick {
  int f[MAXN];
  void upd(int p, int x) {
    for (; p < MAXN; p |= p + 1) f[p] += x;
  }
  int get(int p) {
    int sum = 0;
    for (; p >= 0; p = (p & (p + 1)) - 1) sum += f[p];
    return sum;
  }
} f;

vector < pair <int, int> > q[2][MAXN];
vector < array <int, 4> > qu[MAXN]; /// i, f, l, r
int sum[MAXN];
int par[2][MAXN];

int tmr;
int tin[2][MAXN], tout[2][MAXN];
int a[2][MAXN];
void dfs(int v, int id) {
  tin[id][v] = ++tmr;
  a[id][tmr] = v;
  /*
  {
    / *
      TODO:
        Then Delete it (it's just for debug)
    * /
    cerr << v << " -> ";
    for (auto to : adj[id][v]) {
      {
        cerr << to << ' ';
      }
    }
    cerr << nl;
  }
  */
  for (auto to : adj[id][v]) {
    if (!tin[id][to]) {
      dfs(to, id);
    }
  }
  tout[id][v] = tmr;
}

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;
  X = _X;
  Y = _Y;
  S = _S;
  E = _E;
  L = _L;
  R = _R;
  // copy finished
  // checked 1

  rep(i, 0, sz(X)) {
    g[X[i]].pb(Y[i]);
    g[Y[i]].pb(X[i]);
  }
  // checked 1

  rep(i, 0, sz(S)) {
    q[0][L[i]].pb({S[i], i});
    q[1][R[i]].pb({E[i], i});
  }
  // checked 1
  
  per(i, n - 1, 0) {
    d.p[i] = i;
    for (auto to : g[i]) {
      if (!was[to] || d.get(to) == i) continue;
      adj[0][i].pb(d.get(to));
      d.p[d.get(to)] = i;
    }
    for (auto it : q[0][i]) {
      par[0][it.s] = d.get(it.f);
    }
    was[i] = 1;
  }
  // checked 1

  memset(was, 0, sizeof(was));
  rep(i, 0, n) {
    d.p[i] = i;
    for (auto to : g[i]) {
      if (!was[to] || d.get(to) == i) continue;
      adj[1][i].pb(d.get(to));
      d.p[d.get(to)] = i;
    }
    for (auto it : q[1][i]) {
      par[1][it.s] = d.get(it.f);
    }
    was[i] = 1;
  }
  // checked 1

  dfs(0, 0);
  tmr = 0;
  dfs(n - 1, 1);
  // checked 1

  rep(i, 0, sz(S)) {
    int v1 = par[0][i];
    int l1 = tin[0][v1], r1 = tout[0][v1];
    int v2 = par[1][i];
    int l2 = tin[1][v2], r2 = tout[1][v2];

    if (l1) qu[l1 - 1].pb({i, -1, l2, r2});
    qu[r1].pb({i, 1, l2, r2});
  }
  vector <int> ans(sz(S)), pos(n, 0);
  rep(i, 1, n + 1) pos[a[1][i]] = i;
  rep(i, 1, n + 1) {
    f.upd(pos[a[0][i]], 1);
    for (auto it : qu[i]) {
      ans[it[0]] += it[1] * (f.get(it[3]) - f.get(it[2] - 1));
    }
  }
  rep(i, 0, sz(ans)) {
    assert(ans[i] >= 0);
    if (ans[i] > 0) ans[i] = 1;
    else ans[i] = 0;
  }
  return ans;
}

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