Submission #208795

#	Time	Username	Problem	Language	Result	Execution time	Memory
208795		anonymous	Werewolf (IOI18_werewolf)	C++14	0 / 100	1028 ms	131636 KiB

werewolf

#include "werewolf.h"
#include <vector>
#include <utility>
#include <algorithm>
#define MAXN 200005
using namespace std;

class DSU { //1 indexed
    int par[MAXN], sz;
    vector<int> T[MAXN];
public:
    int anc[MAXN][20], ID[MAXN][2], seq = 1;
    int Find(int x) {
        return(par[x] == x ? x : par[x] = Find(par[x]));
    }
    void Union(int x, int y) {
        int p1 = Find(x), p2 = Find(y);
        if (p1 == p2) {return;}
        if (!anc[p1][0]) {
            anc[p1][0]=p2;
            T[p2].push_back(p1);
        }
        par[p1]=p2;
    }
    void Init(int n) {
        sz = n;
        for (int i=1; i <= n; i++) {
            par[i]=i;
        }
    }
    void makeJump() {
        for (int i=1; i<20; i++) {
            for (int j=1; j<=sz; j++) {
                anc[j][i] = anc[anc[j][i-1]][i];
            }
        }
    }
    void ET(int u) {
        ID[u][0] = seq;
        seq++;
        for (auto v: T[u]) {ET(v);}
        ID[u][1] = seq - 1;
    }
    int range(int v, int cap, bool t) { //t = 1 means all values at most cap
        for (int i=19; i>=0; i--) { //t = 0 means all values at least cap
            if (t && anc[v][i] && anc[v][i] <= cap) {
                v = anc[v][i];
            } else if ((!t) && anc[v][i] && anc[v][i] >= cap) {
                v = anc[v][i];
            }
        }
        if (t && anc[v][0] && anc[v][0] <= cap) {
            v = anc[v][0];
        } else if ((!t) && anc[v][0] && anc[v][0] >= cap) {
            v = anc[v][0];
        }
        return(v);
    }
} Tmin, Tmax; //semi-Kruskal reconstruction trees: doesn't need to add new node

class PersistentSegtree {
    int ST[MAXN * 30][3];
    int R[MAXN], X[MAXN], pt = 1, ver = 1;
public:
    int upd(int ind, int l, int r, int cur) {
        if (ind < l || ind > r) {return(cur);}
        if (l == r) {
            ST[pt][0] = ST[cur][0] + 1, pt++;
            return(pt-1);
        } else {
            int tmp = pt, mid = (l + r) >> 1;
            pt++;
            ST[tmp][1] = upd(ind, l, mid, ST[cur][1]);
            ST[tmp][2] = upd(ind, mid+1, r, ST[cur][2]);
            ST[tmp][0] = ST[ST[tmp][1]][0] + ST[ST[tmp][2]][0];
            return(tmp);
        }
    }
    int ask(int lo, int hi, int l, int r, int cur) {
        if (hi < l || lo > r || !cur) {return(0);}
        if (lo <= l && hi >= r) {return(ST[cur][0]);}
        else {
            int mid = (l + r) >> 1;
            return(ask(lo, hi, l, mid, ST[cur][1]) +
                   ask(lo, hi, mid+1, r, ST[cur][2]));
        }
    }
    void add(int x, int y) {
        X[ver] = x;
        R[ver] = upd(y, 1, MAXN, R[ver-1]);
        ver++;
    }
    int get(int x) { //find largest index i that X[i] not exceeding x
        int lo = 0, hi = ver;
        while (lo + 1 != hi) {
            int mid = (lo + hi) >> 1;
            if (X[mid] <= x) {lo = mid;}
            else {hi = mid;}
        }
        return(lo);
    }
    int Sum(int xlo, int ylo, int xhi, int yhi) {
        int ql = get(xlo) - 1, qr = get(xhi);
        return(ask(ylo, yhi, 1, MAXN, R[qr]) - ask(ylo, yhi, 1, MAXN, R[ql]));
    }
} PST;

vector<int> adj[MAXN];
vector<pair<int,int> > pts;

vector<int> check_validity(int N, vector<int> X, vector<int> Y,
                                vector<int> S, vector<int> E,
                                vector<int> L, vector<int> R) {
  int Q = S.size(), M = X.size();
  Tmin.Init(N), Tmax.Init(N);
  for (int i=0; i<M; i++) {
    adj[X[i]+1].push_back(Y[i]+1);
    adj[Y[i]+1].push_back(X[i]+1);
  }
  for (int i=1; i<=N; i++) { //min bottleneck (minimise max wt)
    for (auto v: adj[i]) {
        if (i > v) {
            Tmin.Union(v,i);
        }
    }
  }
  for (int i=N; i>=1; i--) { //max bottleneck (max min wt)
    for (auto v: adj[i]) {
        if (i < v) {
            Tmax.Union(v,i);
        }
    }
  }
  Tmin.ET(N), Tmax.ET(1);
  Tmin.makeJump(), Tmax.makeJump();
  for (int i=1; i<=N; i++) {
    pts.push_back({Tmin.ID[i][0], Tmax.ID[i][0]});
  }
  sort(pts.begin(), pts.end());
  for (auto P: pts) {
    PST.add(P.first, P.second);
  }
  vector<int> A;
  for (int i = 0; i < Q; ++i) {
    int s = S[i] + 1, e = E[i] + 1, l = L[i] + 1, r = R[i] + 1;
    int s2 = Tmax.range(s, l, false), e2 = Tmin.range(e, r, true);
    int xl = Tmin.ID[e2][0], xr = Tmin.ID[e2][1];
    int yl = Tmax.ID[s2][0], yr = Tmax.ID[s2][1];
    if (PST.Sum(xl, yl, xr, yr)) {A.push_back(1);}
    else {A.push_back(0);}

  }
  return A;
}

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