Submission #880285

#	Time	Username	Problem	Language	Result	Execution time	Memory
880285		NeroZein	Werewolf (IOI18_werewolf)	C++17	100 / 100	796 ms	192700 KiB

werewolf

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

using namespace std; 

const int LOG = 20; 
const int MAX_N = 4e5 + 5; 

int n[2]; 
int p[MAX_N][2];
int val[MAX_N][2];
vector<int> adj[MAX_N], g[MAX_N][2];

int get(int v, int ver) {
  return p[v][ver] = (p[v][ver] == v ? v : get(p[v][ver], ver)); 
}

void unite(int u, int v, int ver) {
  u = get(u, ver), v = get(v, ver);
  if (u == v) return;  
  int puv = n[ver]++; 
  g[puv][ver].push_back(u);
  g[puv][ver].push_back(v);
  p[puv][ver] = p[u][ver] = p[v][ver] = puv; 
  if (ver == 0) {
    val[puv][ver] = min(val[u][ver], val[v][ver]);     
  } else {
    val[puv][ver] = max(val[u][ver], val[v][ver]);     
  }
}

int cnt[2];
int dep[MAX_N][2], up[MAX_N][2][LOG]; 
int lx[MAX_N][2], rx[MAX_N][2], owner[MAX_N][2]; 

void dfs(int v, int ver) {
  lx[v][ver] = ++cnt[ver]; 
  owner[cnt[ver]][ver] = v; 
  for (int u : g[v][ver]) {
    dep[u][ver] = dep[v][ver] + 1; 
    up[u][ver][0] = v; 
    for (int j = 1; j < LOG; ++j) {
      up[u][ver][j] = up[up[u][ver][j - 1]][ver][j - 1]; 
    }
    dfs(u, ver); 
  }
  rx[v][ver] = cnt[ver]; 
}

int tree[MAX_N];
int common[MAX_N];
vector<array<int, 4>> qs[MAX_N];

void upd(int i) {
  while (i < MAX_N) {
    tree[i]++;
    i += i & -i;
  }
}

int query(int i) {
  int ret = 0;
  while (i) {
    ret += tree[i];
    i -= i & -i; 
  }
  return ret;
}

int query(int l, int r) {
  return query(r) - query(l - 1); 
}

vector<int> check_validity(int N, vector<int> X, vector<int> Y,
                                  vector<int> S, vector<int> E,
                                  vector<int> L, vector<int> R) {
  for (int i = 0; i < (int) X.size(); ++i) {
    adj[X[i]].push_back(Y[i]);
    adj[Y[i]].push_back(X[i]);
  }
  n[0] = n[1] = N; 
  for (int i = 0; i < N; ++i) {
    p[i][0] = p[i][1] = val[i][0] = val[i][1] = i; 
  }
  for (int v = N - 1; v >= 0; --v) {
    for (int u : adj[v]) {
      if (u > v) {
        unite(u, v, 0); 
      }
    }
  }
  for (int v = 0; v < N; ++v) {
    for (int u : adj[v]) {
      if (u < v) {
        unite(u, v, 1); 
      }
    }
  }
  assert(n[0] == n[1] && n[0] == N * 2 - 1); 
  dfs(n[0] - 1, 0); dfs(n[1] - 1, 1); 
  int Q = (int) S.size(); 
  
  for (int i = 0; i < Q; ++i) {
    if (S[i] < L[i] || E[i] > R[i]) continue; 
    vector<int> r = {S[i], E[i]}; 
    for (int j = LOG - 1; j >= 0; --j) {
      if ((1 << j) <= dep[r[0]][0] && val[up[r[0]][0][j]][0] >= L[i]) {
        r[0] = up[r[0]][0][j];
      }
      if ((1 << j) <= dep[r[1]][1] && up[r[1]][1][j] && val[up[r[1]][1][j]][1] <= R[i]) {
        r[1] = up[r[1]][1][j]; 
      }
    }
    int l1 = lx[r[0]][0], r1 = rx[r[0]][0]; 
    int l2 = lx[r[1]][1], r2 = rx[r[1]][1]; 
    qs[l2 - 1].push_back({l1, r1, -1, i});
    qs[r2].push_back({l1, r1, 1, i}); 
  }
  for (int i = 1; i <= n[1]; ++i) {//eulerian 
    if (owner[i][1] < N) {
      upd(lx[owner[i][1]][0]); 
    }
    for (auto [l1, r1, v, j] : qs[i]) {
      common[j] += query(l1, r1) * v; 
    }
  }
  
  vector<int> A(Q); 
  for (int i = 0; i < Q; ++i) {
    A[i] = common[i] > 0; 
  }
  return A;
}

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