oj.uz

Submission #219252

# Submission time Handle Problem Language Result Execution time Memory
219252 2020-04-04T18:33:12 Z IgorI Werewolf (IOI18_werewolf) C++17
100 / 100
 1381 ms 132712 KB 
#include <iostream>
#include <map>
#include <vector>
#include <algorithm>

using namespace std;

typedef vector<int> vi;

const int N = 2e5 + 55;

int n, m, q;

vi graph[N];
int sz1[N];
int root1[N];
int mx1[N];
vi tree1[N];
int sz2[N];
int root2[N];
int mn2[N];
vi tree2[N];

int Root1(int x)
{
    if (root1[x] == x) return x;
    return root1[x] = Root1(root1[x]);
}

int Root2(int x)
{
    if (root2[x] == x) return x;
    return root2[x] = Root2(root2[x]);
}

void Merge1(int v, int u)
{
    v = Root1(v);
    u = Root1(u);
    int x = mx1[v], y = mx1[u];
    if (v != u)
    {
        tree1[x].push_back(y);
        tree1[y].push_back(x);
        if (sz1[v] < sz1[u])
        {
            sz1[u] += sz1[v];
            root1[v] = u;
            mx1[u] = max(x, y);
        }
        else
        {
            sz1[v] += sz1[u];
            root1[u] = v;
            mx1[v] = max(x, y);
        }
    }
}

void Merge2(int v, int u)
{
    v = Root2(v);
    u = Root2(u);
    int x = mn2[v], y = mn2[u];
    if (v != u)
    {
        tree2[x].push_back(y);
        tree2[y].push_back(x);
        if (sz2[v] < sz2[u])
        {
            sz2[u] += sz2[v];
            root2[v] = u;
            mn2[u] = min(x, y);
        }
        else
        {
            sz2[v] += sz2[u];
            root2[u] = v;
            mn2[v] = min(x, y);
        }
    }
}

int up1[20][N];
int up2[20][N];

void dfs1(int v, int p)
{
    up1[0][v] = p;
    for (auto u : tree1[v]) if (u != p)
    {
        dfs1(u, v);
    }
}

void dfs2(int v, int p)
{
    up2[0][v] = p;
    for (auto u : tree2[v]) if (u != p)
    {
        dfs2(u, v);
    }
}

int id[N], t = 0;

void dfs3(int v, int p)
{
    id[v] = t++;
    for (auto u : tree2[v]) if (u != p)
    {
        dfs3(u, v);
    }
}

vi tree3[N], tree4[N];

int L3[N], R3[N];
int L4[N], R4[N];
vector<int> euler;

bool comp(pair<pair<int, int>, int> a, pair<pair<int, int>, int> b)
{
    return R3[a.first.first] < R3[b.first.first];
}


void dfs4(int v, int p)
{
    L4[v] = v;
    R4[v] = v;
    for (auto u : tree4[v]) if (u != p)
    {
        dfs4(u, v);
        R4[v] = R4[u];
    }
}

void dfs5(int v, int p)
{
    L3[v] = euler.size();
    R3[v] = euler.size();
    euler.push_back(v);
    for (auto u : tree3[v]) if (u != p)
    {
        dfs5(u, v);
        R3[v] = euler.size();
        euler.push_back(v);
    }
}

int T[4 * N];

void _set(int p, int v, int L = 0, int R = N, int V = 0)
{
    if (L + 1 == R)
    {
        T[V] = v;
        return;
    }
    int mid = (L + R) / 2;
    if (p < mid) _set(p, v, L, mid, 2 * V + 1);
    else _set(p, v, mid, R, 2 * V + 2);
    T[V] = max(T[2 * V + 1], T[2 * V + 2]);
}

int get_max(int l, int r, int L = 0, int R = N, int V = 0)
{
    if (r <= L || R <= l)
        return -1;
    if (l <= L && R <= r)
        return T[V];
    int mid = (L + R) / 2;
    return max(get_max(l, r, L, mid, 2 * V + 1), get_max(l, r, mid, R, 2 * V + 2));
}

vector<int> check_validity(int n0, vector<int> x, vector<int> y, vector<int> s, vector<int> e, vector<int> l, vector<int> r)
{
    n = n0;
    m = x.size();
    q = s.size();
    for (int i = 0; i < m; i++)
    {
        graph[x[i]].push_back(y[i]);
        graph[y[i]].push_back(x[i]);
    }
    vi ans(q);
    fill(sz1, sz1 + n, 1);
    fill(sz2, sz2 + n, 1);
    for (int i = 0; i < n; i++) root1[i] = i, root2[i] = i, mx1[i] = i, mn2[i] = i;
    for (int i = 0; i < n; i++)
    {
        for (auto u : graph[i])
        {
            if (u < i)
                Merge1(u, i);
        }
    }
    for (int i = n - 1; i >= 0; i--)
    {
        for (auto u : graph[i])
        {
            if (u > i)
                Merge2(u, i);
        }
    }
    dfs1(n - 1, n - 1);
    dfs2(0, 0);
    for (int j = 1; j < 20; j++)
    {
        for (int i = 0; i < n; i++)
        {
            int x = up1[j - 1][i];
            up1[j][i] = up1[j - 1][x];
            int y = up2[j - 1][i];
            up2[j][i] = up2[j - 1][y];
        }
    }
    vector<pair<pair<int, int>, int> > ques;
    for (int i = 0; i < q; i++)
    {
        int st = s[i];
        for (int j = 19; j >= 0; j--)
        {
            if (l[i] <= up2[j][st])
                st = up2[j][st];
        }
        int fn = e[i];
        for (int j = 19; j >= 0; j--)
        {
            if (up1[j][fn] <= r[i])
                fn = up1[j][fn];
        }
        ques.push_back({{fn, st}, i});
    }
    dfs3(0, 0);
    for (int i = 0; i < n; i++)
    {
        for (auto u : tree1[i])
        {
            int x = id[i], y = id[u];
            tree3[x].push_back(y);
        }
        for (auto u : tree2[i])
        {
            int x = id[i], y = id[u];
            tree4[x].push_back(y);
        }
    }
    for (int i = 0; i < ques.size(); i++)
    {
        ques[i].first.first = id[ques[i].first.first];
        ques[i].first.second = id[ques[i].first.second];
    }
    dfs4(0, 0);
    dfs5(id[n - 1], id[n - 1]);
    sort(ques.begin(), ques.end(), comp);
    int j = 0;
    for (int r0 = 0; r0 < euler.size(); r0++)
    {
        int v = euler[r0];
        int l0 = L3[v];
        _set(v, r0);
        for (; j < ques.size();)
        {
            if (r0 == R3[v] && ques[j].first.first == v)
            {
                int d = get_max(L4[ques[j].first.second], R4[ques[j].first.second] + 1);
                if (l0 <= d)
                {
                    ans[ques[j].second] = 1;
                }
                j++;
            }
            else
                break;
        }
    }
    return ans;
}

Compilation message

werewolf.cpp: In function 'std::vector<int> check_validity(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
werewolf.cpp:250:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < ques.size(); i++)
                     ~~^~~~~~~~~~~~~
werewolf.cpp:259:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int r0 = 0; r0 < euler.size(); r0++)
                      ~~~^~~~~~~~~~~~~~
werewolf.cpp:264:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (; j < ques.size();)
                ~~^~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 24192 KB Output is correct
2 Correct 19 ms 24192 KB Output is correct
3 Correct 19 ms 24192 KB Output is correct
4 Correct 18 ms 24192 KB Output is correct
5 Correct 19 ms 24192 KB Output is correct
6 Correct 19 ms 24192 KB Output is correct
7 Correct 19 ms 24192 KB Output is correct
8 Correct 19 ms 24192 KB Output is correct
9 Correct 24 ms 24184 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 24192 KB Output is correct
2 Correct 19 ms 24192 KB Output is correct
3 Correct 19 ms 24192 KB Output is correct
4 Correct 18 ms 24192 KB Output is correct
5 Correct 19 ms 24192 KB Output is correct
6 Correct 19 ms 24192 KB Output is correct
7 Correct 19 ms 24192 KB Output is correct
8 Correct 19 ms 24192 KB Output is correct
9 Correct 24 ms 24184 KB Output is correct
10 Correct 27 ms 25728 KB Output is correct
11 Correct 29 ms 25720 KB Output is correct
12 Correct 27 ms 25600 KB Output is correct
13 Correct 27 ms 25728 KB Output is correct
14 Correct 27 ms 25728 KB Output is correct
15 Correct 30 ms 25848 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 1381 ms 113380 KB Output is correct
2 Correct 1110 ms 121064 KB Output is correct
3 Correct 1140 ms 122984 KB Output is correct
4 Correct 1153 ms 122056 KB Output is correct
5 Correct 1169 ms 121968 KB Output is correct
6 Correct 1256 ms 121960 KB Output is correct
7 Correct 1322 ms 122000 KB Output is correct
8 Correct 929 ms 125144 KB Output is correct
9 Correct 749 ms 123256 KB Output is correct
10 Correct 716 ms 121956 KB Output is correct
11 Correct 772 ms 122096 KB Output is correct
12 Correct 812 ms 122084 KB Output is correct
13 Correct 1098 ms 128108 KB Output is correct
14 Correct 1089 ms 128120 KB Output is correct
15 Correct 1077 ms 128104 KB Output is correct
16 Correct 1093 ms 128272 KB Output is correct
17 Correct 1336 ms 121832 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 24192 KB Output is correct
2 Correct 19 ms 24192 KB Output is correct
3 Correct 19 ms 24192 KB Output is correct
4 Correct 18 ms 24192 KB Output is correct
5 Correct 19 ms 24192 KB Output is correct
6 Correct 19 ms 24192 KB Output is correct
7 Correct 19 ms 24192 KB Output is correct
8 Correct 19 ms 24192 KB Output is correct
9 Correct 24 ms 24184 KB Output is correct
10 Correct 27 ms 25728 KB Output is correct
11 Correct 29 ms 25720 KB Output is correct
12 Correct 27 ms 25600 KB Output is correct
13 Correct 27 ms 25728 KB Output is correct
14 Correct 27 ms 25728 KB Output is correct
15 Correct 30 ms 25848 KB Output is correct
16 Correct 1381 ms 113380 KB Output is correct
17 Correct 1110 ms 121064 KB Output is correct
18 Correct 1140 ms 122984 KB Output is correct
19 Correct 1153 ms 122056 KB Output is correct
20 Correct 1169 ms 121968 KB Output is correct
21 Correct 1256 ms 121960 KB Output is correct
22 Correct 1322 ms 122000 KB Output is correct
23 Correct 929 ms 125144 KB Output is correct
24 Correct 749 ms 123256 KB Output is correct
25 Correct 716 ms 121956 KB Output is correct
26 Correct 772 ms 122096 KB Output is correct
27 Correct 812 ms 122084 KB Output is correct
28 Correct 1098 ms 128108 KB Output is correct
29 Correct 1089 ms 128120 KB Output is correct
30 Correct 1077 ms 128104 KB Output is correct
31 Correct 1093 ms 128272 KB Output is correct
32 Correct 1336 ms 121832 KB Output is correct
33 Correct 1349 ms 123496 KB Output is correct
34 Correct 437 ms 59008 KB Output is correct
35 Correct 1316 ms 126624 KB Output is correct
36 Correct 1362 ms 122772 KB Output is correct
37 Correct 1351 ms 125772 KB Output is correct
38 Correct 1363 ms 123368 KB Output is correct
39 Correct 1282 ms 131944 KB Output is correct
40 Correct 1200 ms 131816 KB Output is correct
41 Correct 934 ms 125028 KB Output is correct
42 Correct 867 ms 122728 KB Output is correct
43 Correct 1099 ms 130932 KB Output is correct
44 Correct 1047 ms 125952 KB Output is correct
45 Correct 942 ms 132072 KB Output is correct
46 Correct 988 ms 131816 KB Output is correct
47 Correct 1062 ms 128104 KB Output is correct
48 Correct 1060 ms 128348 KB Output is correct
49 Correct 1041 ms 128232 KB Output is correct
50 Correct 1072 ms 127944 KB Output is correct
51 Correct 1084 ms 132712 KB Output is correct
52 Correct 1102 ms 132708 KB Output is correct