Submission #829378

#	Time	Username	Problem	Language	Result	Execution time	Memory
829378		Josia	Werewolf (IOI18_werewolf)	C++17	100 / 100	1467 ms	150936 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>

using namespace std;


int N, M, Q;
vector<vector<int>> graph;
vector<int> human, wolf;
vector<vector<int>> treeWolf;
vector<vector<int>> treeHuman;
vector<pair<int, int>> prepostWolf;
vector<pair<int, int>> prepostHuman;
vector<vector<int>> jumpWolf;
vector<vector<int>> jumpHuman;


struct ufToMakeArrays {
    vector<int> chefs;
    void init() {
        chefs.resize(N);
        for (int i = 0; i<N; i++) {
            chefs[i] = i;
        }
    }

    int find(int x) {
        if (chefs[x] == x) return x;
        return chefs[x] = find(chefs[x]);
    }

    void unite(int a, int b, bool minmax) {
        a = find(a);
        b = find(b);
        if (a == b) return;
        if (minmax?a<b:a>b) swap(a, b);

        chefs[b] = a;
    }


    void makeTreeWolf() {
        init();
        for (int i = 0; i<N; i++) {
            for (int u: graph[i]) {
                if (u >= i) continue;
                if (find(u) == find(i)) continue;
                treeWolf[find(i)].push_back(find(u));
                treeWolf[find(u)].push_back(find(i));
                unite(u, i, 1);
            }
        }
    }


    void makeTreeHuman() {
        init();
        for (int i = N-1; i>=0; i--) {
            for (int u: graph[i]) {
                if (u <= i) continue;
                if (find(u) == find(i)) continue;
                treeHuman[find(i)].push_back(find(u));
                treeHuman[find(u)].push_back(find(i));
                unite(u, i, 0);
            }
        }
    }

    void dfsWolf(int v, int p) {
        jumpWolf[0][v] = p;
        prepostWolf[v].first = wolf.size();
        wolf.push_back(v);
        for (int i: treeWolf[v]) {
            if (i == p) continue;
            dfsWolf(i, v);
        }
        prepostWolf[v].second = wolf.size()-1;
    }

    void dfsHuman(int v, int p) {
        jumpHuman[0][v] = p;
        prepostHuman[v].first = human.size();
        human.push_back(v);
        for (int i: treeHuman[v]) {
            if (i == p) continue;
            dfsHuman(i, v);
        }
        prepostHuman[v].second = human.size()-1;
    }


    void make() {
        treeHuman.assign(N, vector<int>()); treeWolf.assign(N, vector<int>());

        makeTreeWolf(); makeTreeHuman();

        wolf.clear(); human.clear();

        prepostHuman.assign(N, {0, 0});
        prepostWolf.assign(N, {0, 0});

        jumpHuman.assign(20, vector<int>(N));
        jumpWolf.assign(20, vector<int>(N));

        dfsWolf(N-1, -1); dfsHuman(0, -1);


        for (int i = 1; i<20; i++) {
            for (int j = 0; j<N; j++) {
                jumpHuman[i][j] = jumpHuman[i-1][j] == -1 ? -1 : jumpHuman[i-1][jumpHuman[i-1][j]];
                jumpWolf[i][j] = jumpWolf[i-1][j] == -1 ? -1 : jumpWolf[i-1][jumpWolf[i-1][j]];
            }
        }
    }
};



vector<int> wolfInv, humanInv, humanToWolf;

void makeInv() {
    wolfInv.resize(N);
    humanInv.resize(N);
    for (int i = 0; i<N; i++) wolfInv[wolf[i]] = i;
    for (int i = 0; i<N; i++) humanInv[human[i]] = i;

    humanToWolf.resize(N);
    for (int i = 0; i<N; i++) humanToWolf[i] = wolfInv[human[i]];
}


struct seg {
    struct node {
        int val=0, left=-1, right=-1;
    };

    vector<node> tree = {node()};

    void build(int v, int rl, int rr) {
        if (rl == rr) return;

        tree[v].left = tree.size();
        tree.push_back(node());
        tree[v].right = tree.size();
        tree.push_back(node());

        int rm = (rl + rr)/2;

        build(tree[v].left, rl, rm);
        build(tree[v].right, rm+1, rr);
    }

    int update(int v, int rl, int rr, int pos, int x) {
        if (rl == rr) {
            int newV = tree.size();
            tree.push_back(tree[v]);

            tree[newV].val += x;
            return newV;
        }
        int rm = (rl + rr)/2;

        int newV = tree.size();
        tree.push_back(tree[v]);

        if (pos <= rm) tree[newV].left = update(tree[newV].left, rl, rm, pos, x);
        else tree[newV].right = update(tree[newV].right, rm+1, rr, pos, x);

        tree[newV].val = tree[tree[newV].left].val + tree[tree[newV].right].val;

        return newV;
    }

    int query(int v, int rl, int rr, int ql, int qr) {
        if (ql > qr) return 0;
        if (rl == ql && rr == qr) return tree[v].val;

        int rm = (rl + rr)/2;

        return query(tree[v].left, rl, rm, ql, min(qr, rm)) + query(tree[v].right, rm+1, rr, max(ql, rm+1), qr);
    }

    vector<int> times;

    int queryDouble(int hl, int hr, int wl, int wr) {
        // cerr << query(times[wr], 0, N-1, hl, hr) << " - " << query(times[wl-1], 0, N-1, hl, hr) << "\n";
        // return query(times[wr], 0, N-1, hl, hr) - (wl==0?0:query(times[wl-1], 0, N-1, hl, hr));
        return query(times[hr], 0, N-1, wl, wr) - (hl==0?0:query(times[hl-1], 0, N-1, wl, wr));
    }

    void init() {
        build(0, 0, N-1);
        for (int i = 0; i<N; i++) {
            times.push_back(update(i==0?0:times.back(), 0, N-1, humanToWolf[i], 1));
        }
        assert((int)times.size() == N);
    }
};


pair<int, int> getRangeHuman(int pos, int lim) {
    for (int i = 19; i>=0; i--) {
        if (jumpHuman[i][pos] != -1 && jumpHuman[i][pos] >= lim) {
            pos = jumpHuman[i][pos];
        }
    }
    return prepostHuman[pos];
}

pair<int, int> getRangeWolf(int pos, int lim) {
    for (int i = 19; i>=0; i--) {
        if (jumpWolf[i][pos] != -1 && jumpWolf[i][pos] <= lim) {
            pos = jumpWolf[i][pos];
        }
    }
    return prepostWolf[pos];
}


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;
    M = X.size();
    Q = S.size();

    graph.clear();
    graph.resize(N);
    for (int i = 0; i<M; i++) {
        graph[X[i]].push_back(Y[i]);
        graph[Y[i]].push_back(X[i]);
    }

    ufToMakeArrays blub;
    blub.make();

    makeInv();


    // for (int i: human) cerr << i << " ";
    // cerr << "\n";
    // for (int i: wolf) cerr << i << " ";
    // cerr << "\n";


    seg tree;

    tree.init();



    vector<int> res(Q, 0);

    for (int i = 0; i<Q; i++) {
        // cerr << humanInv[S[i]] << "\n";
        pair<int, int> rangeHuman = getRangeHuman(S[i], L[i]);
        pair<int, int> rangeWolf = getRangeWolf(E[i], R[i]);

        // cerr << rangeHuman.first << " " << rangeHuman.second << " " << rangeWolf.first << " " << rangeWolf.second << "\n";

        // cerr << tree.queryDouble(rangeHuman.first, rangeHuman.second, rangeWolf.first, rangeWolf.second) << "\n";

        if (tree.queryDouble(rangeHuman.first, rangeHuman.second, rangeWolf.first, rangeWolf.second)) res[i] = 1;
    }
    return res;
}

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