oj.uz

Submission #423174

# Submission time Handle Problem Language Result Execution time Memory
423174 2021-06-10T19:37:10 Z Tangent Werewolf (IOI18_werewolf) C++17
34 / 100
 745 ms 34680 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 360 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 360 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 680 ms 34476 KB Output is correct
2 Correct 439 ms 34628 KB Output is correct
3 Correct 428 ms 34504 KB Output is correct
4 Correct 505 ms 34564 KB Output is correct
5 Correct 530 ms 34556 KB Output is correct
6 Correct 621 ms 34556 KB Output is correct
7 Correct 720 ms 34560 KB Output is correct
8 Correct 420 ms 34556 KB Output is correct
9 Correct 328 ms 34652 KB Output is correct
10 Correct 352 ms 34544 KB Output is correct
11 Correct 434 ms 34416 KB Output is correct
12 Correct 438 ms 34560 KB Output is correct
13 Correct 600 ms 34544 KB Output is correct
14 Correct 561 ms 34628 KB Output is correct
15 Correct 593 ms 34628 KB Output is correct
16 Correct 619 ms 34560 KB Output is correct
17 Correct 745 ms 34680 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 360 KB Output isn't correct
2 Halted 0 ms 0 KB -