제출 #991103

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
991103		LaviniaTornaghi	늑대인간 (IOI18_werewolf)	C++17	7 / 100	4032 ms	524288 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);
    }
};

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<vector<bool>> grid(N, vector<bool>(N));
    for (int i = 0; i < N; i++)
        grid[human_tree.get_pos(i)][wolf_tree.get_pos(i)] = true;

    vector<int> ans(Q);
    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]);

        for (int x = l1; x < r1; x++)
            for (int y = l2; y < r2; y++)
                ans[i] |= grid[x][y];
    }

    return ans;
}

컴파일 시 표준 에러 (stderr) 메시지

werewolf.cpp: In instantiation of 'std::pair<int, int> Tree<Cmp>::get_range(int, int) [with Cmp = std::greater_equal<int>]':
werewolf.cpp:120: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:121: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:106: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:112: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:106: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:112: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: 0 / 8
• Subtask 3: 0 / 34
• Subtask 4: 0 / 51