Submission #614227

#	Time	Username	Problem	Language	Result	Execution time	Memory
614227		evenvalue	Werewolf (IOI18_werewolf)	C++17	100 / 100	985 ms	92144 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 MergeSortTree {
  const int n;
  vector<vector<int>> t;

  void build(const int x, const int l, const int r, const vector<int> &a) {
    if (l == r) {
      t[x] = {a[l]};
      return;
    }
    const int mid = (l + r) / 2;
    const int y = 2 * (mid - l + 1) + x;
    build(x + 1, l, mid, a);
    build(y, mid + 1, r, a);
    merge(t[x + 1].begin(), t[x + 1].end(),
          t[y].begin(), t[y].end(),
          back_inserter(t[x]));
  }

  int query(const int x, const int l, const int r, const int ql, const int qr, const int lo, const int hi) {
    if (ql <= l and r <= qr) {
      return (int) distance(lower_bound(t[x].begin(), t[x].end(), lo),
                            upper_bound(t[x].begin(), t[x].end(), hi));
    }
    const int mid = (l + r) / 2;
    const int y = 2 * (mid - l + 1) + x;
    if (qr <= mid) {
      return query(x + 1, l, mid, ql, qr, lo, hi);
    } else if (mid < ql) {
      return query(y, mid + 1, r, ql, qr, lo, hi);
    } else {
      return query(x + 1, l, mid, ql, qr, lo, hi) +
             query(y, mid + 1, r, ql, qr, lo, hi);
    }
  }

public:
  explicit MergeSortTree(const vector<int> &a) : n((int) a.size()), t(2 * n - 1) {
    build(0, 0, n - 1, a);
  }

  int query(const int l, const int r, const int lo, const int hi) {
    return query(0, 0, n - 1, l, r, lo, hi);
  }
};

class dsu {
  vector<int> e;
  vector<pair<int, int>> val;
  vector<pair<int, int>> range;

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

public:
  explicit dsu(const int n) : e(n, -1), val(n, {0, 0}), range(n) {
    for (int i = 0; i < n; i++) {
      range[i] = {i, i};
    }
  }

  bool unite(int x, int y) {
    x = find(x), y = find(y);
    if (x > y) swap(x, y);
    if (x == y) return false;
    val[y] = {x, -e[x]};
    range[x] = {min(range[x].first, range[y].first),
                max(range[x].second, range[y].second)};
    e[x] += e[y];
    e[y] = x;
    return true;
  }

  vector<int> order() {
    vector<int> new_order(val.size());
    for (int i = 0; i < new_order.size(); i++) {
      new_order[i] = new_order[val[i].first] + val[i].second;
    }
    return new_order;
  }

  pair<int, int> get_range(const int x) {
    return range[find(x)];
  }
};

struct query {
  int s, e, l, r, i;
  int human_l, human_r;
  int werewolf_l, werewolf_r;
};

void humans(const vector<vector<int>> &g, vector<query> &queries, const vector<int> &order_human) {
  const int n = (int) g.size();
  sort(queries.begin(), queries.end(), [&](const query &q1, const query &q2) {
    return q1.l > q2.l;
  });
  dsu d(n);
  for (int l = n - 1, j = 0; l >= 0; l--) {
    for (const int y : g[l]) {
      if (y < l) continue;
      d.unite(order_human[l], order_human[y]);
    }
    while (j < queries.size() and queries[j].l == l) {
      const auto &[x, y] = d.get_range(order_human[queries[j].s]);
      queries[j].human_l = x;
      queries[j].human_r = y;
      j++;
    }
  }
}

void werewolfs(const vector<vector<int>> &g, vector<query> &queries, const vector<int> &order_werewolf) {
  const int n = (int) g.size();
  sort(queries.begin(), queries.end(), [&](const query &q1, const query &q2) {
    return q1.r < q2.r;
  });
  dsu d(n);
  for (int r = 0, j = 0; r < n; r++) {
    for (const int y : g[r]) {
      if (y > r) continue;
      d.unite(order_werewolf[r], order_werewolf[y]);
    }
    while (j < queries.size() and queries[j].r == r) {
      const auto &[x, y] = d.get_range(order_werewolf[queries[j].e]);
      queries[j].werewolf_l = x;
      queries[j].werewolf_r = y;
      j++;
    }
  }
}

void print_vec(const vector<int> &v, const string &name = "") {
  cerr << name << (name.empty() ? "" : ": ");
  for (const int x : v) {
    cerr << x << ' ';
  }
  cerr << '\n';
}

vector<int> check_validity(int n, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
  const int m = (int) X.size();//number of edges
  const int q = (int) S.size();//number of queries
  vector<vector<int>> g(n);
  for (int i = 0; i < m; i++) {
    const int x = X[i], y = Y[i];
    g[x].push_back(y);
    g[y].push_back(x);
  }
  vector<query> queries(q);
  for (int i = 0; i < q; i++) {
    queries[i] = {S[i], E[i], L[i], R[i], i};
  }
  dsu human(n), werewolf(n);
  for (int l = n - 1; l >= 0; l--) {
    for (const int y : g[l]) {
      if (y < l) continue;
      human.unite(l, y);
    }
  }
  for (int r = 0; r < n; r++) {
    for (const int y : g[r]) {
      if (y > r) continue;
      werewolf.unite(r, y);
    }
  }
  vector<int> v(n);
  vector<int> order_human = human.order();
  vector<int> order_werewolf = werewolf.order();
  for (int i = 0; i < n; i++) {
    v[order_human[i]] = order_werewolf[i];
  }
  humans(g, queries, order_human);
  werewolfs(g, queries, order_werewolf);
  sort(queries.begin(), queries.end(), [&](const query &q1, const query &q2) {
    return q1.i < q2.i;
  });
  vector<int> ans(q);
  MergeSortTree mst(v);
  for (int i = 0; i < q; i++) {
    const auto &[s, e, l, r, idx,
                 hl, hr, wl, wr] = queries[i];
    ans[i] = (mst.query(hl, hr, wl, wr) > 0);
  }
  return ans;
}

Compilation message (stderr)

werewolf.cpp: In member function 'std::vector<int> dsu::order()':
werewolf.cpp:100:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |     for (int i = 0; i < new_order.size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~~~~
werewolf.cpp: In function 'void humans(const std::vector<std::vector<int> >&, std::vector<query>&, const std::vector<int>&)':
werewolf.cpp:128:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  128 |     while (j < queries.size() and queries[j].l == l) {
      |            ~~^~~~~~~~~~~~~~~~
werewolf.cpp: In function 'void werewolfs(const std::vector<std::vector<int> >&, std::vector<query>&, const std::vector<int>&)':
werewolf.cpp:148:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  148 |     while (j < queries.size() and queries[j].r == r) {
      |            ~~^~~~~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 8 / 8
• Subtask 3: 34 / 34
• Subtask 4: 51 / 51