Submission #235492

#	Time	Username	Problem	Language	Result	Execution time	Memory
235492		lyc	Werewolf (IOI18_werewolf)	C++14	15 / 100	4070 ms	348796 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 Query { int S, E, L, R, id; } query[mxQ];

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

    SegmentTree(int n): n(n) {}
    void update(int x, int u, int v, int s, int e, int p) {
        auto it = d[p].find(u);
        if (it != d[p].end()) d[p].erase(it);
        d[p].insert(v);
        if (s != e) {
            int m = (s+e)/2;
            if (x <= m) update(x,u,v,s,m,p*2);
            else update(x,u,v,m+1,e,p*2+1);
        }
    }
    inline void update(int x, int u, int v) { update(x,u,v,0,n-1,1); }
    bool query(int x, int y, int v, int s, int e, int p) {
        if (s == x && e == y) {
            return d[p].lower_bound(v) != d[p].upper_bound(v);
        } else {
            int m = (s+e)/2;
            if (y <= m) return query(x,y,v,s,m,p*2);
            if (x >  m) return query(x,y,v,m+1,e,p*2+1);
            return query(x,m,v,s,m,p*2) || query(m+1,y,v,m+1,e,p*2+1);
        }
    }
    inline bool query(int x, int y, int v) { return query(x,y,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;
    }
} *KT;

struct UnionFind {
    int pa[mxN];
    set<int> child[mxN];
    UnionFind(int n) {
        FOR(i,0,n-1){
            pa[i] = i;
            child[i].insert(i);
            ST->update(KT->pre[i],-1,i);
        }
    }
    int finds(int i) { return (pa[i] == i) ? i : (pa[i] = finds(pa[i])); }
    bool unions(int i, int j) {
        int x = finds(i), y = finds(j);
        if (x != y) {
            if (SZ(child[x]) < SZ(child[y])) swap(x,y);
            for (auto& u : child[y]) {
                assert(pa[u] == y);
                pa[u] = x;
                ST->update(KT->pre[u],y,x);
                child[x].insert(u);
            }
            child[y].clear();
            return true;
        } return false;
    }
} *UF;

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]) };
    }
    FOR(i,0,Q-1){
        query[i] = (Query){ S[i], E[i], L[i], R[i], 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;
            });
    sort(query,query+Q,[](Query a, Query b){
            if (a.R == b.R) return a.id < b.id;
            return a.R < b.R;
            });

    KT = new KruskalTree(N);
    FOR(i,0,M-1){
        KT->unions(edge[i].X,edge[i].Y,edge[i].W);
    }
    KT->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;
            });
    ST = new SegmentTree(2*N);
    UF = new UnionFind(N);
    vector<int> ans(Q);
    int ei = 0;
    FOR(i,0,Q-1){
        while (ei < M && edge[ei].W <= query[i].R) {
            UF->unions(edge[ei].X,edge[ei].Y);
            ++ei;
        }
        int ep = UF->finds(query[i].E);
        int sp = KT->findFaGE(query[i].S,query[i].L);
        //TRACE(ep _ sp);
        ans[query[i].id] = ST->query(KT->pre[sp],KT->pst[sp],ep);
    }
    return ans;
}

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