Submission #712954

#	Time	Username	Problem	Language	Result	Execution time	Memory
712954		boris_mihov	Werewolf (IOI18_werewolf)	C++17	100 / 100	1016 ms	111808 KiB

werewolf

#include "werewolf.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>

typedef long long llong;
const int MAXLOG = 20 + 5;
const int MAXN = 200000 + 10;
const int INF  = 1e9;

int n, m, q;
struct DSU
{
    int par[MAXN];
    int dep[MAXN];
    int min[MAXN];
    int max[MAXN];
    void reset()
    {
        std::fill(dep + 1, dep + 1 + n, 1);
        std::iota(par + 1, par + 1 + n, 1);
        std::iota(min + 1, min + 1 + n, 1);
        std::iota(max + 1, max + 1 + n, 1);
    }

    int find(int node)
    {
        if (par[node] == node) return node;
        return par[node] = find(par[node]);
    }

    inline void connect(int u, int v)
    {
        u = find(u); v = find(v);
        if (u == v) 
        {
            return;
        }

        if (dep[u] > dep[v]) 
        {
            std::swap(u, v);
        }
        
        if (dep[u] == dep[v]) 
        {
            dep[v]++;
        }

        min[v] = std::min(min[u], min[v]);
        max[v] = std::max(max[u], max[v]);
        par[u] = v;
    }

    inline bool areConnected(int u, int v)
    {
        return find(u) == find(v);
    }
};

struct Sparse
{
    int sparse[MAXLOG][MAXN];
    void build(int s[])
    {
        for (int i = 1 ; i <= n ; ++i)
        {
            sparse[0][i] = s[i];
        }

        for (int log = 1 ; (1 << log) <= n ; ++log)
        {
            for (int i = 1 ; i <= n ; ++i)
            {
                sparse[log][i] = sparse[log - 1][sparse[log - 1][i]];
            }
        }
    }

    inline int findLastBigger(int node, int value)
    {
        for (int log = MAXLOG - 1 ; log >= 0 ; --log)
        {
            if (sparse[log][node] >= value)
            {
                node = sparse[log][node];
            }
        }

        return node;
    }

    inline int findLastLower(int node, int value)
    {
        for (int log = MAXLOG - 1 ; log >= 0 ; --log)
        {
            if (sparse[log][node] <= value && sparse[log][node] != 0)
            {
                node = sparse[log][node];
            }
        }

        return node;
    }
};

struct BIT
{
    int tree[MAXN];
    inline void update(int pos, int value)
    {
        pos++;
        for (int idx = pos ; idx <= n ; idx += idx & (-idx))
        {
            tree[idx] += value;
        }
    }

    inline int query(int pos)
    {
        pos++;
        int res = 0;
        for (int idx = pos ; idx > 0 ; idx -= idx & (-idx))
        {
            res += tree[idx];
        }

        return res;
    }
};

int inMIN[MAXN];
int inMAX[MAXN];
int outMIN[MAXN];
int outMAX[MAXN];
int parMIN[MAXN];
int parMAX[MAXN];
int inMAXtour[MAXN];
std::vector <int> tourMIN;
std::vector <int> tourMAX;
std::vector <int> g[MAXN];
std::vector <int> treeMIN[MAXN];
std::vector <int> treeMAX[MAXN];
Sparse sparseMAX;
Sparse sparseMIN;
BIT fenwick;
DSU dsu;

void makeMAXTour(int node)
{
    inMAXtour[node] = inMAX[node] = tourMAX.size();
    tourMAX.push_back(node);

    for (const int &i : treeMAX[node])
    {
        makeMAXTour(i);
        parMAX[i] = node; 
    }

    outMAX[node] = tourMAX.size() - 1;
}

void makeMINTour(int node)
{
    inMIN[node] = tourMIN.size();
    tourMIN.push_back(inMAXtour[node]);
    for (const int &i : treeMIN[node])
    {
        makeMINTour(i);
        parMIN[i] = node; 
    }

    outMIN[node] = tourMIN.size() - 1;
}

struct Query
{
    int idx, l, r;
    bool add;
};

std::vector <int> ans;
std::vector <Query> queries[MAXN];
std::vector <int> check_validity(int N, std::vector <int> X, std::vector <int> Y, std::vector <int> S, std::vector <int> E, std::vector <int> L, std::vector <int> R)
{
    n = N;
    m = X.size();
    q = S.size();

    for (int i = 0 ; i < m ; ++i)
    {
        g[X[i] + 1].push_back(Y[i] + 1);
        g[Y[i] + 1].push_back(X[i] + 1);
    }

    dsu.reset();
    for (int i = n ; i >= 1 ; --i)
    {
        for (const int &j : g[i])
        {
            if (j < i || dsu.areConnected(i, j))
            {
                continue;
            }

            treeMAX[i].push_back(dsu.min[dsu.find(j)]);
            dsu.connect(i, j);
        }
    }

    dsu.reset();
    for (int i = 1 ; i <= n ; ++i)
    {
        for (const int &j : g[i])
        {
            if (j > i || dsu.areConnected(i, j))
            {
                continue;
            }

            treeMIN[i].push_back(dsu.max[dsu.find(j)]);
            dsu.connect(i, j);
        }
    }

    makeMAXTour(1);
    makeMINTour(n);
    sparseMAX.build(parMAX);
    sparseMIN.build(parMIN);

    for (int i = 0 ; i < q ; ++i)
    {
        int minRoot = sparseMIN.findLastLower(E[i] + 1, R[i] + 1);
        int maxRoot = sparseMAX.findLastBigger(S[i] + 1, L[i] + 1);
        if (inMIN[minRoot] > 0) queries[inMIN[minRoot] - 1].push_back({i, inMAX[maxRoot], outMAX[maxRoot], false});   
        queries[outMIN[minRoot]].push_back({i, inMAX[maxRoot], outMAX[maxRoot], true});   
    }

    ans.resize(q);
    for (int i = 0 ; i < n ; ++i)
    {
        fenwick.update(tourMIN[i], 1);
        for (const Query &curr : queries[i])
        {
            if (curr.add) ans[curr.idx] += fenwick.query(curr.r) - fenwick.query(curr.l - 1); 
            else ans[curr.idx] -= fenwick.query(curr.r) - fenwick.query(curr.l - 1); 
        }
    }

    for (int i = 0 ; i < q ; ++i)
    {
        ans[i] = (ans[i] > 0);
    }

    return ans;
}

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