Submission #423174

#	Time	Username	Problem	Language	Result	Execution time	Memory
423174		Tangent	Werewolf (IOI18_werewolf)	C++17	34 / 100	745 ms	34680 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();
  vii ord(n), pos(n);
  vvii adj(n);
  rep(i, X.size()) {
    adj[X[i]].emplace_back(Y[i]);
    adj[Y[i]].emplace_back(X[i]);
  }
  rep(i, n) {
    if (adj[i].size() == 1) {
      ord[0] = i;
      ord[1] = adj[i][0];
      int curr = 1;
      while (curr < n - 1) {
        forin(x, adj[ord[curr]]) {
          if (x != ord[curr - 1]) {
            ord[curr + 1] = x;
            break;
          }
        }
        curr++;
      }
      break;
    }
  }
  rep(i, n) {
    pos[ord[i]] = i;
  }

  vii tmin(2 * n), tmax(2 * n);
  rep(i, n) {
    tmin[n + i] = tmax[n + i] = ord[i];
  }
  for (int i = n - 1; i >= 1; i--) {
    tmin[i] = min(tmin[i * 2], tmin[i * 2 + 1]);
    tmax[i] = max(tmax[i * 2], tmax[i * 2 + 1]);
  }

  auto minquery = [&](int l, int r) {
    l += n;
    r += n;
    int res = n;
    while (l < r) {
      if (l % 2) res = min(res, tmin[l++]);
      if (r % 2) res = min(res, tmin[--r]);
      l /= 2;
      r /= 2;
    }
    return res;
  };
  auto maxquery = [&](int l, int r) { //[l,r)
    l += n;
    r += n;
    int res = -1;
    while (l < r) {
      if (l % 2) res = max(res, tmax[l++]);
      if (r % 2) res = max(res, tmax[--r]);
      l /= 2;
      r /= 2;
    }
    return res;
  };

  vii res(Q);
  rep(i, Q) {
    if (pos[S[i]] < pos[E[i]]) {
      if (minquery(pos[S[i]], pos[E[i]] + 1) >= L[i]) {
        res[i] = 1;
        continue;
      }
      int lo = pos[S[i]] + 1, hi = pos[E[i]];
      while (lo < hi) {
        int mid = (lo + hi) / 2;
        if (minquery(pos[S[i]], mid + 1) < L[i]) {
          hi = mid;
        } else {
          lo = mid + 1;
        }
      }
      if (maxquery(lo - 1, pos[E[i]] + 1) <= R[i]) {
        res[i] = 1;
      }
    } else {
      swap(S[i], E[i]);
      if (maxquery(pos[S[i]], pos[E[i]] + 1) <= R[i]) {
        res[i] = 1;
        continue;
      }
      int lo = pos[S[i]] + 1, hi = pos[E[i]];
      while (lo < hi) {
        int mid = (lo + hi) / 2;
        if (maxquery(pos[S[i]], mid + 1) > R[i]) {
          hi = mid;
        } else {
          lo = mid + 1;
        }
      }
      if (minquery(lo - 1, pos[E[i]] + 1) >= L[i]) {
        res[i] = 1;
      }
    }
  }
  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()) {
      |   ^~~

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