Submission #597534

#	Time	Username	Problem	Language	Result	Execution time	Memory
597534		evenvalue	Werewolf (IOI18_werewolf)	C++17	Compilation error	0 ms	0 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T>
using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;

template<typename T>
using min_heap = priority_queue<T, vector<T>, greater<T>>;
template<typename T>
using max_heap = priority_queue<T, vector<T>, less<T>>;

using int64 = long long;
using ld = long double;

constexpr int kInf = 1e9 + 10;
constexpr int64 kInf64 = 1e15 + 10;
constexpr int kMod = 1e9 + 7;

class dsu {
  int n;
  std::vector<int> e;

  int pfind(const int x) {
    return (e[x] < 0 ? x : pfind(e[x]));
  }

public:
  dsu() : n(0), comp(0) {}
  explicit dsu(const int n) : n(n), comp(n), e(n, -1) {}

  int comp;

  int find(const int x) {
    assert(0 <= x and x < n);
    return pfind(x);
  }

  bool unite(int x, int y) {
    x = find(x), y = find(y);
    if (x == y) return false;
    if (e[x] > e[y]) swap(x, y);
    e[x] += e[y];
    e[y] = x;
    return true;
  }

  bool same(const int x, const int y) {
    return (find(x) == find(y));
  }

  int size(const int x) {
    return -e[find(x)];
  }

  std::vector<std::vector<int>> components() {
    std::vector<std::vector<int>> res(n);
    for (int x = 0; x < n; x++) {
      res[pfind(x)].push_back(x);
    }
    res.erase(
        std::remove_if(res.begin(), res.end(), [&](const std::vector<int> &v) { return v.empty(); }),
        res.end());
    return res;
  }

  dsu &operator=(dsu other) {
    swap(n, other.n);
    swap(e, other.e);
    swap(comp, other.comp);
    return *this;
  }
};

vector<int> check_validity(const int N, const vector<int> &X, const vector<int> &Y, const vector<int> &S, const vector<int> &E, const vector<int> &L, const vector<int> &R) {
  const int n = N, m = X.size(), q = S.size();
  vector<vector<int>> g(n);
  for (int i = 0; i < m; i++) {
    g[X[i]].push_back(Y[i]);
    g[Y[i]].push_back(X[i]);
  }

  vector<dsu> human(n, dsu(n)), werewolf(n, dsu(n));
  for (int l = n - 2; l >= 0; l--) {
    human[l] = human[l + 1];
    for (const int y : g[l]) {
      if (y < l) continue;
      human[l].unite(l, y);
    }
  }
  for (int r = 1; r < n; r++) {
    werewolf[r] = werewolf[r - 1];
    for (const int y : g[r]) {
      if (y > r) continue;
      werewolf[r].unite(r, y);
    }
  }

  vector<int> ans(q);
  for (int query = 0; query < q; query++) {
    const int s = S[query], e = E[query], l = L[query], r = R[query];
    for (int x = l; x <= r; x++) {
      if (human[l].same(s, x) and werewolf[r].same(e, x)) {
        ans[query] = 1;
      }
    }
  }

  return ans;
}

Compilation message (stderr)

werewolf.cpp: In constructor 'dsu::dsu(int)':
werewolf.cpp:37:7: warning: 'dsu::comp' will be initialized after [-Wreorder]
   37 |   int comp;
      |       ^~~~
werewolf.cpp:27:20: warning:   'std::vector<int> dsu::e' [-Wreorder]
   27 |   std::vector<int> e;
      |                    ^
werewolf.cpp:35:12: warning:   when initialized here [-Wreorder]
   35 |   explicit dsu(const int n) : n(n), comp(n), e(n, -1) {}
      |            ^~~
/usr/bin/ld: /tmp/cctkimw4.o: in function `main':
grader.cpp:(.text.startup+0x377): undefined reference to `check_validity(int, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status