oj.uz

Submission #985960

# Submission time Handle Problem Language Result Execution time Memory
985960 2024-05-19T12:21:16 Z MateiKing80 Werewolf (IOI18_werewolf) C++14
100 / 100
 799 ms 116264 KB 
#include <bits/stdc++.h>
#include "werewolf.h"

using namespace std;

#define all(a) (a).begin(), (a).end()

const int NMAX = 2e5, MMAX = 4e5;
vector<int> vec[NMAX + 5];

struct DSU
{
    int n;
    vector<int> papa;

    DSU(int N)
    {
        papa.resize(N + 1);
        for(int i = 1; i <= N; i ++)
            papa[i] = i;
        n = N;
    }

    int real_papa(int nod)
    {
        if(papa[nod] == nod)
            return nod;
        return papa[nod] = real_papa(papa[nod]);
    }

    bool query(int u, int v)
    {
        return real_papa(u) == real_papa(v);
    }

    void join(int u, int v)
    {
        papa[real_papa(v)] = real_papa(u);
    }
};

struct Arbore
{
    vector<vector<int>> lift, vec;
    int n, bitMax, root;

    Arbore(int N, int ROOT)
    {
        n = N;
        vec.resize(N + 1);
        bitMax = 20;
        root = ROOT;
    }

    void add_edge(int u, int v)
    {
        vec[u].push_back(v);
        vec[v].push_back(u);
    }

    void dfsLift(int nod, int papa)
    {
        lift[0][nod] = papa;
        for(auto i : vec[nod])
            if(i != papa)
                dfsLift(i, nod);
    }

    void makeLift()
    {
        lift.resize(bitMax, vector<int> (n + 1));
        dfsLift(root, 0);
        for(int i = 1; i < bitMax; i ++)
            for(int j = 1; j <= n; j ++)
                lift[i][j] = lift[i - 1][lift[i - 1][j]];
    }

    int findSmallestBigger(int u, int val)
    {
        int bit = bitMax - 1;
        while(bit >= 0)
        {
            if(lift[bit][u] >= val)
                u = lift[bit][u];
            bit --;
        }
        return u;
    }

    int findBiggestSmaller(int u, int val)
    {
        int bit = bitMax - 1;
        while(bit >= 0)
        {
            if(lift[bit][u] <= val && lift[bit][u] != 0)
                u = lift[bit][u];
            bit --;
        }
        return u;
    }

    void dfsOrder(int nod, int papa, vector<int> &ord, vector<pair<int, int>> &subTree)
    {
        ord.push_back(nod);
        subTree[nod].first = ord.size() - 1;
        for(auto i : vec[nod])
            if(i != papa)
                dfsOrder(i, nod, ord, subTree);
        subTree[nod].second = ord.size() - 1;
    }

    vector<pair<int, int>> preOrder()
    {
        vector<int> ord(1, 0);
        vector<pair<int, int>> subTree(n + n);
        dfsOrder(root, 0, ord, subTree);
        return subTree;
    }
};

struct Fenwick
{
    vector<int> aib;
    int n;

    Fenwick(int N)
    {
        n = N;
        aib.resize(N + 1);
    }

    inline int lsb(int x)
    {
        return x & -x;
    }

    void update(int pos, int val)
    {
        while(pos <= n)
        {
            aib[pos] += val;
            pos += lsb(pos);
        }
    }

    int query(int pos)
    {
        int ans = 0;
        while(pos)
        {
            ans += aib[pos];
            pos -= lsb(pos);
        }
        return ans;
    }
};

struct ura
{
    int pos, val, index, inm;
};

bool operator < (ura a, ura b)
{
    return a.val < b.val;
}

vector<int> check_validity(int n, vector<int> u, vector<int> v, vector<int> s, vector<int> f, vector<int> l, vector<int> r)
{
    int m = u.size(), q = s.size();
    vector<vector<int>> vec(n + 1);
    for(int i = 0; i < m; i ++)
        vec[u[i] + 1].push_back(v[i] + 1), vec[v[i] + 1].push_back(u[i] + 1);
    for(int i = 0; i < q; i ++)
        s[i] ++, f[i] ++, l[i] ++, r[i] ++;

    DSU dsuOm(n), dsuLup(n);
    Arbore om(n, 1), lup(n, n);
    for(int i = n; i; i --)
    {
        for(auto j : vec[i])
            if(j >= i && !dsuOm.query(i, j))
            {
                om.add_edge(dsuOm.real_papa(i), dsuOm.real_papa(j));
                dsuOm.join(i, j);
            }
    }
    for(int i = 1; i <= n; i ++)
    {
        for(auto j : vec[i])
            if(j <= i && !dsuLup.query(i, j))
            {
                lup.add_edge(dsuLup.real_papa(i), dsuLup.real_papa(j));
                dsuLup.join(i, j);
            }
    }
    om.makeLift(), lup.makeLift();

    auto ordOm = om.preOrder(), ordLup = lup.preOrder();
    vector<int> ans(q), posLupSchimbat(n + 1);
    Fenwick aib(n);

    for(int i = 1; i <= n; i ++)
        posLupSchimbat[ordOm[i].first] = ordLup[i].first;
    vector<ura> aux;

    for(int i = 0; i < q; i ++)
    {
        if(s[i] < l[i] || f[i] > r[i])
            continue;
        l[i] = om.findSmallestBigger(s[i], l[i]);
        r[i] = lup.findBiggestSmaller(f[i], r[i]);
        aux.push_back({ordLup[r[i]].second, ordOm[l[i]].second, i, 1});
        aux.push_back({ordLup[r[i]].second, ordOm[l[i]].first - 1, i, -1});
        aux.push_back({ordLup[r[i]].first - 1, ordOm[l[i]].second, i, -1});
        aux.push_back({ordLup[r[i]].first - 1, ordOm[l[i]].first - 1, i, 1});

    }

    sort(all(aux));
    int p = 0;
    for(int i = 0; i <= n; i ++)
    {
        while(p < aux.size() && aux[p].val == i)
            ans[aux[p].index] += aib.query(aux[p].pos) * aux[p].inm, p ++;
        if(i != n)
            aib.update(posLupSchimbat[i + 1], 1);
    }

    for(int i = 0; i < q; i ++)
        ans[i] = ans[i] != 0;

    return ans;
}

Compilation message

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:224:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<ura>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  224 |         while(p < aux.size() && aux[p].val == i)
      |               ~~^~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4956 KB Output is correct
2 Correct 1 ms 4956 KB Output is correct
3 Correct 1 ms 4944 KB Output is correct
4 Correct 2 ms 4956 KB Output is correct
5 Correct 1 ms 4956 KB Output is correct
6 Correct 1 ms 4956 KB Output is correct
7 Correct 1 ms 4956 KB Output is correct
8 Correct 2 ms 4956 KB Output is correct
9 Correct 1 ms 4956 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4956 KB Output is correct
2 Correct 1 ms 4956 KB Output is correct
3 Correct 1 ms 4944 KB Output is correct
4 Correct 2 ms 4956 KB Output is correct
5 Correct 1 ms 4956 KB Output is correct
6 Correct 1 ms 4956 KB Output is correct
7 Correct 1 ms 4956 KB Output is correct
8 Correct 2 ms 4956 KB Output is correct
9 Correct 1 ms 4956 KB Output is correct
10 Correct 6 ms 6744 KB Output is correct
11 Correct 6 ms 6748 KB Output is correct
12 Correct 6 ms 6716 KB Output is correct
13 Correct 6 ms 6748 KB Output is correct
14 Correct 6 ms 6748 KB Output is correct
15 Correct 6 ms 6760 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 788 ms 108056 KB Output is correct
2 Correct 648 ms 111200 KB Output is correct
3 Correct 642 ms 110376 KB Output is correct
4 Correct 648 ms 108616 KB Output is correct
5 Correct 670 ms 109768 KB Output is correct
6 Correct 762 ms 108344 KB Output is correct
7 Correct 715 ms 109368 KB Output is correct
8 Correct 491 ms 110524 KB Output is correct
9 Correct 345 ms 109608 KB Output is correct
10 Correct 356 ms 108344 KB Output is correct
11 Correct 378 ms 108328 KB Output is correct
12 Correct 380 ms 108864 KB Output is correct
13 Correct 641 ms 112424 KB Output is correct
14 Correct 617 ms 110884 KB Output is correct
15 Correct 643 ms 111652 KB Output is correct
16 Correct 598 ms 112448 KB Output is correct
17 Correct 690 ms 108348 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4956 KB Output is correct
2 Correct 1 ms 4956 KB Output is correct
3 Correct 1 ms 4944 KB Output is correct
4 Correct 2 ms 4956 KB Output is correct
5 Correct 1 ms 4956 KB Output is correct
6 Correct 1 ms 4956 KB Output is correct
7 Correct 1 ms 4956 KB Output is correct
8 Correct 2 ms 4956 KB Output is correct
9 Correct 1 ms 4956 KB Output is correct
10 Correct 6 ms 6744 KB Output is correct
11 Correct 6 ms 6748 KB Output is correct
12 Correct 6 ms 6716 KB Output is correct
13 Correct 6 ms 6748 KB Output is correct
14 Correct 6 ms 6748 KB Output is correct
15 Correct 6 ms 6760 KB Output is correct
16 Correct 788 ms 108056 KB Output is correct
17 Correct 648 ms 111200 KB Output is correct
18 Correct 642 ms 110376 KB Output is correct
19 Correct 648 ms 108616 KB Output is correct
20 Correct 670 ms 109768 KB Output is correct
21 Correct 762 ms 108344 KB Output is correct
22 Correct 715 ms 109368 KB Output is correct
23 Correct 491 ms 110524 KB Output is correct
24 Correct 345 ms 109608 KB Output is correct
25 Correct 356 ms 108344 KB Output is correct
26 Correct 378 ms 108328 KB Output is correct
27 Correct 380 ms 108864 KB Output is correct
28 Correct 641 ms 112424 KB Output is correct
29 Correct 617 ms 110884 KB Output is correct
30 Correct 643 ms 111652 KB Output is correct
31 Correct 598 ms 112448 KB Output is correct
32 Correct 690 ms 108348 KB Output is correct
33 Correct 799 ms 110608 KB Output is correct
34 Correct 219 ms 42108 KB Output is correct
35 Correct 731 ms 112264 KB Output is correct
36 Correct 748 ms 109860 KB Output is correct
37 Correct 760 ms 110880 KB Output is correct
38 Correct 788 ms 109256 KB Output is correct
39 Correct 755 ms 114520 KB Output is correct
40 Correct 656 ms 114896 KB Output is correct
41 Correct 448 ms 110372 KB Output is correct
42 Correct 386 ms 108916 KB Output is correct
43 Correct 544 ms 112960 KB Output is correct
44 Correct 519 ms 110984 KB Output is correct
45 Correct 433 ms 114824 KB Output is correct
46 Correct 412 ms 116264 KB Output is correct
47 Correct 609 ms 112424 KB Output is correct
48 Correct 592 ms 110888 KB Output is correct
49 Correct 612 ms 111200 KB Output is correct
50 Correct 610 ms 112452 KB Output is correct
51 Correct 526 ms 113768 KB Output is correct
52 Correct 522 ms 114504 KB Output is correct