oj.uz

Submission #991109

# Submission time Handle Problem Language Result Execution time Memory
991109 2024-06-01T09:53:19 Z LaviniaTornaghi Werewolf (IOI18_werewolf) C++17
100 / 100
 1213 ms 253136 KB 
#include <bits/stdc++.h>
#include "werewolf.h"
using namespace std;

template<typename Cmp>
class Tree {
    vector<vector<int>> adj;
    vector<int> time;
    Cmp cmp;

    int t;
    vector<vector<int>> bin_lift;
    vector<pair<int, int>> timer;
    vector<int> pos_of;

    void dfs(int node, int par = -1) {
        if (par != -1) {
            bin_lift[node].push_back(par);
            for (int i = 0; bin_lift[bin_lift[node][i]].size() > i; i++) {
                bin_lift[node].push_back(bin_lift[bin_lift[node][i]][i]);
            }
        }

        timer[node].first = t;
        if (adj[node].empty())
            pos_of[node] = t++;

        for (auto x: adj[node])
            dfs(x, node);
    
        timer[node].second = t;
    }

public:

    pair<int, int> get_range(int node, int limit) {
        for (int i = bin_lift[node].size() - 1; i >= 0; i--)
            if (bin_lift[node].size() > i && cmp(time[bin_lift[node][i]], limit))
                node = bin_lift[node][i];
        return timer[node];
    }

    int get_pos(int node) { return pos_of[node]; }

    Tree(int N, const vector<vector<int>> &adj, const vector<int> &time) 
        : adj(adj), time(time), cmp(), bin_lift(adj.size()), t(0), timer(adj.size()), pos_of(N)
    { dfs(adj.size() - 1); }
};

class DSU {
    vector<int> arr;
    vector<int> root;
    vector<int> time;
    vector<vector<int>> adj;

public:

    int find(int node) {
        if (arr[node] < 0) return node;
        return arr[node] = find(arr[node]);
    }

    void join(int u, int v, int t) {
        u = find(u), v = find(v);
        if (u == v) return;

        if (arr[v] < arr[u]) swap(u, v);
        arr[u] += arr[v];
        arr[v] = u;

        adj.push_back({root[u], root[v]});
        time.push_back(t);
        root[u] = adj.size() - 1;
    }

    template<typename Cmp>
    Tree<Cmp> get_tree() { return Tree<Cmp>(arr.size(), adj, time); }

    DSU(int N, int start_t) : arr(N, -1), root(N), time(N, start_t), adj(N) {
        time.reserve(2 * N - 1);
        adj.reserve(2 * N - 1);
        iota(root.begin(), root.end(), 0);
    }
};

class SegTree {
    vector<int> arr;
    int s;

public:

    void add(int pos, int d) {
        pos += s;
        arr[pos] += d;
        
        for (pos >>= 1; pos; pos >>= 1)
            arr[pos] = arr[2 * pos] + arr[2 * pos + 1];
    }

    int query(int l, int r) {
        int ans = 0;
        for (l += s, r += s; l < r; l >>= 1, r >>= 1) {
            if (l & 1) ans += arr[l++];
            if (r & 1) ans += arr[--r];
        }
        return ans;
    }

    SegTree(int N) {
        s = 1 << (int)ceil(log2(N));
        arr.resize(2 * s);
    }
};

vector<int> check_validity(
    int N,
    vector<int> X, vector<int> Y,
    vector<int> S, vector<int> E,
    vector<int> L, vector<int> R
) {
    int M = X.size();
    int Q = S.size();

    vector<vector<int>> adj_wolf(N), adj_human(N);
    for (int i = 0; i < M; i++) {
        auto [u, v] = minmax(X[i], Y[i]);
        adj_human[u].push_back(v);
        adj_wolf[v].push_back(u);
    }

    DSU human_dsu(N, N);
    for (int i = N - 1; i >= 0; i--)
        for (auto j: adj_human[i])
            human_dsu.join(i, j, i);
    Tree human_tree = human_dsu.get_tree<greater_equal<int>>();

    DSU wolf_dsu(N, -1);
    for (int i = 0; i < N; i++)
        for (auto j: adj_wolf[i])
            wolf_dsu.join(i, j, i);
    Tree wolf_tree = wolf_dsu.get_tree<less_equal<int>>();

    vector<int> on(N + 1);
    vector<vector<array<int, 4>>> queries(N + 1);
    for (int i = 0; i < N; i++)
        on[human_tree.get_pos(i)] = wolf_tree.get_pos(i);

    for (int i = 0; i < Q; i++) {
        auto [l1, r1] = human_tree.get_range(S[i], L[i]);
        auto [l2, r2] = wolf_tree.get_range(E[i], R[i]);

        queries[l1].push_back({l2, r2, i, -1});
        queries[r1].push_back({l2, r2, i, +1});
    }

    vector<int> ans(Q);
    SegTree segtree(N);    

    for (int i = 0; i <= N; i++) {
        for (auto [l, r, idx, mult]: queries[i])
            ans[idx] += mult * segtree.query(l, r);
        segtree.add(on[i], +1);
    }

    for (int i = 0; i < Q; i++)
        ans[i] = ans[i] > 0;

    return ans;
}

Compilation message

werewolf.cpp: In instantiation of 'std::pair<int, int> Tree<Cmp>::get_range(int, int) [with Cmp = std::greater_equal<int>]':
werewolf.cpp:149:56:   required from here
werewolf.cpp:38:39: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   38 |             if (bin_lift[node].size() > i && cmp(time[bin_lift[node][i]], limit))
      |                 ~~~~~~~~~~~~~~~~~~~~~~^~~
werewolf.cpp: In instantiation of 'std::pair<int, int> Tree<Cmp>::get_range(int, int) [with Cmp = std::less_equal<int>]':
werewolf.cpp:150:55:   required from here
werewolf.cpp:38:39: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
werewolf.cpp: In instantiation of 'Tree<Cmp>::Tree(int, const std::vector<std::vector<int> >&, const std::vector<int>&) [with Cmp = std::greater_equal<int>]':
werewolf.cpp:77:35:   required from 'Tree<Cmp> DSU::get_tree() [with Cmp = std::greater_equal<int>]'
werewolf.cpp:135:62:   required from here
werewolf.cpp:12:25: warning: 'Tree<std::greater_equal<int> >::bin_lift' will be initialized after [-Wreorder]
   12 |     vector<vector<int>> bin_lift;
      |                         ^~~~~~~~
werewolf.cpp:11:9: warning:   'int Tree<std::greater_equal<int> >::t' [-Wreorder]
   11 |     int t;
      |         ^
werewolf.cpp:45:5: warning:   when initialized here [-Wreorder]
   45 |     Tree(int N, const vector<vector<int>> &adj, const vector<int> &time)
      |     ^~~~
werewolf.cpp: In instantiation of 'Tree<Cmp>::Tree(int, const std::vector<std::vector<int> >&, const std::vector<int>&) [with Cmp = std::less_equal<int>]':
werewolf.cpp:77:35:   required from 'Tree<Cmp> DSU::get_tree() [with Cmp = std::less_equal<int>]'
werewolf.cpp:141:57:   required from here
werewolf.cpp:12:25: warning: 'Tree<std::less_equal<int> >::bin_lift' will be initialized after [-Wreorder]
   12 |     vector<vector<int>> bin_lift;
      |                         ^~~~~~~~
werewolf.cpp:11:9: warning:   'int Tree<std::less_equal<int> >::t' [-Wreorder]
   11 |     int t;
      |         ^
werewolf.cpp:45:5: warning:   when initialized here [-Wreorder]
   45 |     Tree(int N, const vector<vector<int>> &adj, const vector<int> &time)
      |     ^~~~
werewolf.cpp: In instantiation of 'void Tree<Cmp>::dfs(int, int) [with Cmp = std::greater_equal<int>]':
werewolf.cpp:47:7:   required from 'Tree<Cmp>::Tree(int, const std::vector<std::vector<int> >&, const std::vector<int>&) [with Cmp = std::greater_equal<int>]'
werewolf.cpp:77:35:   required from 'Tree<Cmp> DSU::get_tree() [with Cmp = std::greater_equal<int>]'
werewolf.cpp:135:62:   required from here
werewolf.cpp:19:64: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   19 |             for (int i = 0; bin_lift[bin_lift[node][i]].size() > i; i++) {
      |                             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
werewolf.cpp: In instantiation of 'void Tree<Cmp>::dfs(int, int) [with Cmp = std::less_equal<int>]':
werewolf.cpp:47:7:   required from 'Tree<Cmp>::Tree(int, const std::vector<std::vector<int> >&, const std::vector<int>&) [with Cmp = std::less_equal<int>]'
werewolf.cpp:77:35:   required from 'Tree<Cmp> DSU::get_tree() [with Cmp = std::less_equal<int>]'
werewolf.cpp:141:57:   required from here
werewolf.cpp:19:64: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]

Subtask #1
7.0 / 7.0

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

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 6 ms 3488 KB Output is correct
11 Correct 7 ms 3420 KB Output is correct
12 Correct 6 ms 3164 KB Output is correct
13 Correct 6 ms 3676 KB Output is correct
14 Correct 6 ms 3420 KB Output is correct
15 Correct 7 ms 3676 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 666 ms 181420 KB Output is correct
2 Correct 758 ms 227312 KB Output is correct
3 Correct 671 ms 214308 KB Output is correct
4 Correct 618 ms 203308 KB Output is correct
5 Correct 590 ms 200236 KB Output is correct
6 Correct 580 ms 199152 KB Output is correct
7 Correct 560 ms 188568 KB Output is correct
8 Correct 666 ms 226744 KB Output is correct
9 Correct 521 ms 215024 KB Output is correct
10 Correct 449 ms 202156 KB Output is correct
11 Correct 504 ms 201360 KB Output is correct
12 Correct 501 ms 197872 KB Output is correct
13 Correct 951 ms 239856 KB Output is correct
14 Correct 973 ms 239768 KB Output is correct
15 Correct 1126 ms 239780 KB Output is correct
16 Correct 1121 ms 239872 KB Output is correct
17 Correct 694 ms 188888 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 6 ms 3488 KB Output is correct
11 Correct 7 ms 3420 KB Output is correct
12 Correct 6 ms 3164 KB Output is correct
13 Correct 6 ms 3676 KB Output is correct
14 Correct 6 ms 3420 KB Output is correct
15 Correct 7 ms 3676 KB Output is correct
16 Correct 666 ms 181420 KB Output is correct
17 Correct 758 ms 227312 KB Output is correct
18 Correct 671 ms 214308 KB Output is correct
19 Correct 618 ms 203308 KB Output is correct
20 Correct 590 ms 200236 KB Output is correct
21 Correct 580 ms 199152 KB Output is correct
22 Correct 560 ms 188568 KB Output is correct
23 Correct 666 ms 226744 KB Output is correct
24 Correct 521 ms 215024 KB Output is correct
25 Correct 449 ms 202156 KB Output is correct
26 Correct 504 ms 201360 KB Output is correct
27 Correct 501 ms 197872 KB Output is correct
28 Correct 951 ms 239856 KB Output is correct
29 Correct 973 ms 239768 KB Output is correct
30 Correct 1126 ms 239780 KB Output is correct
31 Correct 1121 ms 239872 KB Output is correct
32 Correct 694 ms 188888 KB Output is correct
33 Correct 950 ms 215184 KB Output is correct
34 Correct 185 ms 38872 KB Output is correct
35 Correct 1213 ms 236700 KB Output is correct
36 Correct 908 ms 215480 KB Output is correct
37 Correct 960 ms 225520 KB Output is correct
38 Correct 813 ms 216444 KB Output is correct
39 Correct 796 ms 241592 KB Output is correct
40 Correct 774 ms 224752 KB Output is correct
41 Correct 655 ms 215532 KB Output is correct
42 Correct 561 ms 214960 KB Output is correct
43 Correct 823 ms 253136 KB Output is correct
44 Correct 803 ms 225008 KB Output is correct
45 Correct 669 ms 241272 KB Output is correct
46 Correct 692 ms 240512 KB Output is correct
47 Correct 955 ms 240112 KB Output is correct
48 Correct 908 ms 239856 KB Output is correct
49 Correct 926 ms 240112 KB Output is correct
50 Correct 959 ms 239856 KB Output is correct
51 Correct 741 ms 223604 KB Output is correct
52 Correct 747 ms 223820 KB Output is correct