Submission #276865

#	Time	Username	Problem	Language	Result	Execution time	Memory
276865		Haunted_Cpp	Werewolf (IOI18_werewolf)	C++17	0 / 100	1587 ms	103676 KiB

werewolf

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

const int MAX_N = 2e5 + 5;
const int MAX_K = 25 + 5;
 
class SparseTable {
private:
  vector<vector<int>> mx;
  vector<vector<int>> mn;
  vector<int> LOG;
  void build(const vector<int> &arr) {
    const int N = arr.size();
    LOG.resize(N);
    for (int i = 1; i <= N; i++) {
      LOG[i] = log2(i);
    }
    for (int i = 0; i < N; i++) {
      mx[i][0] = mn[i][0] = arr[i];
    }
    for (int j = 1; j < MAX_K; j++) {
      for (int i = 0; i + (1 << j) <= N; i++) {
        mn[i][j] = min(mn[i][j - 1], mn[i + (1 << (j - 1))][j - 1]);
        mx[i][j] = max(mx[i][j - 1], mx[i + (1 << (j - 1))][j - 1]);
      }
    }
  }
public:
  SparseTable(const vector<int> &arr) {
    mx = vector<vector<int>> (MAX_N, vector<int>(MAX_K, -1));
    mn = vector<vector<int>> (MAX_N, vector<int>(MAX_K, 1e9));
    LOG.resize(MAX_N);
    build(arr);
  }
  int get_max(int ql, int qr) {
    const int T = (qr - ql + 1);
    const int P = LOG[T];
    return max(mx[ql][P], mx[qr - (1 << P) + 1][P]);
  }
  int get_min(int ql, int qr) {
    const int T = (qr - ql + 1);
    const int P = LOG[T];
    return min(mn[ql][P], mn[qr - (1 << P) + 1][P]);
  }
};
 

vector<vector<int>> g(MAX_N);
 
vector<int> in(MAX_N);
vector<int> out(MAX_N);
vector<int> euler = {0};

vector<bool> vis(MAX_N, false);
 
int Time = 0;
 
void dfs(int node) {
  vis[node] = true;
  in[node] = ++Time;
  euler.emplace_back(node);
  for (auto to : g[node]) {
    if (!vis[to]) {
      vis[to] = true;
      dfs(to);
    }
  }
  out[node] = Time;
}
 
vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
  vector<int> deg(N);
  for (int i = 0; i < (int) X.size(); i++) {
    const int st = X[i];
    const int et = Y[i];
    ++deg[st];
    ++deg[et];
    g[st].emplace_back(et);
    g[et].emplace_back(st);
  }
  int root = -1;
  for (int i = 0; i < N; i++) {
    if (deg[i] == 1) {
      root = i;
      break;
    }
  }
  dfs(root);
  SparseTable seg(euler);
  int Q = S.size();
  vector<int> A(Q, 0);
  for (int i = 0; i < Q; i++) {
    int cidade_inicial = S[i];
    int cidade_final = E[i];
    const int evitar_humano = L[i];
    const int evitar_lobo = R[i];
    if (cidade_inicial < evitar_humano) {
      A[i] = 0;
      continue;
    }
    if (cidade_final > evitar_lobo) {
      A[i] = 0;
      continue;
    }
    
    if (in[cidade_inicial] < in[cidade_final]) {
      int lo = in[cidade_inicial];
      int hi = N;
      while(lo < hi) {
        const int mid = lo + (hi - lo) / 2;
        if (seg.get_min(in[cidade_inicial], mid) < evitar_humano) hi = mid;
        else lo = mid + 1;
      }
      const int rightmost_inicial = max(in[cidade_inicial], hi - 1);
      lo = 0;
      hi = in[cidade_final];
      while(lo < hi) {
        const int mid = lo + (hi - lo) / 2 + 1;
        if (seg.get_max(mid, in[cidade_final]) > evitar_lobo) lo = mid;
        else hi = mid - 1;
      }
      const int leftmost_final = min(in[cidade_final], lo + 1);
      A[i] = (leftmost_final <= rightmost_inicial);
    } else {
      int lo = 0;
      int hi = in[cidade_inicial];
      while(lo < hi) {
        const int mid = lo + (hi - lo) / 2 + 1;
        if (seg.get_min(mid, in[cidade_inicial]) < evitar_humano) lo = mid;
        else hi = mid - 1;
      }
      const int leftmost_inicial = min(in[cidade_inicial], lo + 1);
      lo = in[cidade_final];
      hi = N;
      while(lo < hi) {
        const int mid = lo + (hi - lo) / 2;
        if (seg.get_max(in[cidade_final], mid) > evitar_lobo) hi = mid;
        else lo = mid + 1;
      }
      const int rightmost_final = max(in[cidade_final], hi - 1);
      A[i] = (rightmost_final >= leftmost_inicial);
    }
  }
  return A;
}

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