oj.uz

Submission #738428

# Submission time Handle Problem Language Result Execution time Memory
738428 2023-05-08T18:12:41 Z danikoynov Werewolf (IOI18_werewolf) C++14
100 / 100
 906 ms 130104 KB 
#include "werewolf.h"
#include <bits/stdc++.h>

using namespace std;

const int maxn = 4e5 + 10;

struct query
{
    int l, r, s, e;

    query(int _l = 0, int _r = 0, int _s = 0, int _e = 0)
    {
        l = _l;
        r = _r;
        s = _s;
        e = _e;
    }
} ask[maxn];

struct node_query
{
    int idx, ver;

    node_query(int _ver = 0, int _idx = 0)
    {
        ver = _ver;
        idx = _idx;
    }
};

int n, q, m, used0[maxn], used1[maxn];
vector < int > graph[maxn];
vector < node_query > task[maxn];

const int maxlog = 21;

int fen[maxn];

int tour_pos[maxn], in[maxn], out[maxn];


void add(int p, int val)
{
    for (int i = p; i < maxn; i += (i & -i))
        fen[i] += val;
}

int sum(int p)
{
    int s = 0;
    for (int i = p; i > 0; i -= (i & -i))
        s += fen[i];
    return s;
}

vector < int > ans;

struct reconstruction_tree
{
    vector < int > par, tin, tout, sub;
    vector < vector < int > > adj;
    vector < vector < int > > dp;
    int timer;
    reconstruction_tree(int n)
    {
        timer = 0;
        tin.resize(n);
        tout.resize(n);
        par.resize(n);
        adj.resize(n);
        sub.resize(n);
        dp.resize(maxlog);
        for (int i = 0; i < maxlog; i ++)
            dp[i].resize(n);
        for (int i = 0; i < n; i ++)
        {
            par[i] = i;
        }
    }

    void euler(int v, int par, bool type)
    {
        dp[0][v] = par;
        for (int j = 1; j < maxlog; j ++)
        {
            if (dp[j - 1][v] == -1)
            {
                dp[j][v] = -1;
                continue;
            }
            dp[j][v] = dp[j - 1][dp[j - 1][v]];
        }

        tin[v] = ++ timer;
        if (type == false)
        {
            tour_pos[v] = timer;
            in[v] = timer;
        }
        sub[v] = 1;
        for (int u : adj[v])
        {
            euler(u, v, type);
            sub[v] += sub[u];
        }
        tout[v] = timer;
        if (type == false)
        {
            out[v] = timer;
        }
    }

    void add_dfs(int v, int val)
    {
        add(tour_pos[v], val);
        for (int u : adj[v])
        {
            add_dfs(u, val);
        }
    }
    void dfs(int v, int p, bool big)
    {

        int mx = -1;
        for (int u : adj[v])
        {
            if (mx == -1 || sub[u] > sub[mx])
                mx = u;
        }

        for (int u : adj[v])
        {
            if (u != mx)
                dfs(u, v, false);
        }

        if (mx != -1)
            dfs(mx, v, true);
        for (int u : adj[v])
        {
            if (u != mx)
            add_dfs(u, 1);
        }

        add(tour_pos[v], 1);

        ///answer queries
        for (node_query cur : task[v])
        {
            if (sum(out[cur.ver]) - sum(in[cur.ver] - 1) > 0)
                ans[cur.idx] = 1;
            else
                ans[cur.idx] = 0;
        }
        if (!big)
        {
            add_dfs(v, -1);
        }

    }

    int find_leader(int v)
    {
        if (v == par[v])
            return v;
        return (par[v] = find_leader(par[v]));
    }

    bool unite(int v, int u)
    {
        v = find_leader(v);
        u = find_leader(u);
        if (v == u)
            return false;
        par[u] = v;
        return true;
    }

    void add_vertex(int v, bool type)
    {
        for (int u : graph[v])
        {
            if (type == 0 && u > v)
                continue;
            if (type == 1 && u < v)
                continue;
            int ld = find_leader(u);
            if (unite(v, u))
                adj[v].push_back(ld);
        }
    }
};


vector<int> check_validity(int N, vector<int> X, vector<int> Y,
                           vector<int> S, vector<int> E,
                           vector<int> L, vector<int> R)
{
    n = N;
    q = L.size();
    m = X.size();
    for (int i = 0; i < q; i ++)
    {
        ask[i] = query(L[i], R[i], S[i], E[i]);
    }
    for (int i = 0; i < m; i ++)
    {
        graph[X[i]].push_back(Y[i]);
        graph[Y[i]].push_back(X[i]);
    }

    reconstruction_tree max_tree(n), min_tree(n);

    for (int i = 0; i < n; i ++)
    {
        min_tree.add_vertex(i, 0);
    }

    for (int i = n - 1; i >= 0; i --)
    {
        max_tree.add_vertex(i, 1);
    }

    min_tree.euler(n - 1, -1, false);
    max_tree.euler(0, -1, true);
    ans.resize(q, 0);
    for (int i = 0; i < q; i ++)
    {
        int ver = ask[i].s;
        for (int j = maxlog - 1; j >= 0; j --)
        {
            if (max_tree.dp[j][ver] != -1 && max_tree.dp[j][ver] >= ask[i].l)
                ver = max_tree.dp[j][ver];
        }

        int to = ask[i].e;
        for (int j = maxlog - 1; j >= 0; j --)
        {
            if (min_tree.dp[j][to] != -1 && min_tree.dp[j][to] <= ask[i].r)
                to = min_tree.dp[j][to];
        }

        ///cout << ver << " " << to << endl;
        task[ver].push_back(node_query(to, i));
    }

    max_tree.dfs(0, -1, true);

    return ans;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 25420 KB Output is correct
2 Correct 13 ms 25372 KB Output is correct
3 Correct 14 ms 25428 KB Output is correct
4 Correct 13 ms 25428 KB Output is correct
5 Correct 14 ms 25428 KB Output is correct
6 Correct 14 ms 25428 KB Output is correct
7 Correct 13 ms 25440 KB Output is correct
8 Correct 14 ms 25428 KB Output is correct
9 Correct 17 ms 25372 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 25420 KB Output is correct
2 Correct 13 ms 25372 KB Output is correct
3 Correct 14 ms 25428 KB Output is correct
4 Correct 13 ms 25428 KB Output is correct
5 Correct 14 ms 25428 KB Output is correct
6 Correct 14 ms 25428 KB Output is correct
7 Correct 13 ms 25440 KB Output is correct
8 Correct 14 ms 25428 KB Output is correct
9 Correct 17 ms 25372 KB Output is correct
10 Correct 19 ms 26812 KB Output is correct
11 Correct 19 ms 26708 KB Output is correct
12 Correct 18 ms 26676 KB Output is correct
13 Correct 19 ms 26996 KB Output is correct
14 Correct 18 ms 26836 KB Output is correct
15 Correct 19 ms 26836 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 851 ms 107236 KB Output is correct
2 Correct 741 ms 109668 KB Output is correct
3 Correct 656 ms 107392 KB Output is correct
4 Correct 668 ms 106536 KB Output is correct
5 Correct 711 ms 106644 KB Output is correct
6 Correct 746 ms 107184 KB Output is correct
7 Correct 776 ms 106420 KB Output is correct
8 Correct 676 ms 109672 KB Output is correct
9 Correct 499 ms 106936 KB Output is correct
10 Correct 501 ms 106200 KB Output is correct
11 Correct 505 ms 106144 KB Output is correct
12 Correct 627 ms 106016 KB Output is correct
13 Correct 800 ms 122548 KB Output is correct
14 Correct 767 ms 122564 KB Output is correct
15 Correct 757 ms 122544 KB Output is correct
16 Correct 768 ms 122716 KB Output is correct
17 Correct 762 ms 106544 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 25420 KB Output is correct
2 Correct 13 ms 25372 KB Output is correct
3 Correct 14 ms 25428 KB Output is correct
4 Correct 13 ms 25428 KB Output is correct
5 Correct 14 ms 25428 KB Output is correct
6 Correct 14 ms 25428 KB Output is correct
7 Correct 13 ms 25440 KB Output is correct
8 Correct 14 ms 25428 KB Output is correct
9 Correct 17 ms 25372 KB Output is correct
10 Correct 19 ms 26812 KB Output is correct
11 Correct 19 ms 26708 KB Output is correct
12 Correct 18 ms 26676 KB Output is correct
13 Correct 19 ms 26996 KB Output is correct
14 Correct 18 ms 26836 KB Output is correct
15 Correct 19 ms 26836 KB Output is correct
16 Correct 851 ms 107236 KB Output is correct
17 Correct 741 ms 109668 KB Output is correct
18 Correct 656 ms 107392 KB Output is correct
19 Correct 668 ms 106536 KB Output is correct
20 Correct 711 ms 106644 KB Output is correct
21 Correct 746 ms 107184 KB Output is correct
22 Correct 776 ms 106420 KB Output is correct
23 Correct 676 ms 109672 KB Output is correct
24 Correct 499 ms 106936 KB Output is correct
25 Correct 501 ms 106200 KB Output is correct
26 Correct 505 ms 106144 KB Output is correct
27 Correct 627 ms 106016 KB Output is correct
28 Correct 800 ms 122548 KB Output is correct
29 Correct 767 ms 122564 KB Output is correct
30 Correct 757 ms 122544 KB Output is correct
31 Correct 768 ms 122716 KB Output is correct
32 Correct 762 ms 106544 KB Output is correct
33 Correct 894 ms 108908 KB Output is correct
34 Correct 255 ms 59888 KB Output is correct
35 Correct 879 ms 121744 KB Output is correct
36 Correct 872 ms 116100 KB Output is correct
37 Correct 848 ms 120228 KB Output is correct
38 Correct 863 ms 117360 KB Output is correct
39 Correct 870 ms 125200 KB Output is correct
40 Correct 771 ms 127208 KB Output is correct
41 Correct 613 ms 117988 KB Output is correct
42 Correct 632 ms 114760 KB Output is correct
43 Correct 767 ms 128528 KB Output is correct
44 Correct 860 ms 119352 KB Output is correct
45 Correct 649 ms 124040 KB Output is correct
46 Correct 732 ms 123896 KB Output is correct
47 Correct 834 ms 130104 KB Output is correct
48 Correct 906 ms 129892 KB Output is correct
49 Correct 791 ms 129972 KB Output is correct
50 Correct 763 ms 129888 KB Output is correct
51 Correct 753 ms 127060 KB Output is correct
52 Correct 699 ms 126912 KB Output is correct