Submission #991102

#	Time	Username	Problem	Language	Result	Execution time	Memory
991102		LaviniaTornaghi	Werewolf (IOI18_werewolf)	C++14	Compilation error	0 ms	0 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;
}

Compilation message (stderr)

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:97:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   97 |         auto [u, v] = minmax(X[i], Y[i]);
      |              ^
werewolf.cpp:106:10: error: missing template arguments before 'human_tree'
  106 |     Tree human_tree = human_dsu.get_tree<greater_equal<int>>();
      |          ^~~~~~~~~~
werewolf.cpp:112:10: error: missing template arguments before 'wolf_tree'
  112 |     Tree wolf_tree = wolf_dsu.get_tree<less_equal<int>>();
      |          ^~~~~~~~~
werewolf.cpp:116:14: error: 'human_tree' was not declared in this scope
  116 |         grid[human_tree.get_pos(i)][wolf_tree.get_pos(i)] = true;
      |              ^~~~~~~~~~
werewolf.cpp:116:37: error: 'wolf_tree' was not declared in this scope
  116 |         grid[human_tree.get_pos(i)][wolf_tree.get_pos(i)] = true;
      |                                     ^~~~~~~~~
werewolf.cpp:120:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  120 |         auto [l1, r1] = human_tree.get_range(S[i], L[i]);
      |              ^
werewolf.cpp:120:25: error: 'human_tree' was not declared in this scope
  120 |         auto [l1, r1] = human_tree.get_range(S[i], L[i]);
      |                         ^~~~~~~~~~
werewolf.cpp:121:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  121 |         auto [l2, r2] = wolf_tree.get_range(E[i], R[i]);
      |              ^
werewolf.cpp:121:25: error: 'wolf_tree' was not declared in this scope
  121 |         auto [l2, r2] = wolf_tree.get_range(E[i], R[i]);
      |                         ^~~~~~~~~