oj.uz

답안 #320440

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
320440 2020-11-08T18:56:38 Z mihai145 늑대인간 (IOI18_werewolf) C++14
100 / 100
 3044 ms 314656 KB 
#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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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