Submission #422736

#	Time	Username	Problem	Language	Result	Execution time	Memory
422736		Tangent	Werewolf (IOI18_werewolf)	C++17	15 / 100	4062 ms	32308 KiB

werewolf

#include "werewolf.h"
#include "bits/stdc++.h"

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vii;
typedef vector<ll> vll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<vii> vvii;
typedef vector<vll> vvll;
typedef vector<vpii> vvpii;
typedef vector<vpll> vvpll;

#define ffor(i, a, b) for (ll i = a; i < b; i++)
#define rep(i, n) ffor(i, 0, n)
#define forin(x, a) for (auto &x: a)
#define all(a) a.begin(), a.end()

std::vector<int> check_validity(int N, std::vector<int> X, std::vector<int> Y,
                                std::vector<int> S, std::vector<int> E,
                                std::vector<int> L, std::vector<int> R) {
  int Q = S.size();

  vpii edges, edges2, l, r;
  rep(i, X.size()) {
    if (X[i] > Y[i]) {
      swap(X[i], Y[i]);
    }
    edges.emplace_back(X[i], Y[i]);
    edges2.emplace_back(Y[i], X[i]);
  }
  sort(all(edges));
  sort(all(edges2));

  rep(i, Q) {
    l.emplace_back(L[i], i);
    r.emplace_back(R[i], i);
  }
  sort(all(l));
  sort(all(r));
  reverse(all(r));
  
  vii res(Q);
  vii parent(N, -1), parent2(N, -1);

  function<int(int)> root, root2;
  root = [&](int x) {
    if (parent[x] < 0) {
      return x;
    }
    return parent[x] = root(parent[x]);
  };
  root2 = [&](int x) {
    if (parent2[x] < 0) {
      return x;
    }
    return parent2[x] = root2(parent2[x]);
  };

  function<void(int, int)> merge, merge2;
  merge = [&](int x, int y) {
    int rx = root(x), ry = root(y);
    if (rx != ry) {
      if (parent[rx] < parent[ry]) {
        swap(rx, ry);
      }
      parent[ry] += parent[rx];
      parent[rx] = ry;
    }
  };
  merge2 = [&](int x, int y) {
    int rx = root2(x), ry = root2(y);
    if (rx != ry) {
      if (parent2[rx] < parent2[ry]) {
        swap(rx, ry);
      }
      parent2[ry] += parent2[rx];
      parent2[rx] = ry;
    }
  };

  vvii reached(Q);
  int edge_ind = edges.size() - 1;
  while (!l.empty()) {
    int i = l.back().second;
    l.pop_back();
    while (edge_ind >= 0 & edges[edge_ind].first >= L[i]) {
      merge(edges[edge_ind].first, edges[edge_ind].second);
      edge_ind--;
    }
    ffor(j, L[i], R[i] + 1) {
      if (root(j) == root(S[i])) {
        reached[i].emplace_back(j);
      }
    }
  }

  edge_ind = 0;
  while (!r.empty()) {
    int i = r.back().second;
    r.pop_back();
    while (edge_ind < edges2.size() && edges2[edge_ind].first <= R[i]) {
      merge2(edges2[edge_ind].first, edges2[edge_ind].second);
      edge_ind++;
    }
    forin(j, reached[i]) {
      if (root2(j) == root2(E[i])) {
        res[i] = 1;
        break;
      }
    }
  }
  return res;
}

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:18:40: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 | #define ffor(i, a, b) for (ll i = a; i < b; i++)
      |                                        ^
werewolf.cpp:19:19: note: in expansion of macro 'ffor'
   19 | #define rep(i, n) ffor(i, 0, n)
      |                   ^~~~
werewolf.cpp:29:3: note: in expansion of macro 'rep'
   29 |   rep(i, X.size()) {
      |   ^~~
werewolf.cpp:91:21: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
   91 |     while (edge_ind >= 0 & edges[edge_ind].first >= L[i]) {
      |            ~~~~~~~~~^~~~
werewolf.cpp:106:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |     while (edge_ind < edges2.size() && edges2[edge_ind].first <= R[i]) {
      |            ~~~~~~~~~^~~~~~~~~~~~~~~

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