oj.uz

Submission #418897

# Submission time Handle Problem Language Result Execution time Memory
418897 2021-06-06T07:53:54 Z Berted Werewolf (IOI18_werewolf) C++14
100 / 100
 1066 ms 90048 KB 
#include "werewolf.h"
#include <vector>
#include <set>
#include <algorithm>

#include <iostream>

#define vi vector<int>
#define pii pair<int, int>
#define ppp pair<pii, pii>
#define ppt pair<ppp, int>
#define fst first
#define snd second

using namespace std;

const int LG = 18;

int N, M, Q, par[200001], lf[200001], rg[200001], t = 0;
ppt A[200001];
vi adj[200001], tr[200001]; 

set<int> dt[200001];

int sps[200001][LG];

int find(int x) {return par[x] = (par[x] == x) ? x : find(par[x]);}
inline void join(int a, int b, int t)
{
    //cerr << "J: " << a << " " << b << "\n";
    a = find(a), b = find(b);
    if (a != b)
    {
        if (t) 
        {  
            if (dt[a].size() < dt[b].size()) swap(a, b);
            par[b] = a;
            while (dt[b].size())
            {
                dt[a].insert(*dt[b].begin());
                dt[b].erase(dt[b].begin());
            }
        } 
        else 
        {
            par[b] = a;
            //cerr << a << " -> " << b << "\n";
            tr[a].push_back(b);
        }
    }
}

void DFS(int u, int p)
{
    sps[u][0] = p;
    //cerr << u << " " << p << "\n";
    for (int i = 1; i < LG; i++)
    {
        if (sps[u][i - 1] == -1) sps[u][i] = -1;
        else sps[u][i] = sps[sps[u][i - 1]][i - 1];
    }
    lf[u] = t++;
    for (const auto &v : tr[u]) DFS(v, u);
    rg[u] = t - 1;
}

vi check_validity(int N, vi X, vi Y, vi S, vi E, vi L, vi R) 
{
    ::N = N; M = X.size(); Q = S.size();
    vi ret(Q, 0);

    for (int i = 0; i < N; i++) par[i] = i;
    for (int i = 0; i < M; i++)
    {
        if (X[i] > Y[i]) swap(X[i], Y[i]);
        adj[Y[i]].push_back(X[i]);
    }
    for (int u = 1; u < N; u++)
    {
        for (const auto &v : adj[u]) join(u, v, 0);
    }

    for (int u = 0; u < N; u++)
    {
        if (par[u] == u) DFS(u, -1);
        adj[u].clear();
    }
    for (int i = 0; i < M; i++) {adj[X[i]].push_back(Y[i]);}

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

    sort(A, A + Q);
    int j = Q - 1;
    for (int i = N - 1; i >= 0; i--)
    {
        dt[i].insert(lf[i]); par[i] = i;
        for (const auto &v : adj[i]) 
        {
            //cerr << "J1: " << i << " " << v << "\n";
            join(i, v, 1);
        }
        for (; j >= 0 && A[j].fst.fst.fst >= i; j--)
        {
            int r = A[j].fst.fst.snd, s = A[j].fst.snd.fst, e = A[j].fst.snd.snd, id = A[j].snd;
            for (int k = LG - 1; k >= 0; k--)
            {
                if (sps[e][k] == -1) continue;
                else if (sps[e][k] <= r) {e = sps[e][k];}
            }

            s = find(s);
            auto it = dt[s].lower_bound(lf[e]);
            ret[id] = (it != dt[s].end() && *it <= rg[e]);
        }
    }
    
    return ret;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 19148 KB Output is correct
2 Correct 14 ms 19020 KB Output is correct
3 Correct 13 ms 19096 KB Output is correct
4 Correct 13 ms 19020 KB Output is correct
5 Correct 13 ms 19096 KB Output is correct
6 Correct 13 ms 19148 KB Output is correct
7 Correct 13 ms 19020 KB Output is correct
8 Correct 13 ms 19104 KB Output is correct
9 Correct 13 ms 19020 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 19148 KB Output is correct
2 Correct 14 ms 19020 KB Output is correct
3 Correct 13 ms 19096 KB Output is correct
4 Correct 13 ms 19020 KB Output is correct
5 Correct 13 ms 19096 KB Output is correct
6 Correct 13 ms 19148 KB Output is correct
7 Correct 13 ms 19020 KB Output is correct
8 Correct 13 ms 19104 KB Output is correct
9 Correct 13 ms 19020 KB Output is correct
10 Correct 19 ms 19916 KB Output is correct
11 Correct 19 ms 20036 KB Output is correct
12 Correct 20 ms 19916 KB Output is correct
13 Correct 19 ms 20160 KB Output is correct
14 Correct 19 ms 20120 KB Output is correct
15 Correct 20 ms 20044 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 947 ms 77856 KB Output is correct
2 Correct 804 ms 74788 KB Output is correct
3 Correct 758 ms 72520 KB Output is correct
4 Correct 856 ms 71564 KB Output is correct
5 Correct 805 ms 78064 KB Output is correct
6 Correct 881 ms 77892 KB Output is correct
7 Correct 905 ms 77832 KB Output is correct
8 Correct 750 ms 81352 KB Output is correct
9 Correct 605 ms 78920 KB Output is correct
10 Correct 633 ms 78092 KB Output is correct
11 Correct 672 ms 78056 KB Output is correct
12 Correct 785 ms 77916 KB Output is correct
13 Correct 732 ms 84644 KB Output is correct
14 Correct 753 ms 84800 KB Output is correct
15 Correct 754 ms 84804 KB Output is correct
16 Correct 792 ms 84636 KB Output is correct
17 Correct 861 ms 77868 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 19148 KB Output is correct
2 Correct 14 ms 19020 KB Output is correct
3 Correct 13 ms 19096 KB Output is correct
4 Correct 13 ms 19020 KB Output is correct
5 Correct 13 ms 19096 KB Output is correct
6 Correct 13 ms 19148 KB Output is correct
7 Correct 13 ms 19020 KB Output is correct
8 Correct 13 ms 19104 KB Output is correct
9 Correct 13 ms 19020 KB Output is correct
10 Correct 19 ms 19916 KB Output is correct
11 Correct 19 ms 20036 KB Output is correct
12 Correct 20 ms 19916 KB Output is correct
13 Correct 19 ms 20160 KB Output is correct
14 Correct 19 ms 20120 KB Output is correct
15 Correct 20 ms 20044 KB Output is correct
16 Correct 947 ms 77856 KB Output is correct
17 Correct 804 ms 74788 KB Output is correct
18 Correct 758 ms 72520 KB Output is correct
19 Correct 856 ms 71564 KB Output is correct
20 Correct 805 ms 78064 KB Output is correct
21 Correct 881 ms 77892 KB Output is correct
22 Correct 905 ms 77832 KB Output is correct
23 Correct 750 ms 81352 KB Output is correct
24 Correct 605 ms 78920 KB Output is correct
25 Correct 633 ms 78092 KB Output is correct
26 Correct 672 ms 78056 KB Output is correct
27 Correct 785 ms 77916 KB Output is correct
28 Correct 732 ms 84644 KB Output is correct
29 Correct 753 ms 84800 KB Output is correct
30 Correct 754 ms 84804 KB Output is correct
31 Correct 792 ms 84636 KB Output is correct
32 Correct 861 ms 77868 KB Output is correct
33 Correct 894 ms 78504 KB Output is correct
34 Correct 353 ms 51712 KB Output is correct
35 Correct 937 ms 81168 KB Output is correct
36 Correct 869 ms 78556 KB Output is correct
37 Correct 904 ms 80224 KB Output is correct
38 Correct 877 ms 79180 KB Output is correct
39 Correct 935 ms 89636 KB Output is correct
40 Correct 863 ms 87660 KB Output is correct
41 Correct 730 ms 79688 KB Output is correct
42 Correct 683 ms 78468 KB Output is correct
43 Correct 1066 ms 85872 KB Output is correct
44 Correct 858 ms 80200 KB Output is correct
45 Correct 890 ms 90048 KB Output is correct
46 Correct 941 ms 89668 KB Output is correct
47 Correct 706 ms 84804 KB Output is correct
48 Correct 701 ms 84676 KB Output is correct
49 Correct 692 ms 84768 KB Output is correct
50 Correct 697 ms 84636 KB Output is correct
51 Correct 811 ms 87640 KB Output is correct
52 Correct 854 ms 87556 KB Output is correct