Submission #195356

#	Time	Username	Problem	Language	Result	Execution time	Memory
195356		kdh9949	Werewolf (IOI18_werewolf)	C++17	15 / 100	1064 ms	173592 KiB

werewolf

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

const int N = 200005, LG = 18;

int n, q, p[2 * N], tim[2][2 * N], sgs[2][2 * N], sge[2][2 * N], cnt;
int sp[2][LG][N];
vector<int> e[N], t[2 * N];

struct Qry{ int i, s, e, sgn; };
vector<Qry> qv[N];
vector<int> pos[N];

int f(int x){ return p[x] = (x == p[x] ? x : f(p[x])); }

void aft(int id, int x){
  if(x < n){
    sgs[id][x] = sge[id][x] = ++cnt;
    return;
  }
  sgs[id][x] = N;
  for(int i : t[x]){
    aft(id, i);
    sgs[id][x] = min(sgs[id][x], sgs[id][i]);
    sge[id][x] = max(sge[id][x], sge[id][i]);
  }
}

struct Fen{
  int d[N];
  void u(int x){ for(; x < N; x += x & -x) d[x]++; }
  int g(int x){ int r = 0; for(; x; x &= x - 1) r += d[x]; return r; }
  int g(int s, int e){ return g(e) - g(s - 1); }
} F;

vector<int> check_validity(int N, vector<int> X, vector<int> Y,
  vector<int> S, vector<int> E, vector<int> L, vector<int> R) {  
  n = N;
  q = S.size();

  for(int i = 0; i < X.size(); i++){
    e[X[i]].push_back(Y[i]);
    e[Y[i]].push_back(X[i]);
  }

  iota(p, p + 2 * n, 0);
  cnt = n;
  for(int i = 1; i < n; i++){
    for(int j : e[i]){
      if(j > i || f(j) == f(i)) continue;
      int x = f(i), y = f(j);
      sp[0][0][x] = sp[0][0][y] = p[x] = p[y] = cnt;
      tim[0][cnt] = i;
      t[cnt].push_back(x);
      t[cnt].push_back(y);
      cnt++;
    }
  }
  cnt = 0;
  aft(0, 2 * n - 2);

  iota(p, p + 2 * n, 0);
  for(int i = 0; i < 2 * n; i++) t[i].clear();
  cnt = n;
  for(int i = n - 2; i >= 0; i--){
    for(int j : e[i]){
      if(j < i || f(j) == f(i)) continue;
      int x = f(i), y = f(j);
      sp[1][0][x] = sp[1][0][y] = p[x] = p[y] = cnt;
      tim[1][cnt] = i;
      t[cnt].push_back(x);
      t[cnt].push_back(y);
      cnt++;
    }
  }
  cnt = 0;
  aft(1, 2 * n - 2);

  for(int id = 0; id < 2; id++){
    sp[id][0][2 * n - 2] = 2 * n - 2;
    for(int j = 1; j < LG; j++){
      for(int k = 0; k < 2 * n - 1; k++){
        sp[id][j][k] = sp[id][j - 1][sp[id][j - 1][k]];
      }
    }
  }

  for(int i = 0; i < n; i++) pos[sgs[0][i]].push_back(sgs[1][i]);
  for(int i = 0; i < q; i++){
    int x = S[i];
    for(int j = LG-1; j >= 0; j--) if(tim[1][sp[1][j][x]] >= L[i]) x = sp[1][j][x];
    int y = E[i];
    for(int j = LG-1; j >= 0; j--) if(tim[0][sp[0][j][y]] <= R[i]) y = sp[0][j][y];

    qv[sgs[0][y] - 1].push_back({i, sgs[1][x], sge[1][x], -1});
    qv[sge[0][y]].push_back({i, sgs[1][x], sge[1][x], 1});
  }

  vector<int> res(q, 0);
  for(int i = 1; i <= n; i++){
    for(int j : pos[i]) F.u(j);
    for(Qry &j : qv[i]) res[j.i] += j.sgn * F.g(j.s, j.e);
  }

  for(int &i : res) i = !!i;
  return res;
}

Compilation message (stderr)

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:42:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < X.size(); i++){
                  ~~^~~~~~~~~~

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