제출 #738428

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
738428		danikoynov	늑대인간 (IOI18_werewolf)	C++14	100 / 100	906 ms	130104 KiB

werewolf

#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 / 7
• Subtask 2: 8 / 8
• Subtask 3: 34 / 34
• Subtask 4: 51 / 51