oj.uz

Submission #712953

# Submission time Handle Problem Language Result Execution time Memory
712953 2023-03-20T15:36:16 Z boris_mihov Werewolf (IOI18_werewolf) C++17
15 / 100
 225 ms 76992 KB 
#include "werewolf.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>

typedef long long llong;
const int MAXLOG = 20 + 5;
const int MAXN = 100000 + 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 6 ms 9812 KB Output is correct
2 Correct 7 ms 9848 KB Output is correct
3 Correct 7 ms 9812 KB Output is correct
4 Correct 6 ms 9812 KB Output is correct
5 Correct 7 ms 9812 KB Output is correct
6 Correct 7 ms 9764 KB Output is correct
7 Correct 6 ms 9812 KB Output is correct
8 Correct 7 ms 9812 KB Output is correct
9 Correct 8 ms 9848 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9812 KB Output is correct
2 Correct 7 ms 9848 KB Output is correct
3 Correct 7 ms 9812 KB Output is correct
4 Correct 6 ms 9812 KB Output is correct
5 Correct 7 ms 9812 KB Output is correct
6 Correct 7 ms 9764 KB Output is correct
7 Correct 6 ms 9812 KB Output is correct
8 Correct 7 ms 9812 KB Output is correct
9 Correct 8 ms 9848 KB Output is correct
10 Correct 12 ms 10964 KB Output is correct
11 Correct 11 ms 10880 KB Output is correct
12 Correct 13 ms 10952 KB Output is correct
13 Correct 11 ms 11116 KB Output is correct
14 Correct 12 ms 11004 KB Output is correct
15 Correct 12 ms 11068 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Runtime error 225 ms 76992 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9812 KB Output is correct
2 Correct 7 ms 9848 KB Output is correct
3 Correct 7 ms 9812 KB Output is correct
4 Correct 6 ms 9812 KB Output is correct
5 Correct 7 ms 9812 KB Output is correct
6 Correct 7 ms 9764 KB Output is correct
7 Correct 6 ms 9812 KB Output is correct
8 Correct 7 ms 9812 KB Output is correct
9 Correct 8 ms 9848 KB Output is correct
10 Correct 12 ms 10964 KB Output is correct
11 Correct 11 ms 10880 KB Output is correct
12 Correct 13 ms 10952 KB Output is correct
13 Correct 11 ms 11116 KB Output is correct
14 Correct 12 ms 11004 KB Output is correct
15 Correct 12 ms 11068 KB Output is correct
16 Runtime error 225 ms 76992 KB Execution killed with signal 6
17 Halted 0 ms 0 KB -