oj.uz

Submission #1078265

# Submission time Handle Problem Language Result Execution time Memory
1078265 2024-08-27T14:38:53 Z juicy Werewolf (IOI18_werewolf) C++17
34 / 100
 397 ms 75624 KB 
#include "werewolf.h"

#include <bits/stdc++.h>

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> a, std::vector<int> b) {
  int q = s.size();
  std::vector<int> pr(n);
  std::function<int(int)> find = [&](int u) {
    return u == pr[u] ? u : pr[u] = find(pr[u]);
  };
  std::vector<std::vector<int>> g(n), tr(n);
  for (int i = 0; i < n - 1; ++i) {
    g[x[i]].push_back(y[i]);
    g[y[i]].push_back(x[i]);
  }
  std::vector<int> ind(n), rank(n);
  std::vector<std::vector<std::array<int, 2>>> at(n);
  auto solve = [&](std::vector<int> &tin, std::vector<int> &tout, std::vector<int> &head) {
    iota(pr.begin(), pr.end(), 0);
    for (int i = 0; i < n; ++i) {
      int u = ind[i];
      for (int j : g[u]) {
        if (rank[j] < i && (j = find(j)) != u) {
          pr[j] = u;
          tr[u].push_back(j);
        }
      }
      for (auto [j, v] : at[u]) {
        head[j] = find(v);
      }
    }
    int timer = 0;
    std::function<void(int)> dfs = [&](int u) {
      tin[u] = ++timer;
      for (int v : tr[u]) {
        dfs(v);
      }
      tout[u] = timer;
    };
    dfs(ind.back());
  };
  std::vector tin(2, std::vector<int>(n)), tout(2, std::vector<int>(n)), head(2, std::vector<int>(q));
  for (int i = 0; i < n; ++i) {
    ind[i] = n - 1 - i;
    rank[n - 1 - i] = i;
  }
  for (int i = 0; i < q; ++i) {
    at[a[i]].push_back({i, s[i]});
  } 
  solve(tin[0], tout[0], head[0]);
  for (int i = 0; i < n; ++i) {
    ind[i] = i;
    rank[i] = i;
    std::vector<int>().swap(tr[i]);
    std::vector<std::array<int, 2>>().swap(at[i]);
  }
  for (int i = 0; i < q; ++i) {
    at[b[i]].push_back({i, e[i]});
  }
  solve(tin[1], tout[1], head[1]);
  std::vector<std::vector<std::array<int, 3>>> queries(n + 1);
  std::vector<int> ft(n + 1);
  for (int i = 0; i < q; ++i) {
    std::array<std::array<int, 2>, 2> range;
    for (int j = 0; j < 2; ++j) {
      range[j] = {tin[j][head[j][i]], tout[j][head[j][i]]};
    }
    queries[range[0][0] - 1].push_back({range[1][0], range[1][1], -i - 1});
    queries[range[0][1]].push_back({range[1][0], range[1][1], i + 1});
  }
  auto upd = [&](int i) {
    for (; i <= n; i += i & -i) {
      ++ft[i];
    }
  };
  auto qry = [&](int i) {
    int cnt = 0;
    for (; i; i -= i & -i) {
      cnt += ft[i];
    }
    return cnt;
  };
  std::vector<int> res(q), pos(n + 1);
  for (int i = 0; i < n; ++i) {
    pos[tin[0][i]] = i;
  }
  for (int i = 1; i <= n; ++i) {
    upd(tin[1][pos[i]]);
    for (auto [l, r, id] : queries[i]) {
      if (id > 0) {
        res[id - 1] += qry(r) - qry(l - 1);
      } else {
        res[-1 - id] -= qry(r) - qry(l - 1); 
      }
    }
  }
  for (int i = 0; i < q; ++i) {
    res[i] = res[i] > 0;
  }
  return res;
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 604 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 604 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 397 ms 68160 KB Output is correct
2 Correct 376 ms 72172 KB Output is correct
3 Correct 351 ms 68976 KB Output is correct
4 Correct 327 ms 66880 KB Output is correct
5 Correct 380 ms 67196 KB Output is correct
6 Correct 350 ms 67904 KB Output is correct
7 Correct 300 ms 66172 KB Output is correct
8 Correct 286 ms 72004 KB Output is correct
9 Correct 281 ms 68416 KB Output is correct
10 Correct 272 ms 65408 KB Output is correct
11 Correct 278 ms 65260 KB Output is correct
12 Correct 283 ms 67192 KB Output is correct
13 Correct 336 ms 75624 KB Output is correct
14 Correct 354 ms 75588 KB Output is correct
15 Correct 332 ms 75516 KB Output is correct
16 Correct 330 ms 75588 KB Output is correct
17 Correct 299 ms 65856 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 604 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -