Submission #235553

#	Time	Username	Problem	Language	Result	Execution time	Memory
235553		lyc	Werewolf (IOI18_werewolf)	C++14	100 / 100	2090 ms	203368 KiB

werewolf

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

#define TRACE(x) cout << #x << " :: " << x << endl;
#define _ << " " <<
#define FOR(i,a,b) for (int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for (int i=(a);i>=(b);--i)
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(), (x).end()

const int mxN = 2e5+5;
const int lgN = 17;
const int mxM = 4e5+5;
const int mxQ = 2e5+5;

int N, M, Q;
struct Edge { int X, Y, W; } edge[mxM];

struct SegmentTree {
    vector<int> d[8*mxN];
    int n;

    SegmentTree(int n): n(n) {}
    void update(int x, int v, int s, int e, int p) {
        if (s == e) {
            d[p].push_back(v);
        } else {
            int m = (s+e)/2;
            if (x <= m) update(x,v,s,m,p*2);
            else update(x,v,m+1,e,p*2+1);
        }
    }
    inline void update(int x, int v) { update(x,v,0,n-1,1); }
    void build(int s, int e, int p) {
        if (s != e) {
            int m = (s+e)/2;
            build(s,m,p*2);
            build(m+1,e,p*2+1);
            vector<int>& a = d[2*p], b = d[2*p+1];
            for (int i = 0, j = 0; i < SZ(a) || j < SZ(b); ) {
                if (i < SZ(a) && (j == SZ(b) || a[i] < b[j])) d[p].push_back(a[i++]);
                else d[p].push_back(b[j++]);
            }
        }
    }
    inline void build() { build(0,n-1,1); }
    int query(int x, int y, int u, int v, int s, int e, int p) {
        if (s == x && e == y) {
            return lower_bound(ALL(d[p]),v+1) - lower_bound(ALL(d[p]),u);
        } else {
            int m = (s+e)/2;
            if (y <= m) return query(x,y,u,v,s,m,p*2);
            if (x >  m) return query(x,y,u,v,m+1,e,p*2+1);
            return query(x,m,u,v,s,m,p*2) + query(m+1,y,u,v,m+1,e,p*2+1);
        }
    }
    inline int query(int x, int y, int u, int v) { return query(x,y,u,v,0,n-1,1); }
} *ST;

struct KruskalTree {
    static const int mxV = 2*mxN;
    int pa[mxV], v[mxV];
    vector<int> al[mxV];
    int cnt, fa[mxV][lgN+1], pre[mxV], pst[mxV], dfsT;

    KruskalTree(int n) {
        FOR(i,0,n-1){
            pa[i] = i;
            v[i] = -1;
        }
        cnt = n;
        memset(fa,-1,sizeof fa);
    }
    int finds(int i) { return (pa[i] == i) ? i : (pa[i] = finds(pa[i])); }
    bool unions(int i, int j, int w) {
        int x = finds(i), y = finds(j);
        if (x != y) {
            pa[cnt] = cnt;
            v[cnt] = w;
            al[cnt].push_back(x);
            al[cnt].push_back(y);
            fa[x][0] = cnt;
            fa[y][0] = cnt;
            pa[x] = pa[y] = cnt;
            ++cnt;
            return true;
        } return false;
    }
    void dfs(int u) {
        pre[u] = dfsT++;
        FOR(k,1,lgN){
            if (fa[u][k-1] == -1) fa[u][k] = -1;
            else fa[u][k] = fa[fa[u][k-1]][k-1];
        }
        for (int v : al[u]) { dfs(v); }
        pst[u] = dfsT-1;
        //TRACE(u _ v[u] _ pre[u] _ pst[u]);
    }
    void init() {
        dfsT = 0;
        dfs(cnt-1);
    }
    int findFaGE(int u, int val) {
        RFOR(k,lgN,0){
            if (fa[u][k] != -1 && v[fa[u][k]] >= val) u = fa[u][k];
        }
        return u;
    }
} *KT1, *KT2;

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) {
    N = _N, M = SZ(X), Q = SZ(S);
    FOR(i,0,M-1){
        edge[i] = (Edge){ X[i], Y[i], min(X[i],Y[i]) };
    }

    sort(edge,edge+M,[](Edge a, Edge b){
            if (a.W == b.W) return (a.X == b.X ? a.Y < b.Y : a.X < b.X);
            return a.W > b.W;
            });

    KT1 = new KruskalTree(N);
    FOR(i,0,M-1){
        KT1->unions(edge[i].X,edge[i].Y,edge[i].W);
    }
    KT1->init();

    FOR(i,0,M-1) edge[i].W = max(edge[i].X,edge[i].Y);
    sort(edge,edge+M,[](Edge a, Edge b){
            if (a.W == b.W) return (a.X == b.X ? a.Y < b.Y : a.X < b.X);
            return a.W < b.W;
            });
    KT2 = new KruskalTree(N);
    FOR(i,0,M-1){
        KT2->unions(edge[i].X,edge[i].Y,-edge[i].W);
    }
    KT2->init();

    ST = new SegmentTree(2*N);
    FOR(i,0,N-1){
        //TRACE(i _ KT1->pre[i] _ KT2->pre[i]);
        ST->update(KT1->pre[i],KT2->pre[i]);
    }
    ST->build();

    vector<int> ans(Q);
    FOR(i,0,Q-1){
        int sp = KT1->findFaGE(S[i],L[i]);
        int ep = KT2->findFaGE(E[i],-R[i]);
        //TRACE(sp _ KT1->pre[sp] _ KT1->pst[sp] _ ep _ KT2->pre[ep] _ KT2->pst[ep]);
        ans[i] = ST->query(KT1->pre[sp],KT1->pst[sp],KT2->pre[ep],KT2->pst[ep]) > 0;
    }
    return ans;
}

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