제출 #390252

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
390252		Hegdahl	늑대인간 (IOI18_werewolf)	C++17	100 / 100	2627 ms	181044 KiB

werewolf

#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#include "werewolf.h"
#include <bits/stdc++.h>

#define ar array

using namespace std;

struct reachability_tree {
  vector<int> boss, under, tup, time_of, lk, rk, leftmost, rightmost;

  vector<int> up[20];

  int find(int i) {
    return i == boss[i] ? i : boss[i] = find(boss[i]);
  }

  void unite(int i, int j) {
    i = find(i), j = find(j);
    if (i == j) return;

    if (under[i] < under[j]) swap(i, j);
    under[i] += under[j];
    boss[j] = i;
    tup[i] = max(tup[i], tup[j]);
  }

  int nxt_new_node;
  void add_edge(int i, int j, int t) {
    i = find(i), j = find(j);
    if (i == j) return;
    i = tup[i];
    j = tup[j];

    lk[nxt_new_node] = i;
    rk[nxt_new_node] = j;
    time_of[nxt_new_node] = t;

    unite(i, nxt_new_node);
    unite(j, nxt_new_node);

    ++nxt_new_node;
  }

  vector<int> tour, pof;
  void dfs(int cur) {
    if (lk[cur] != -1) {
      dfs(lk[cur]);
      leftmost[cur] = leftmost[lk[cur]];
      up[0][lk[cur]] = cur;
    } else leftmost[cur] = tour.size();

    pof[cur] = tour.size();
    tour.push_back(cur);
    up[0][cur] = cur;

    if (rk[cur] != -1) {
      dfs(rk[cur]);
      rightmost[cur] = rightmost[rk[cur]];
      up[0][rk[cur]] = cur;
    } else rightmost[cur] = tour.size()-1;
  }

  ar<int, 2> qry(int i, int t) {
    for (int lvl = 19; lvl >= 0; --lvl)
      if (time_of[up[lvl][i]] <= t)
        i = up[lvl][i];
    return {leftmost[i], rightmost[i]};
  }

  reachability_tree(int n, vector<ar<int, 3>> e) {
    boss.resize(2*n);
    under.resize(2*n, 1);
    tup.resize(2*n);
    time_of.resize(2*n);
    lk.resize(2*n, -1);
    rk.resize(2*n, -1);
    pof.resize(2*n, -1);
    rightmost.resize(2*n, -1);
    leftmost.resize(2*n, -1);

    iota(boss.begin(), boss.end(), 0);
    iota(tup.begin(), tup.end(), 0);

    nxt_new_node = n;

    for (auto [w, i, j] : e)
      add_edge(i, j, w);

    for (int lvl = 0; lvl < 20; ++lvl) {
      up[lvl].resize(2*n);
      iota(up[lvl].begin(), up[lvl].end(), 0);
    }

    for (int i = 0; i < 2*n; ++i)
      if (i == find(i))
        dfs(tup[i]);

    for (int lvl = 0; lvl < 19; ++lvl)
      for (int i = 0; i < 2*n; ++i)
        up[lvl+1][i] = up[lvl][up[lvl][i]];

    /*cout << "tour: ";
    for (int x : tour)
      cerr << x << ' ';
    cerr << '\n';
    cout << "pof: ";
    for (int x : pof)
      cerr << x << ' ';
    cerr << '\n';
    cout << "leftmost: ";
    for (int l : leftmost)
      cerr << l << ' ';
    cerr << '\n';
    cout << "rightmost: ";
    for (int r : rightmost)
      cerr << r << ' ';
    cerr << '\n';*/
  }
};

const int mxN = 4e5;
const int lg2 = __lg(mxN-1)+1;
const int offset = 1<<lg2;
vector<int> values[2*offset];

void insert(int i, int j) {
  i += offset;
  do {
    values[i].push_back(j);
  } while (i /= 2);
}

bool check(int I, int lo, int hi) {
  return lower_bound(values[I].begin(), values[I].end(), lo)
      != upper_bound(values[I].begin(), values[I].end(), hi);
}

bool qry(int li, int hi, int lj, int hj) {
  li += offset-1;
  hi += offset+1;

  while (li+1 < hi) {
    if (li%2 == 0) if (check(li+1, lj, hj)) return true;
    if (hi%2 == 1) if (check(hi-1, lj, hj)) return true;
    li /= 2, hi /= 2;
  }

  return false;
}

vector<int> check_validity(int n, vector<int> e0, vector<int> e1,
                                vector<int> q0, vector<int> q1,
                                vector<int> ls, vector<int> rs) {
  int m = e0.size();
  int q = q0.size();

  vector<ar<int, 3>> e(m);
  for (int mm = 0; mm < m; ++mm)
    e[mm] = {max(e0[mm], e1[mm]), e0[mm], e1[mm]};

  sort(e.begin(), e.end());
  reachability_tree lo_tree(n, e);
  for (auto &[w, i, j] : e)
    w = n-min(i, j);
  sort(e.begin(), e.end());
  reachability_tree hi_tree(n, e);

  for (int nn = 0; nn < n; ++nn) {
    int i = lo_tree.pof[nn];
    int j = hi_tree.pof[nn];
    insert(i, j);
  }

  for (int i = 2*offset-1; i > 0; --i)
    sort(values[i].begin(), values[i].end());

  vector<int> ans(q);
  for (int i = 0; i < q; ++i) {
    //cerr << '\n';
    //cerr << q0[i] << ' ' << q1[i] << ' ' << ls[i] << ' ' << rs[i] << '\n';
    auto [ll, lr] = lo_tree.qry(q1[i], rs[i]);
    auto [hl, hr] = hi_tree.qry(q0[i], n-ls[i]);

    ans[i] = qry(ll, lr, hl, hr);
  }

  return ans;
}

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