oj.uz

Submission #712954

# Submission time Handle Problem Language Result Execution time Memory
712954 2023-03-20T15:36:41 Z boris_mihov Werewolf (IOI18_werewolf) C++17
100 / 100
 1016 ms 111808 KB 
#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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19284 KB Output is correct
2 Correct 11 ms 19320 KB Output is correct
3 Correct 10 ms 19188 KB Output is correct
4 Correct 10 ms 19156 KB Output is correct
5 Correct 10 ms 19252 KB Output is correct
6 Correct 9 ms 19272 KB Output is correct
7 Correct 10 ms 19284 KB Output is correct
8 Correct 11 ms 19284 KB Output is correct
9 Correct 10 ms 19292 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19284 KB Output is correct
2 Correct 11 ms 19320 KB Output is correct
3 Correct 10 ms 19188 KB Output is correct
4 Correct 10 ms 19156 KB Output is correct
5 Correct 10 ms 19252 KB Output is correct
6 Correct 9 ms 19272 KB Output is correct
7 Correct 10 ms 19284 KB Output is correct
8 Correct 11 ms 19284 KB Output is correct
9 Correct 10 ms 19292 KB Output is correct
10 Correct 15 ms 20308 KB Output is correct
11 Correct 15 ms 20328 KB Output is correct
12 Correct 15 ms 20240 KB Output is correct
13 Correct 14 ms 20412 KB Output is correct
14 Correct 15 ms 20436 KB Output is correct
15 Correct 15 ms 20384 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 947 ms 93548 KB Output is correct
2 Correct 862 ms 105332 KB Output is correct
3 Correct 796 ms 102740 KB Output is correct
4 Correct 819 ms 101532 KB Output is correct
5 Correct 767 ms 101600 KB Output is correct
6 Correct 881 ms 101492 KB Output is correct
7 Correct 874 ms 100844 KB Output is correct
8 Correct 744 ms 105284 KB Output is correct
9 Correct 452 ms 102908 KB Output is correct
10 Correct 352 ms 100588 KB Output is correct
11 Correct 398 ms 101368 KB Output is correct
12 Correct 400 ms 101556 KB Output is correct
13 Correct 837 ms 109276 KB Output is correct
14 Correct 834 ms 109240 KB Output is correct
15 Correct 822 ms 109380 KB Output is correct
16 Correct 856 ms 109492 KB Output is correct
17 Correct 869 ms 100556 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19284 KB Output is correct
2 Correct 11 ms 19320 KB Output is correct
3 Correct 10 ms 19188 KB Output is correct
4 Correct 10 ms 19156 KB Output is correct
5 Correct 10 ms 19252 KB Output is correct
6 Correct 9 ms 19272 KB Output is correct
7 Correct 10 ms 19284 KB Output is correct
8 Correct 11 ms 19284 KB Output is correct
9 Correct 10 ms 19292 KB Output is correct
10 Correct 15 ms 20308 KB Output is correct
11 Correct 15 ms 20328 KB Output is correct
12 Correct 15 ms 20240 KB Output is correct
13 Correct 14 ms 20412 KB Output is correct
14 Correct 15 ms 20436 KB Output is correct
15 Correct 15 ms 20384 KB Output is correct
16 Correct 947 ms 93548 KB Output is correct
17 Correct 862 ms 105332 KB Output is correct
18 Correct 796 ms 102740 KB Output is correct
19 Correct 819 ms 101532 KB Output is correct
20 Correct 767 ms 101600 KB Output is correct
21 Correct 881 ms 101492 KB Output is correct
22 Correct 874 ms 100844 KB Output is correct
23 Correct 744 ms 105284 KB Output is correct
24 Correct 452 ms 102908 KB Output is correct
25 Correct 352 ms 100588 KB Output is correct
26 Correct 398 ms 101368 KB Output is correct
27 Correct 400 ms 101556 KB Output is correct
28 Correct 837 ms 109276 KB Output is correct
29 Correct 834 ms 109240 KB Output is correct
30 Correct 822 ms 109380 KB Output is correct
31 Correct 856 ms 109492 KB Output is correct
32 Correct 869 ms 100556 KB Output is correct
33 Correct 904 ms 102432 KB Output is correct
34 Correct 288 ms 59024 KB Output is correct
35 Correct 918 ms 105352 KB Output is correct
36 Correct 891 ms 102700 KB Output is correct
37 Correct 899 ms 104400 KB Output is correct
38 Correct 874 ms 103148 KB Output is correct
39 Correct 1016 ms 111284 KB Output is correct
40 Correct 842 ms 110836 KB Output is correct
41 Correct 491 ms 102420 KB Output is correct
42 Correct 395 ms 101404 KB Output is correct
43 Correct 753 ms 110332 KB Output is correct
44 Correct 642 ms 104040 KB Output is correct
45 Correct 520 ms 111808 KB Output is correct
46 Correct 514 ms 111632 KB Output is correct
47 Correct 877 ms 109476 KB Output is correct
48 Correct 832 ms 109384 KB Output is correct
49 Correct 836 ms 109600 KB Output is correct
50 Correct 812 ms 109332 KB Output is correct
51 Correct 593 ms 111380 KB Output is correct
52 Correct 598 ms 111140 KB Output is correct