oj.uz

Submission #835191

# Submission time Handle Problem Language Result Execution time Memory
835191 2023-08-23T10:06:01 Z Johann Werewolf (IOI18_werewolf) C++14
34 / 100
 549 ms 524288 KB 
#include "werewolf.h"
#include "bits/stdc++.h"
using namespace std;

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()

int N, Q, M;
vi S, E, L, R;
vvi adj;
vi depth;

struct fenwick
{
  vi arr;
  void init(int size)
  {
    arr.assign(size + 1, 0);
  }
  void add(int i, int v)
  {
    ++i;
    while (i < sz(arr))
      arr[i] += v, i += i & (~i + 1);
  }
  int query(int l, int r) { return query(r - 1) - ((l > 0) ? query(l - 1) : 0); }
  int query(int i)
  {
    ++i;
    int ans = 0;
    while (i > 0)
      ans += arr[i], i -= i & (~i + 1);
    return ans;
  }
};

void dfs(int v, int p)
{
  depth[v] = depth[p] + 1;
  for (int u : adj[v])
    if (u != p)
      dfs(u, v);
}

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)
{
  N = _N, Q = sz(_S), M = sz(X);
  S = _S, E = _E, L = _L, R = _R;
  const int LOG = floor(log2(N));

  adj.assign(N, vi());
  for (int i = 0; i < M; ++i)
    adj[X[i]].push_back(Y[i]), adj[Y[i]].push_back(X[i]);
  int leaf = 0;
  for (int i = 0; i < N; ++i)
    if (sz(adj[i]) == 1)
      leaf = i;

  depth.assign(N, -1);
  dfs(leaf, leaf);

  vpii QR(Q), QL(Q);
  for (int q = 0; q < Q; ++q)
    QR[q] = {R[q], q}, QL[q] = {L[q], q};
  sort(all(QR)), sort(all(QL));
  reverse(all(QL));

  fenwick fen;
  fen.init(N);
  auto computeBorder = [&](int v, pii &ret)
  {
    int l = v;
    for (int j = LOG; j >= 0; --j)
      if (l - (1 << j) >= 0 && fen.query(l - (1 << j), v) == v - (l - (1 << j)))
        l -= 1 << j;
    int r = v + 1;
    for (int j = LOG; j >= 0; --j)
      if (r + (1 << j) <= N && fen.query(v, r + (1 << j)) == (r + (1 << j) - v))
        r += 1 << j;
    ret = {l, r};
  };

  vpii SINT(Q), EINT(Q); // [l, r)
  int idx = 0;
  for (int i = 0; i < Q; ++i)
  {
    while (idx <= QR[i].first)
      fen.add(depth[idx++], 1);
    int q = QR[i].second;
    computeBorder(depth[E[q]], EINT[q]);
  }
  idx = N - 1;
  fen.init(N);
  for (int i = 0; i < Q; ++i)
  {
    while (idx >= QL[i].first)
      fen.add(depth[idx--], 1);
    int q = QL[i].second;
    computeBorder(depth[S[q]], SINT[q]);
  }

  std::vector<int> A(Q);
  for (int q = 0; q < Q; ++q)
  {
    A[q] = max(EINT[q].first, SINT[q].first) < min(EINT[q].second, SINT[q].second);
  }
  return A;
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 247 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 247 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 549 ms 42516 KB Output is correct
2 Correct 466 ms 50256 KB Output is correct
3 Correct 458 ms 50212 KB Output is correct
4 Correct 474 ms 50172 KB Output is correct
5 Correct 479 ms 50252 KB Output is correct
6 Correct 483 ms 50252 KB Output is correct
7 Correct 491 ms 50164 KB Output is correct
8 Correct 428 ms 50216 KB Output is correct
9 Correct 305 ms 50124 KB Output is correct
10 Correct 347 ms 50192 KB Output is correct
11 Correct 387 ms 50196 KB Output is correct
12 Correct 395 ms 50168 KB Output is correct
13 Correct 476 ms 50132 KB Output is correct
14 Correct 485 ms 50248 KB Output is correct
15 Correct 473 ms 50336 KB Output is correct
16 Correct 472 ms 50216 KB Output is correct
17 Correct 502 ms 50208 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Runtime error 247 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -