제출 #815427

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

werewolf

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

using namespace std;
 
#ifdef DEBUG
  #include "/home/ioi/codes/debug.h"
#else
  #define debug(...) (void) 37
#endif

struct DSU {
  vector<int> link;
  DSU(int n) {
    link.resize(n);
    iota(link.begin(), link.end(), 0);
  }
  int get(int v) {
    return link[v] = (v == link[v] ? v : get(link[v]));
  }
  bool unite(int x, int y) {
    x = get(x), y = get(y);
    if (x == y) {
      return false;
    }
    link[y] = x;
    return true;
  }
};

struct SegTree {
  vector<int> mx;
  int n;
  SegTree(int _n) : n(_n) {
    mx.resize(2 * n + 1, -1);
  }
  int get(int l, int r) {
    int res = -1;
    for (l += n, r += n + 1; l < r; l >>= 1, r >>= 1) {
      debug(l, r, mx[l], mx[r - 1]);
      if (l & 1) {
        res = max(res, mx[l++]);
      }
      if (r & 1) {
        res = max(res, mx[--r]);
      }
    }
    return res;
  }
  void modify(int x, int v) {
    for (mx[x += n] = v; x > 1; x >>= 1) {
      mx[x >> 1] = max(mx[x], mx[x ^ 1]);
    }
  }
};


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 = int(X.size());
  int Q = int(S.size());
  vector<vector<int>> g(N);
  for (int i = 0; i < M; ++i) {
    g[X[i]].push_back(Y[i]);
    g[Y[i]].push_back(X[i]);
  }
  debug(N, g);
  auto Convert_to_array = [&](bool rev, vector<int> end, vector<int> ver) {
    vector<int> ord(N);
    iota(ord.begin(), ord.end(), 0);
    if (rev) {
      reverse(ord.begin(), ord.end());
    }
    debug(ord);
    DSU d(N);
    const int LG = __lg(N) + 1;    
    vector<vector<int>> lift(LG, vector<int>(N, -1));    
    vector<vector<int>> ch(N);
    for (auto v : ord) {
      for (auto u : g[v]) {
        if ((u < v) ^ rev && d.get(v) != d.get(u)) {
          ch[v].push_back(d.get(u));
          lift[0][d.get(u)] = v;
          d.unite(v, u);
        }
      }
    }
    debug(ch, lift);
    for (int l = 1; l < LG; ++l) {
      for (int i = 0; i < N; ++i) {
        int go = lift[l - 1][i];
        lift[l][i] = (go == -1 ? -1 : lift[l - 1][go]);
      }
    }
    vector<int> tin(N), tout(N), tour;
    function<void(int)> Dfs = [&](int v) {
      tin[v] = int(tour.size());
      tour.push_back(v);
      for (auto u : ch[v]) {
        Dfs(u);
      }
      tout[v] = int(tour.size()) - 1;
    };
    Dfs(ord.back());
    debug(tin, tout, lift);
    vector<int> tour_l(Q), tour_r(Q);
    for (int i = 0; i < Q; ++i) {
      int v = ver[i];
      for (int l = LG - 1; l >= 0; --l) {
        if (lift[l][v] != -1 && (!rev? lift[l][v] <= end[i] : lift[l][v] >= end[i])) {
          v = lift[l][v];
        }
      }
      tour_l[i] = tin[v];
      tour_r[i] = tout[v];
    }
    return make_tuple(tour, tour_l, tour_r);
  };
  auto[end_tour, end_l, end_r] = Convert_to_array(false, R, E);
  auto[start_tour, start_l, start_r] = Convert_to_array(true, L, S);
  debug(end_tour, end_l, end_r);
  debug(start_tour, start_l, start_r);
  vector<vector<int>> qs(N);
  for (int i = 0; i < Q; ++i) {
    qs[end_r[i]].push_back(i);
  }
  vector<int> ind(N);
  for (int i = 0; i < N; ++i) {
    ind[start_tour[i]] = i;
  }
  debug(qs, ind);
  SegTree st(N);
  vector<int> ans(Q);
  for (int i = 0; i < N; ++i) {
    st.modify(ind[end_tour[i]], i);
    debug(ind[end_tour[i]], i);
    for (auto q : qs[i]) {
      int mx = st.get(start_l[q], start_r[q]);
      debug(mx, start_l[q], start_r[q]);
      ans[q] = (mx >= end_l[q]);
    }
  }
  return ans;
}

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