Submission #114103

#	Time	Username	Problem	Language	Result	Execution time	Memory
114103		Alexa2001	Werewolf (IOI18_werewolf)	C++17	100 / 100	1513 ms	163288 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>

using namespace std;

const int Nmax = 2e5 + 5, lg = 19;

int n, q;
vector<int> edge[Nmax];
int node_A[Nmax], node_B[Nmax];
vector<pair<int,int>> when[Nmax];



struct Arb
{
    vector<int> son[Nmax];
    int L[Nmax], R[Nmax], tmp = 0;
    int root;
    int up[lg+2][Nmax];

    void dfs(int node, int dad = -1)
    {
        L[node] = ++tmp;

        up[0][node] = dad;
        int i;
        for(i=1; up[i-1][node] != -1; ++i)
            up[i][node] = up[i-1][up[i-1][node]];
        for(; i<=lg; ++i) up[i][node] = -1;

        for(auto it : son[node])
            dfs(it, node);

        R[node] = tmp;
    }
} A, B;


struct Forest
{
    int t[Nmax];

    int boss(int x)
    {
        if(x == t[x]) return x;
        return t[x] = boss(t[x]);
    }

    void init()
    {
        int i;
        for(i=0; i<n; ++i) t[i] = i;
    }

    bool unite(int x, int y)
    {
        if(x == y) return 0;
        t[y] = x;
        return 1;
    }
} forest;


auto MinSort = [] (int x, int y) { return x < y; };
auto MaxSort = [] (int x, int y) { return x > y; };


void build_tree(Arb &A, function<bool(int, int)> cmp)
{
    vector<int> ord;
    int i;
    for(i=0; i<n; ++i) ord.push_back(i);
    sort(ord.begin(), ord.end(), cmp);

    forest.init();
    for(auto node : ord)
        for(auto it : edge[node])
            if(cmp(it, node))
            {
                int who = forest.boss(it);
                if(who == node) continue;

                A.son[node].push_back(who);
                forest.t[who] = node;
            }
    A.root = ord.back();
    A.dfs(A.root);
}

int fnd(Arb &A, int node, int lim, function<bool (int, int)> cmp)
{
    int i;
    for(i=lg; i>=0; --i)
        if(A.up[i][node] != -1 && cmp(A.up[i][node], lim)) node = A.up[i][node];
    return node;
}

void find_queries(vector<int> &S, vector<int> &E, vector<int> &L, vector<int> &R)
{
    int i;
    for(i=0; i<q; ++i)
    {
        node_A[i] = fnd(A, S[i], L[i] - 1, MaxSort);
        node_B[i] = fnd(B, E[i], R[i] + 1, MinSort);
    }
}


set<int> s[Nmax];
int w[Nmax];
vector<int> ans;

void dfs(int node)
{
    w[node] = 1;

    for(auto it : A.son[node])
    {
        dfs(it);
        w[node] += w[it];
    }

    int xson = -1;
    for(auto it : A.son[node])
        if(xson == -1 || w[it] > w[xson]) xson = it;

    if(xson != -1) swap(s[node], s[xson]);

    for(auto it : A.son[node])
        if(it != xson)
            for(auto x : s[it])
                s[node].insert(x);

    s[node].insert(B.L[node]);

    for(auto it : when[node])
    {
        int bnode, id;
        tie(bnode, id) = it;

        set<int> :: iterator itt = s[node].lower_bound(B.L[bnode]);

        if(itt != s[node].end() && *itt <= B.R[bnode])
            ans[id] = 1;
        else ans[id] = 0;
    }
}

void solve_queries()
{
    int i;
    for(i=0; i<q; ++i)
        when[node_A[i]].push_back({ node_B[i], i });
    dfs(A.root);
}

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 = S.size();
    ans.resize(q);

    int i;
    for(i=0; i<X.size(); ++i)
    {
        edge[X[i]].push_back(Y[i]);
        edge[Y[i]].push_back(X[i]);
    }

    build_tree(A, MaxSort);
    build_tree(B, MinSort);

    find_queries(S, E, L, R);
    solve_queries();

    return ans;
}

Compilation message (stderr)

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:165:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0; i<X.size(); ++i)
              ~^~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 8 / 8
• Subtask 3: 34 / 34
• Subtask 4: 51 / 51