Submission #76581

#	Time	Username	Problem	Language	Result	Execution time	Memory
76581		Xylofo	Werewolf (IOI18_werewolf)	C++14	100 / 100	1886 ms	235564 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i = a; i < b; ++i)
using vi = vector<int>;
using graph = vector<vi>;

const int LG = 28;

struct Tree {
  graph t;
  vi p;
  vector<vi> fastUp;
  int fd(int a) { return p[a] == a ? a : p[a] = fd(p[a]); }
  int n;
  vi start, end, fromP;
  int root;
  Tree(int rev, const graph &g) {
    n = g.size();
    t.resize(n);
    fastUp.assign(n, vi(LG,-1));
    p.resize(n);
    fromP = start = end = p;
    rep(i,0,n) p[i] = i;
    for(int i = rev*(n-1); i >= 0 && i < n; i += 1 - 2*rev) {
      for(int j:g[i]) if(rev ^ (j < i)) {
        int jj = fd(j);
        if(jj != i) {
          p[jj] = i;
          t[i].push_back(jj);
        }
      }
    }
    root = (1-rev)*(n-1);
    int T = 0;
    dfs(root, root, T);
  }
  void dfs(int x, int p, int&T) {
    fastUp[x][0] = p;
    rep(k,0,LG-1) fastUp[x][k+1] = fastUp[fastUp[x][k]][k];

    start[x] = T;
    fromP[T] = x;
    ++T;
    for(int y:t[x]) if(y != p) dfs(y, x, T);
    end[x] = T;
  }
};

namespace ST {
  struct node {
    int mx;
    node *l;
    node *r;
  } nil{-1,nullptr,nullptr};
  int query(int l, int r, int L, int R, node *cur) {
    if(!cur) return -1;
    if(r <= L || R <= l) return -1;
    if(l <= L && R <= r) return cur->mx;
    int M = (L+R)/2;
    return max(query(l,r,L,M,cur->l), query(l,r,M,R,cur->r));
  }
  node* update(int pos, int x, int L, int R, node *cur) {
    if(pos < L || R <= pos) return cur;
    if(!cur) cur = &nil;
    if(L+1 == R) return new node{x,nullptr,nullptr};
    int M = (L+R)/2;
    assert(cur);
    node *l = update(pos,x,L,M,cur->l);
    node *r = update(pos,x,M,R,cur->r);
    return new node{max(l ? l->mx : -1, r ? r->mx : -1), l, r};
  }
}

struct P {
  vi f;
  int n;
  vector<ST::node*> pst;
  P(const vi& p1, const vi& p2) {
    // f(x) = p2^{-1}(p1(x)))
    // (x in [l1,r1] and f(x) in [l2,r2]) => (p1[x] == p2[f(x)] satisfies stuff)
    n = p1.size();
    f.resize(n);
    pst.resize(n+1,nullptr);
    vi p2inv(n), finv(n);
    rep(i,0,n) p2inv[p2[i]] = i;
    rep(i,0,n) f[i] = p2inv[p1[i]];
    rep(i,0,n) finv[f[i]] = i;
    rep(i,0,n) pst[i+1] = update(finv[i], i, 0, n, pst[i]);
  }
  // p1[l1..r1) intersect p2[l2..r2)
  bool slv(int l1, int r1, int l2, int r2) {
    int mx = query(l1,r1,0,n,pst[r2]);
    return mx >= l2;
  }
};

vi check_validity(int N, vi X, vi Y, vi S, vi E, vi L, vi R) {
  int n = N;
  int q = S.size();
  vi A(q);

  graph g(n);
  rep(i,0,X.size()) {
    g[X[i]].push_back(Y[i]);
    g[Y[i]].push_back(X[i]);
  }
  Tree up(0, g), dw(1, g);
  P perm(up.fromP, dw.fromP);
  rep(i,0,q) {
    int s = S[i];
    int e = E[i];
    int l = L[i];
    int r = R[i];
    // ----------------|
    // ... e ... l ... r ... s ...
    //           |----------------
    // find representatives of subtrees
    for(int k = LG-1; k >= 0; --k) {
      if(dw.fastUp[s][k] >= l) s = dw.fastUp[s][k];
      if(up.fastUp[e][k] <= r) e = up.fastUp[e][k];
    }
    int l1 = up.start[e], r1 = up.end[e];
    int l2 = dw.start[s], r2 = dw.end[s];
    A[i] = perm.slv(l1, r1, l2, r2);
  }
  return A;
}

Compilation message (stderr)

werewolf.cpp: In function 'vi check_validity(int, vi, vi, vi, vi, vi, vi)':
werewolf.cpp:4:37: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i,a,b) for(int i = a; i < b; ++i)
werewolf.cpp:104:7:
   rep(i,0,X.size()) {
       ~~~~~~~~~~~~                   
werewolf.cpp:104:3: note: in expansion of macro 'rep'
   rep(i,0,X.size()) {
   ^~~

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