Submission #320440

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
320440	2020-11-08T18:56:38 Z	mihai145	Werewolf (IOI18_werewolf)	C++14	100 / 100	3044 ms	314656 KB

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.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	34 ms	52332 KB	Output is correct
2	Correct	34 ms	52324 KB	Output is correct
3	Correct	34 ms	52332 KB	Output is correct
4	Correct	34 ms	52196 KB	Output is correct
5	Correct	33 ms	52324 KB	Output is correct
6	Correct	34 ms	52332 KB	Output is correct
7	Correct	37 ms	52324 KB	Output is correct
8	Correct	33 ms	52332 KB	Output is correct
9	Correct	33 ms	52328 KB	Output is correct

Subtask #2
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	34 ms	52332 KB	Output is correct
2	Correct	34 ms	52324 KB	Output is correct
3	Correct	34 ms	52332 KB	Output is correct
4	Correct	34 ms	52196 KB	Output is correct
5	Correct	33 ms	52324 KB	Output is correct
6	Correct	34 ms	52332 KB	Output is correct
7	Correct	37 ms	52324 KB	Output is correct
8	Correct	33 ms	52332 KB	Output is correct
9	Correct	33 ms	52328 KB	Output is correct
10	Correct	47 ms	55272 KB	Output is correct
11	Correct	46 ms	55268 KB	Output is correct
12	Correct	45 ms	55268 KB	Output is correct
13	Correct	50 ms	55544 KB	Output is correct
14	Correct	47 ms	55396 KB	Output is correct
15	Correct	47 ms	55396 KB	Output is correct

Subtask #3
34.0 / 34.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1534 ms	303552 KB	Output is correct
2	Correct	2399 ms	306900 KB	Output is correct
3	Correct	2374 ms	304592 KB	Output is correct
4	Correct	2290 ms	303700 KB	Output is correct
5	Correct	2203 ms	303704 KB	Output is correct
6	Correct	2005 ms	303600 KB	Output is correct
7	Correct	1494 ms	303440 KB	Output is correct
8	Correct	2309 ms	306940 KB	Output is correct
9	Correct	1976 ms	304660 KB	Output is correct
10	Correct	1169 ms	303552 KB	Output is correct
11	Correct	1233 ms	303652 KB	Output is correct
12	Correct	1674 ms	303448 KB	Output is correct
13	Correct	2102 ms	312436 KB	Output is correct
14	Correct	2102 ms	312276 KB	Output is correct
15	Correct	1991 ms	312308 KB	Output is correct
16	Correct	1990 ms	312392 KB	Output is correct
17	Correct	1488 ms	303428 KB	Output is correct

Subtask #4
51.0 / 51.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	34 ms	52332 KB	Output is correct
2	Correct	34 ms	52324 KB	Output is correct
3	Correct	34 ms	52332 KB	Output is correct
4	Correct	34 ms	52196 KB	Output is correct
5	Correct	33 ms	52324 KB	Output is correct
6	Correct	34 ms	52332 KB	Output is correct
7	Correct	37 ms	52324 KB	Output is correct
8	Correct	33 ms	52332 KB	Output is correct
9	Correct	33 ms	52328 KB	Output is correct
10	Correct	47 ms	55272 KB	Output is correct
11	Correct	46 ms	55268 KB	Output is correct
12	Correct	45 ms	55268 KB	Output is correct
13	Correct	50 ms	55544 KB	Output is correct
14	Correct	47 ms	55396 KB	Output is correct
15	Correct	47 ms	55396 KB	Output is correct
16	Correct	1534 ms	303552 KB	Output is correct
17	Correct	2399 ms	306900 KB	Output is correct
18	Correct	2374 ms	304592 KB	Output is correct
19	Correct	2290 ms	303700 KB	Output is correct
20	Correct	2203 ms	303704 KB	Output is correct
21	Correct	2005 ms	303600 KB	Output is correct
22	Correct	1494 ms	303440 KB	Output is correct
23	Correct	2309 ms	306940 KB	Output is correct
24	Correct	1976 ms	304660 KB	Output is correct
25	Correct	1169 ms	303552 KB	Output is correct
26	Correct	1233 ms	303652 KB	Output is correct
27	Correct	1674 ms	303448 KB	Output is correct
28	Correct	2102 ms	312436 KB	Output is correct
29	Correct	2102 ms	312276 KB	Output is correct
30	Correct	1991 ms	312308 KB	Output is correct
31	Correct	1990 ms	312392 KB	Output is correct
32	Correct	1488 ms	303428 KB	Output is correct
33	Correct	2334 ms	303952 KB	Output is correct
34	Correct	422 ms	88680 KB	Output is correct
35	Correct	2891 ms	307080 KB	Output is correct
36	Correct	2098 ms	304216 KB	Output is correct
37	Correct	2774 ms	305868 KB	Output is correct
38	Correct	2339 ms	304844 KB	Output is correct
39	Correct	2604 ms	314360 KB	Output is correct
40	Correct	1818 ms	314364 KB	Output is correct
41	Correct	2020 ms	305504 KB	Output is correct
42	Correct	1235 ms	304212 KB	Output is correct
43	Correct	3044 ms	312016 KB	Output is correct
44	Correct	2601 ms	305684 KB	Output is correct
45	Correct	1918 ms	314656 KB	Output is correct
46	Correct	2051 ms	314352 KB	Output is correct
47	Correct	2090 ms	312544 KB	Output is correct
48	Correct	2062 ms	312380 KB	Output is correct
49	Correct	2007 ms	312440 KB	Output is correct
50	Correct	2013 ms	312296 KB	Output is correct
51	Correct	1561 ms	314260 KB	Output is correct
52	Correct	1617 ms	314164 KB	Output is correct

Submission #320440

Compilation message

Subtask #1 7.0 / 7.0

Subtask #2 8.0 / 8.0

Subtask #3 34.0 / 34.0

Subtask #4 51.0 / 51.0

Subtask #1
7.0 / 7.0

Subtask #2
8.0 / 8.0

Subtask #3
34.0 / 34.0

Subtask #4
51.0 / 51.0