Submission #991109

#	Time	Username	Problem	Language	Result	Execution time	Memory
991109		LaviniaTornaghi	Werewolf (IOI18_werewolf)	C++17	100 / 100	1213 ms	253136 KiB

werewolf

#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 (stderr)

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 / 7
• Subtask 2: 8 / 8
• Subtask 3: 34 / 34
• Subtask 4: 51 / 51