oj.uz

Submission #614227

# Submission time Handle Problem Language Result Execution time Memory
614227 2022-07-30T22:28:48 Z evenvalue Werewolf (IOI18_werewolf) C++17
100 / 100
 985 ms 92144 KB 
#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

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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 300 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 296 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 300 KB Output is correct
9 Correct 1 ms 340 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 300 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 296 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 300 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 7 ms 1364 KB Output is correct
11 Correct 9 ms 1460 KB Output is correct
12 Correct 5 ms 1364 KB Output is correct
13 Correct 6 ms 1364 KB Output is correct
14 Correct 6 ms 1364 KB Output is correct
15 Correct 8 ms 1492 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 503 ms 84176 KB Output is correct
2 Correct 764 ms 84208 KB Output is correct
3 Correct 681 ms 84256 KB Output is correct
4 Correct 563 ms 84208 KB Output is correct
5 Correct 607 ms 84088 KB Output is correct
6 Correct 550 ms 84204 KB Output is correct
7 Correct 513 ms 84160 KB Output is correct
8 Correct 666 ms 84208 KB Output is correct
9 Correct 474 ms 84156 KB Output is correct
10 Correct 497 ms 84160 KB Output is correct
11 Correct 528 ms 84084 KB Output is correct
12 Correct 439 ms 84212 KB Output is correct
13 Correct 605 ms 84248 KB Output is correct
14 Correct 594 ms 84328 KB Output is correct
15 Correct 655 ms 84436 KB Output is correct
16 Correct 578 ms 84224 KB Output is correct
17 Correct 506 ms 84092 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 300 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 296 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 300 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 7 ms 1364 KB Output is correct
11 Correct 9 ms 1460 KB Output is correct
12 Correct 5 ms 1364 KB Output is correct
13 Correct 6 ms 1364 KB Output is correct
14 Correct 6 ms 1364 KB Output is correct
15 Correct 8 ms 1492 KB Output is correct
16 Correct 503 ms 84176 KB Output is correct
17 Correct 764 ms 84208 KB Output is correct
18 Correct 681 ms 84256 KB Output is correct
19 Correct 563 ms 84208 KB Output is correct
20 Correct 607 ms 84088 KB Output is correct
21 Correct 550 ms 84204 KB Output is correct
22 Correct 513 ms 84160 KB Output is correct
23 Correct 666 ms 84208 KB Output is correct
24 Correct 474 ms 84156 KB Output is correct
25 Correct 497 ms 84160 KB Output is correct
26 Correct 528 ms 84084 KB Output is correct
27 Correct 439 ms 84212 KB Output is correct
28 Correct 605 ms 84248 KB Output is correct
29 Correct 594 ms 84328 KB Output is correct
30 Correct 655 ms 84436 KB Output is correct
31 Correct 578 ms 84224 KB Output is correct
32 Correct 506 ms 84092 KB Output is correct
33 Correct 735 ms 84360 KB Output is correct
34 Correct 314 ms 38840 KB Output is correct
35 Correct 821 ms 85128 KB Output is correct
36 Correct 684 ms 84356 KB Output is correct
37 Correct 819 ms 84796 KB Output is correct
38 Correct 678 ms 84544 KB Output is correct
39 Correct 507 ms 84484 KB Output is correct
40 Correct 754 ms 91696 KB Output is correct
41 Correct 768 ms 84616 KB Output is correct
42 Correct 616 ms 84252 KB Output is correct
43 Correct 985 ms 87608 KB Output is correct
44 Correct 825 ms 84840 KB Output is correct
45 Correct 644 ms 84820 KB Output is correct
46 Correct 844 ms 84520 KB Output is correct
47 Correct 620 ms 84548 KB Output is correct
48 Correct 539 ms 84288 KB Output is correct
49 Correct 615 ms 84376 KB Output is correct
50 Correct 602 ms 84268 KB Output is correct
51 Correct 635 ms 92064 KB Output is correct
52 Correct 637 ms 92144 KB Output is correct