oj.uz

Submission #902210

# Submission time Handle Problem Language Result Execution time Memory
902210 2024-01-10T07:10:37 Z rxlfd314 Werewolf (IOI18_werewolf) C++17
100 / 100
 817 ms 132036 KB 
#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
using ari2 = array<int, 2>;

#define vt vector
#define size(x) (int((x).size()))
#define all(x) begin(x), end(x)

#define REP(a, b, c, d) for (int a = (b); (d) > 0 ? a <= (c) : a >= (c); a += (d))
#define FOR(a, b, c) REP(a, b, c, 1)
#define ROF(a, b, c) REP(a, b, c, -1)

vt<int> check_validity(int N, vt<int> X, vt<int> Y, vt<int> S, vt<int> E, vt<int> L, vt<int> R) {
  vt<int> adj[N];
  FOR(i, 0, size(X)-1) {
    adj[X[i]].push_back(Y[i]);
    adj[Y[i]].push_back(X[i]);
  }
  auto gen_tree = [&](int mul) {
    int uf[N], mx[N];
    memset(uf, -1, sizeof(uf));
    FOR(i, 0, N-1)
      mx[i] = i * mul;
    function<int(int)> find = [&](int i) {
      return uf[i] < 0 ? i : uf[i] = find(uf[i]);
    };
    vt<vt<int>> tree(N);
    auto unite = [&](int a, int b) {
      if ((a = find(a)) == (b = find(b)))
        return false;
      if (uf[a] > uf[b])
        swap(a, b);
      tree[mul * max(mx[a], mx[b])].push_back(mul * min(mx[a], mx[b]));
      uf[a] += uf[b];
      uf[b] = a;
      mx[a] = max(mx[a], mx[b]);
      return true;
    };
    REP(i, ~mul ? 0 : N-1, ~mul ? N-1 : 0, mul)
      for (int j : adj[i])
        if (j * mul < i * mul)
          unite(i, j);
    return tree;
  };
  
  vt<vt<int>> wt = gen_tree(1); // root is N-1
  vt<vt<int>> ht = gen_tree(-1); // root is 0
  
  int tin[N], tout[N], lift_ht[N][18], lift_wt[N][18], timer = 0;
  function<void(int, int)> dfs_ht = [&](int i, int p) {
    tin[i] = timer++;
    lift_ht[i][0] = p;
    for (int j : ht[i])
      dfs_ht(j, i);
    tout[i] = timer - 1;
  };
  function<void(int, int)> dfs_wt = [&](int i, int p) {
    lift_wt[i][0] = p;
    for (int j : wt[i])
      dfs_wt(j, i);
  };
  dfs_ht(0, 0); 
  dfs_wt(N-1, N-1);
  FOR(j, 1, 17)
    FOR(i, 0, N-1) {
      lift_wt[i][j] = lift_wt[lift_wt[i][j-1]][j-1];
      lift_ht[i][j] = lift_ht[lift_ht[i][j-1]][j-1];
    }
  
  // S in ht
  // E in wt
  vt<ari2> Q[N];
  FOR(i, 0, size(S)-1) {
    // find maximum ancestor of E[i]
    int a = E[i];
    ROF(j, 17, 0)
      if (lift_wt[a][j] <= R[i])
        a = lift_wt[a][j];
    // find minimum ancestor of S[i]
    int b = S[i];
    ROF(j, 17, 0)
      if (lift_ht[b][j] >= L[i])
        b = lift_ht[b][j];
    Q[a].push_back({b, i});
  }
  
  vt<int> ans(size(S));
  set<int> ss[N];
  function<void(int)> dfs = [&](int i) {
    ss[i].insert(tin[i]);
    for (int j : wt[i]) {
      dfs(j);
      if (size(ss[j]) > size(ss[i]))
        swap(ss[j], ss[i]);
      for (int v : ss[j])
        ss[i].insert(v);
      ss[j].clear();
    }
    for (auto [j, q] : Q[i])
      ans[q] = ss[i].lower_bound(tin[j]) != ss[i].upper_bound(tout[j]);
  };
  dfs(N-1);
  
  return ans;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 504 KB Output is correct
2 Correct 1 ms 360 KB Output is correct
3 Correct 1 ms 356 KB Output is correct
4 Correct 1 ms 756 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 360 KB Output is correct
8 Correct 1 ms 360 KB Output is correct
9 Correct 1 ms 360 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 504 KB Output is correct
2 Correct 1 ms 360 KB Output is correct
3 Correct 1 ms 356 KB Output is correct
4 Correct 1 ms 756 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 360 KB Output is correct
8 Correct 1 ms 360 KB Output is correct
9 Correct 1 ms 360 KB Output is correct
10 Correct 8 ms 2076 KB Output is correct
11 Correct 5 ms 1900 KB Output is correct
12 Correct 5 ms 1896 KB Output is correct
13 Correct 5 ms 2288 KB Output is correct
14 Correct 7 ms 2376 KB Output is correct
15 Correct 6 ms 2236 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 724 ms 107948 KB Output is correct
2 Correct 639 ms 113056 KB Output is correct
3 Correct 592 ms 106560 KB Output is correct
4 Correct 536 ms 104156 KB Output is correct
5 Correct 562 ms 104064 KB Output is correct
6 Correct 660 ms 104700 KB Output is correct
7 Correct 626 ms 106636 KB Output is correct
8 Correct 584 ms 112916 KB Output is correct
9 Correct 473 ms 105608 KB Output is correct
10 Correct 431 ms 103556 KB Output is correct
11 Correct 464 ms 103812 KB Output is correct
12 Correct 514 ms 104504 KB Output is correct
13 Correct 721 ms 125756 KB Output is correct
14 Correct 759 ms 125392 KB Output is correct
15 Correct 755 ms 125884 KB Output is correct
16 Correct 761 ms 126160 KB Output is correct
17 Correct 693 ms 106476 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 504 KB Output is correct
2 Correct 1 ms 360 KB Output is correct
3 Correct 1 ms 356 KB Output is correct
4 Correct 1 ms 756 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 360 KB Output is correct
8 Correct 1 ms 360 KB Output is correct
9 Correct 1 ms 360 KB Output is correct
10 Correct 8 ms 2076 KB Output is correct
11 Correct 5 ms 1900 KB Output is correct
12 Correct 5 ms 1896 KB Output is correct
13 Correct 5 ms 2288 KB Output is correct
14 Correct 7 ms 2376 KB Output is correct
15 Correct 6 ms 2236 KB Output is correct
16 Correct 724 ms 107948 KB Output is correct
17 Correct 639 ms 113056 KB Output is correct
18 Correct 592 ms 106560 KB Output is correct
19 Correct 536 ms 104156 KB Output is correct
20 Correct 562 ms 104064 KB Output is correct
21 Correct 660 ms 104700 KB Output is correct
22 Correct 626 ms 106636 KB Output is correct
23 Correct 584 ms 112916 KB Output is correct
24 Correct 473 ms 105608 KB Output is correct
25 Correct 431 ms 103556 KB Output is correct
26 Correct 464 ms 103812 KB Output is correct
27 Correct 514 ms 104504 KB Output is correct
28 Correct 721 ms 125756 KB Output is correct
29 Correct 759 ms 125392 KB Output is correct
30 Correct 755 ms 125884 KB Output is correct
31 Correct 761 ms 126160 KB Output is correct
32 Correct 693 ms 106476 KB Output is correct
33 Correct 711 ms 106292 KB Output is correct
34 Correct 211 ms 34336 KB Output is correct
35 Correct 804 ms 111696 KB Output is correct
36 Correct 661 ms 106068 KB Output is correct
37 Correct 691 ms 110544 KB Output is correct
38 Correct 734 ms 107344 KB Output is correct
39 Correct 718 ms 131096 KB Output is correct
40 Correct 666 ms 121084 KB Output is correct
41 Correct 546 ms 108312 KB Output is correct
42 Correct 573 ms 104620 KB Output is correct
43 Correct 817 ms 119492 KB Output is correct
44 Correct 599 ms 109656 KB Output is correct
45 Correct 530 ms 132036 KB Output is correct
46 Correct 571 ms 131528 KB Output is correct
47 Correct 793 ms 125868 KB Output is correct
48 Correct 711 ms 125668 KB Output is correct
49 Correct 713 ms 125952 KB Output is correct
50 Correct 683 ms 125048 KB Output is correct
51 Correct 729 ms 121128 KB Output is correct
52 Correct 655 ms 121772 KB Output is correct