Submission #320440

#	Time	Username	Problem	Language	Result	Execution time	Memory
320440		mihai145	늑대인간 (IOI18_werewolf)	C++14	100 / 100	3044 ms	314656 KiB

werewolf

#include "werewolf.h"
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>

const int NMAX = 2e5;
const int LOGMAX = 18;

int _N, M, Q;

std::vector <int> g[NMAX + 2];

int dadSmall[NMAX + 2], dadBig[NMAX + 2];
std::vector <int> dsuSmall[NMAX + 2]; ///in subtree[x] am toate nodurile reach-able <= x
std::vector <int> dsuBig[NMAX + 2]; ///in subree[x] am toate nodurile reach-able >= x

int RootSmall(int x) {
    if(x == dadSmall[x])
        return x;

    return dadSmall[x] = RootSmall(dadSmall[x]);
}

int RootBig(int x) {
    if(x == dadBig[x])
        return x;

    return dadBig[x] = RootBig(dadBig[x]);
}

void JoinSmall(int p, int q) {
    int rootP = RootSmall(p);
    int rootQ = RootSmall(q);

    if(rootP == rootQ)
        return ;

    if(rootP > rootQ) {
        dsuSmall[rootP].push_back(rootQ);
        dadSmall[rootQ] = rootP;
    } else {
        dsuSmall[rootQ].push_back(rootP);
        dadSmall[rootP] = rootQ;
    }
}

void JoinBig(int p, int q) {
    int rootP = RootBig(p);
    int rootQ = RootBig(q);

    if(rootP == rootQ)
        return ;

    if(rootP < rootQ) {
        dsuBig[rootP].push_back(rootQ);
        dadBig[rootQ] = rootP;
    } else {
        dsuBig[rootQ].push_back(rootP);
        dadBig[rootP] = rootQ;
    }
}

int liftSmall[LOGMAX + 1][NMAX + 2], liftBig[LOGMAX + 1][NMAX + 2];

std::vector <int> tourSmall;
int lfSmall[NMAX + 2], rgSmall[NMAX + 2];

std::vector <int> tourBig;
int lfBig[NMAX + 2], rgBig[NMAX + 2];

void TraverseSmall(int node) {
    //std::cout << node << '\n';
    lfSmall[node] = (int)tourSmall.size();
    tourSmall.push_back(node);

    for(auto it : dsuSmall[node])
        TraverseSmall(it);

    rgSmall[node] = (int)tourSmall.size() - 1;
}

void TraverseBig(int node) {
    //std::cout << node << '\n';
    lfBig[node] = (int)tourBig.size();
    tourBig.push_back(node);

    for(auto it : dsuBig[node])
        TraverseBig(it);

    rgBig[node] = (int)tourBig.size() - 1;
}

void BuildDSUs() {
    for(int i = 0; i < _N; i++) {
        dadSmall[i] = i;
        dadBig[i] = i;
    }

    for(int i = 1; i < _N; i++)
        for(auto it : g[i])
            if(it < i)
                JoinSmall(it, i);

    for(int i = _N - 2; i >= 0; i--)
        for(auto it : g[i])
            if(it > i)
                JoinBig(it, i);

    /*
    std::cout << "DSU Small:\n";
    for(int i = 0; i < N; i++)
        for(auto it : dsuSmall[i])
            std::cout << i << ' ' << it << '\n';
    std::cout << "DSU Big:\n";
    for(int i = 0; i < N; i++)
        for(auto it : dsuBig[i])
            std::cout << i << ' ' << it << '\n';
    */

    TraverseSmall(_N - 1);
    TraverseBig(0);

    /*
    std::cout << "Tour Small\n";
    for(auto it : tourSmall)
        std::cout << it << ' ';
    std::cout << '\n';

    for(int i = 0; i < _N; i++)
        std::cout << lfSmall[i] << ' ' << rgSmall[i] << '\n';

    std::cout << "Tour Big\n";
    for(auto it : tourBig)
        std::cout << it << ' ';
    std::cout << '\n';

    for(int i = 0; i < _N; i++)
        std::cout << lfBig[i] << ' ' << rgBig[i] << '\n';
    */
}

void PrecomputeLift() {
    for(int l = 0; l <= LOGMAX; l++)
        for(int i = 0; i < _N; i++)
            liftSmall[l][i] = liftBig[l][i] = -1;

    //liftSmall[0][N - 1] = -1;
    for(int i = 0; i < _N; i++)
        for(auto it : dsuSmall[i])
            liftSmall[0][it] = i;

    for(int l = 1; l <= LOGMAX; l++)
        for(int i = 0; i < _N; i++)
            if(liftSmall[l - 1][i] != -1)
                liftSmall[l][i] = liftSmall[l - 1][liftSmall[l - 1][i]];

    //liftBig[0][0] = -1;
    for(int i = 0; i < _N; i++)
        for(auto it : dsuBig[i])
            liftBig[0][it] = i;

    for(int l = 1; l <= LOGMAX; l++)
        for(int i = 0; i < _N; i++)
            if(liftBig[l - 1][i] != -1)
                liftBig[l][i] = liftBig[l - 1][liftBig[l - 1][i]];
    /*
    std::cout << liftSmall[0][1] << ' ' << liftSmall[1][1] << ' ' << liftSmall[2][1] << ' ' << liftSmall[3][1] << '\n';
    std::cout << liftSmall[1][0] << ' ' << liftSmall[2][3] << '\n';

    std::cout << liftBig[0][2] << ' ' << liftBig[1][2] << '\n';
    std::cout << liftBig[1][4] << ' ' << liftBig[5][4] << '\n';
    */
}

struct Query {
    int l1, r1, l2, r2;
    int index;
};

std::vector < Query > queries;

int StoreQuery(int st, int en, int L, int R, int index) {

    ///All nodes reach-able from st, >= L
    int rootBig = st;
    for(int l = LOGMAX; l >= 0; l--)
        if(liftBig[l][rootBig] != -1 && liftBig[l][rootBig] >= L) {
            rootBig = liftBig[l][rootBig];
        }

    ///All nodes reach-able from en, <= R
    int rootSmall = en;
    for(int l = LOGMAX; l >= 0; l--)
        if(liftSmall[l][rootSmall] != -1 && liftSmall[l][rootSmall] <= R) {
            rootSmall = liftSmall[l][rootSmall];
        }

    queries.push_back({lfSmall[rootSmall], rgSmall[rootSmall], lfBig[rootBig], rgBig[rootBig], index});

    /*
    std::cout << "Nodes reach-able from " << st << " with >= " << L << '\n';
    dfsBig(rootBig);
    std::cout << "---\n";

    std::cout << "Nodes reach-able from " << en << " with <= " << R << '\n';
    dfsSmall(rootSmall);
    std::cout << "---\n";
    */

    return 1;
}

int posTourSmall[NMAX + 2], posTourBig[NMAX + 2];
int matchBig[NMAX + 2];

struct SegmentTree {
    std::set <int> v[4 * NMAX];

    void Build(int node, int st, int dr) {
        if(st == dr) {
            v[node].insert(matchBig[st]);
            return;
        }

        int mid = (st + dr) >> 1;
        Build(2 * node, st, mid);
        Build(2 * node + 1, mid + 1, dr);

        for(auto it : v[2 * node])
            v[node].insert(it);

        for(auto it : v[2 * node + 1])
            v[node].insert(it);
    }

    bool Query(int node, int st, int dr, int L, int R, int L2, int R2) {
        if(R < st || L > dr)
            return false;

        if(L <= st && dr <= R) {
            auto p = v[node].lower_bound(L2);
            if(p != v[node].end() && *p <= R2)
                return true;
            return false;
        }

        int mid = (st + dr) >> 1;

        bool ans1 = Query(2 * node, st, mid, L, R, L2, R2);
        bool ans2 = Query(2 * node + 1, mid + 1, dr, L, R, L2, R2);

        return ans1 | ans2;
    }
};
SegmentTree sg;

void BuildSegmentTree() {
    for(int i = 0; i < _N; i++) {
        //posTourSmall[tourSmall[i]] = i;
        posTourBig[tourBig[i]] = i;
    }

    for(int i = 0; i < _N; i++) {
        matchBig[i] = posTourBig[tourSmall[i]];
    }

    /*
    std::cout << "Tour small:\n";
    for(auto it : tourSmall)
        std::cout << it << ' ';
    std::cout << "\nTour big:\n";
    for(auto it : tourBig)
        std::cout << it << ' ';
    std::cout << "\nMatch big:\n";
    for(int i = 0; i < _N; i++)
        std::cout << matchBig[i] << ' ';
    std::cout << "\n\n\n";
    */

    sg.Build(1, 0, _N - 1);
}

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 = (int)X.size();
    for(int i = 0; i < M; i++) {
        g[X[i]].push_back(Y[i]);
        g[Y[i]].push_back(X[i]);
    }

    BuildDSUs();

    PrecomputeLift();

    BuildSegmentTree();

    Q = (int)S.size();

    for (int i = 0; i < Q; ++i) {
        StoreQuery(S[i], E[i], L[i], R[i], i);
    }

    /*
    for (int i = 0; i < Q; ++i) {
        std::cout << "Query " << queries[i].index << ' ' << queries[i].l1 << ' ' << queries[i].r1 << ' ' << queries[i].l2 << ' ' << queries[i].r2 << '\n';
    }
    */

    std::vector<int> A(Q);
    for(int i = 0; i < Q; ++i) {
        A[i] = sg.Query(1, 0, _N - 1, queries[i].l1, queries[i].r1, queries[i].l2, queries[i].r2);
    }

    return A;
}

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