제출 #292092

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
292092		AlexLuchianov	늑대인간 (IOI18_werewolf)	C++14	100 / 100	1867 ms	153080 KiB

werewolf

#include "werewolf.h"
#include <vector>
#include <cassert>
#include <cmath>
#include <algorithm>
#include <iostream>

using ll = long long;
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))

int const lgmax = 20;

class Dsu{
public:
  std::vector<int> mult;
  Dsu(int n) {
    mult.resize(n);
    for(int i = 0; i < n; i++)
      mult[i] = i;
  }
  int jump(int gala) {
    if(mult[gala] != gala)
      mult[gala] = jump(mult[gala]);
    return mult[gala];
  }
  void unite(int gala, int galb) {
    gala = jump(gala);
    galb = jump(galb);
    mult[galb] = gala;
  }
};

class SegmentTree{
private:
  std::vector<std::vector<int>> aint;
public:
  SegmentTree(int n) {
    aint.resize(1 + 4 * n);
  }
  void build(int node, int from, int to, std::vector<int> &aux) {
    if(from < to) {
      int mid = (from + to) / 2;
      build(node * 2, from, mid, aux);
      build(node * 2 + 1, mid + 1, to, aux);
      aint[node].resize(to - from + 1);
      std::merge(aint[node * 2].begin(), aint[node * 2].end(),
                 aint[node * 2 + 1].begin(), aint[node * 2 + 1].end(),
                 aint[node].begin());
    } else
      aint[node].push_back(aux[from]);
  }

  bool check_node(int node, int l, int r) {
    std::vector<int>::iterator it = std::lower_bound(aint[node].begin(), aint[node].end(), l);
    if(it == aint[node].end() || r < *it)
      return false;
    return true;
  }
  
  bool check(int node, int from, int to, int x, int y, int l, int r) {
    if(from == x && to == y)
      return check_node(node, l, r);
    else {
      int mid = (from + to) / 2;
      if(x <= mid && y <= mid)
        return check(node * 2, from, mid, x, y, l, r);
      else if(mid + 1 <= x && mid + 1 <= y)
        return check(node * 2 + 1, mid + 1, to, x, y, l, r);
      else 
        return (check(node * 2, from, mid, x, mid, l, r) |
               check(node * 2 + 1, mid + 1, to, mid + 1, y, l, r));
    }
  }
};
std::vector<std::vector<int>> g1, g2;

void dfs(int node, std::vector<std::vector<int>> &g, std::vector<std::vector<int>> &far,
         std::vector<int> &start, std::vector<int> &stop, std::vector<int> &level, int &ptr) {
  start[node] = ptr++;
  for(int h = 0; h < g[node].size();h++) {
    int to = g[node][h];
    far[0][to] = node;
    level[to] = level[node] + 1;
    dfs(to, g, far, start, stop, level, ptr);
  }
  stop[node] = ptr - 1;
}

void computefar(std::vector<std::vector<int>> &far, int n) {
  for(int i = 1;i < far.size(); i++) {
    far[i].resize(n);
    for(int j = 0; j < n; j++)
      far[i][j] = far[i - 1][far[i - 1][j]];
  }
}

std::vector<std::vector<int>> far, far2;

int expand(int node, std::vector<int> &level, std::vector<std::vector<int>> &far, int l, int r) {
  for(int h = far.size() - 1; 0 <= h; h--)
    if((1 << h) <= level[node]) {
      if(l <= far[h][node] && far[h][node] <= r)
        node = far[h][node];
    }
  return node;
}

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) {
  std::vector<std::vector<int>> g(N);
  for(int i = 0; i < X.size(); i++) {
    g[X[i]].push_back(Y[i]);
    g[Y[i]].push_back(X[i]);
  }
  Dsu dsu(N);
  g1.resize(N);
  g2.resize(N);

  for(int i = 0; i < N; i++) {
    for(int h = 0; h < g[i].size(); h++) {
      int to = dsu.jump(g[i][h]);
      if(to < i) {
        g1[i].push_back(to);
        dsu.unite(i, to);
      }
    }
  }
  dsu = Dsu(N);
  for(int i = N - 1; 0 <= i; i--) {
    for(int h = 0; h < g[i].size(); h++) {
      int to = dsu.jump(g[i][h]);
      if(i < to) {
        g2[i].push_back(to);
        dsu.unite(i, to);
      }
    }
  }
  int n = N;
  far.resize(1 + lgmax);
  far2.resize(1 + lgmax);
  far[0].resize(n);
  far2[0].resize(n);

  std::vector<int> start(n), stop(n), start2(n), stop2(n), level(n), level2(n);
  int ptr = 0;
  dfs(0, g2, far2, start2, stop2, level2,  ptr);
  ptr = 0;
  dfs(N - 1, g1, far, start, stop, level, ptr);
  
  computefar(far, n);
  computefar(far2, n);
  
  std::vector<int> aux(N);
  for(int i = 0; i < N; i++)
    aux[start[i]] = start2[i];
  SegmentTree aint(N);
  aint.build(1, 0, N - 1, aux);

  std::vector<int> sol(S.size());
  
  for(int h = 0; h < S.size(); h++) {
    int f2 = expand(S[h], level2, far2, L[h], N - 1);
    int f1 = expand(E[h], level, far, 0, R[h]);
    sol[h] = aint.check(1, 0, N - 1, start[f1], stop[f1], start2[f2], stop2[f2]);
  }
  return sol;
}

컴파일 시 표준 에러 (stderr) 메시지

werewolf.cpp: In function 'void dfs(int, std::vector<std::vector<int> >&, std::vector<std::vector<int> >&, std::vector<int>&, std::vector<int>&, std::vector<int>&, int&)':
werewolf.cpp:81:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |   for(int h = 0; h < g[node].size();h++) {
      |                  ~~^~~~~~~~~~~~~~~~
werewolf.cpp: In function 'void computefar(std::vector<std::vector<int> >&, int)':
werewolf.cpp:91:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |   for(int i = 1;i < far.size(); i++) {
      |                 ~~^~~~~~~~~~~~
werewolf.cpp: In function 'std::vector<int> check_validity(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
werewolf.cpp:113:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |   for(int i = 0; i < X.size(); i++) {
      |                  ~~^~~~~~~~~~
werewolf.cpp:122:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  122 |     for(int h = 0; h < g[i].size(); h++) {
      |                    ~~^~~~~~~~~~~~~
werewolf.cpp:132:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  132 |     for(int h = 0; h < g[i].size(); h++) {
      |                    ~~^~~~~~~~~~~~~
werewolf.cpp:163:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  163 |   for(int h = 0; h < S.size(); h++) {
      |                  ~~^~~~~~~~~~

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