제출 #835191

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
835191		Johann	늑대인간 (IOI18_werewolf)	C++14	34 / 100	549 ms	524288 KiB

werewolf

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

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()

int N, Q, M;
vi S, E, L, R;
vvi adj;
vi depth;

struct fenwick
{
  vi arr;
  void init(int size)
  {
    arr.assign(size + 1, 0);
  }
  void add(int i, int v)
  {
    ++i;
    while (i < sz(arr))
      arr[i] += v, i += i & (~i + 1);
  }
  int query(int l, int r) { return query(r - 1) - ((l > 0) ? query(l - 1) : 0); }
  int query(int i)
  {
    ++i;
    int ans = 0;
    while (i > 0)
      ans += arr[i], i -= i & (~i + 1);
    return ans;
  }
};

void dfs(int v, int p)
{
  depth[v] = depth[p] + 1;
  for (int u : adj[v])
    if (u != p)
      dfs(u, v);
}

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)
{
  N = _N, Q = sz(_S), M = sz(X);
  S = _S, E = _E, L = _L, R = _R;
  const int LOG = floor(log2(N));

  adj.assign(N, vi());
  for (int i = 0; i < M; ++i)
    adj[X[i]].push_back(Y[i]), adj[Y[i]].push_back(X[i]);
  int leaf = 0;
  for (int i = 0; i < N; ++i)
    if (sz(adj[i]) == 1)
      leaf = i;

  depth.assign(N, -1);
  dfs(leaf, leaf);

  vpii QR(Q), QL(Q);
  for (int q = 0; q < Q; ++q)
    QR[q] = {R[q], q}, QL[q] = {L[q], q};
  sort(all(QR)), sort(all(QL));
  reverse(all(QL));

  fenwick fen;
  fen.init(N);
  auto computeBorder = [&](int v, pii &ret)
  {
    int l = v;
    for (int j = LOG; j >= 0; --j)
      if (l - (1 << j) >= 0 && fen.query(l - (1 << j), v) == v - (l - (1 << j)))
        l -= 1 << j;
    int r = v + 1;
    for (int j = LOG; j >= 0; --j)
      if (r + (1 << j) <= N && fen.query(v, r + (1 << j)) == (r + (1 << j) - v))
        r += 1 << j;
    ret = {l, r};
  };

  vpii SINT(Q), EINT(Q); // [l, r)
  int idx = 0;
  for (int i = 0; i < Q; ++i)
  {
    while (idx <= QR[i].first)
      fen.add(depth[idx++], 1);
    int q = QR[i].second;
    computeBorder(depth[E[q]], EINT[q]);
  }
  idx = N - 1;
  fen.init(N);
  for (int i = 0; i < Q; ++i)
  {
    while (idx >= QL[i].first)
      fen.add(depth[idx--], 1);
    int q = QL[i].second;
    computeBorder(depth[S[q]], SINT[q]);
  }

  std::vector<int> A(Q);
  for (int q = 0; q < Q; ++q)
  {
    A[q] = max(EINT[q].first, SINT[q].first) < min(EINT[q].second, SINT[q].second);
  }
  return A;
}

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