oj.uz

Submission #972128

# Submission time Handle Problem Language Result Execution time Memory
972128 2024-04-30T06:40:39 Z duckindog Werewolf (IOI18_werewolf) C++17
100 / 100
 843 ms 169240 KB 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>

#ifndef LOCAL
#include "werewolf.h"
#endif

using namespace std;

const int N = 200'000 + 10;
int n, m, q;
vector<int> ad[N];
 
struct Edge { 
  int u, v;
} edge[N << 1];

struct couldCan { 
  vector<int> ad[N << 1];
  int f[N << 1][19];
  int sz[N << 1], st[N << 1], ed[N << 1], it;
  int w[N << 1];

  int id[N << 1];

  couldCan() { memset(id, -1, sizeof id); }

  int root(int u) { return id[u] < 0 ? u : id[u] = root(id[u]); }
  void add(int u, int v) {
    u = root(u); v = root(v);
    if (u == v) return;
    if (u < v) swap(u, v);
    id[v] = u;
  }

  void dfs(int u, int p = -1) { 
    for (int i = 1; i <= 18; ++i) f[u][i] = f[f[u][i - 1]][i - 1];
    
    st[u] = ++it;
    
    for (const auto& v : ad[u]) { 
      f[v][0] = u;
      dfs(v, u);
      sz[u] += sz[v] + 1;
    }

    ed[u] = it;
  }

} T[2];

struct Query {
  int v, idx;
};
vector<Query> Q[N << 1];

struct BIT { 
  int n;
  int bit[N << 1], g[N << 1], idx;
  void clear() { idx += 1; }
  int& val(int i) { 
    if (g[i] != idx) {
      bit[i] = 0;
      g[i] = idx;
    }
    return bit[i];
  }
  void upd(int i, int x) {
    for (; i <= n; i += i & -i) val(i) += x;
  }
  int que(int i) { 
    int ret = 0;
    for (; i; i -= i & -i) ret += val(i);
    return ret;
  }
} f;

bool answer[N];

vector<int> node;
void get(int u) { 
  if (u < n) node.push_back(u);
  for (const auto& v : T[0].ad[u]) get(v);
}

void dfs(int u) { 
  sort(T[0].ad[u].begin(), T[0].ad[u].end(), [&](const auto& a, const auto& b) { 
    return T[0].sz[a] < T[0].sz[b];
  });
  int heavy = (!T[0].ad[u].size() ? -1 : T[0].ad[u].end()[-1]);
  f.clear();
  for (const auto& v : T[0].ad[u]) dfs(v);
  
  node.clear();
  for (const auto& v : T[0].ad[u]) if (v != heavy) get(v);

  if (u < n) f.upd(T[1].st[u], 1);
  for (const auto& x : node) f.upd(T[1].st[x], 1);

  for (const auto& [v, idx] : Q[u]) { 
    answer[idx] = f.que(T[1].ed[v]) - f.que(T[1].st[v] - 1);
  }
}

vector<int> check_validity(int n_, vector<int> x, vector<int> y,
                                vector<int> s, vector<int> e,
                                vector<int> l, vector<int> r) {
  n = n_; m = x.size(); q = s.size();

  for (int i = 0; i < m; ++i) { 
    int u = x[i], v = y[i];
    ad[u].push_back(v);
    ad[v].push_back(u);
    edge[i] = {u, v};
  }

  for (int t = 0; t < 2; ++t) { 
    auto& tree = T[t];

    auto weight = [&](const auto& edge) { 
      if (!t) return min(edge.u, edge.v);
      return max(edge.u, edge.v);
    };
    sort(edge, edge + m, [&](const auto& a, const auto& b) { 
      if (!t) return weight(a) > weight(b);
      return weight(a) < weight(b);
    });

    int it = n - 1;
    for (int i = 0; i < m; ++i) { 
      auto [u, v] = edge[i];
      int w = weight(edge[i]);

      if (tree.root(u) == tree.root(v)) continue;

      it += 1;
      
      tree.add(it, u = tree.root(u)); tree.add(it, v = tree.root(v));
      tree.ad[it].push_back(u);
      tree.ad[it].push_back(v);
      
      tree.w[it] = w;
    }
    tree.dfs(tree.f[it][0] = it);
  }

  for (int i = 0; i < q; ++i) { 
    { //human
      const auto& tree = T[0];
      for (int j = 18; j >= 0; --j) if (tree.w[tree.f[s[i]][j]] >= l[i]) s[i] = tree.f[s[i]][j];
    }
    { //wolf
      const auto& tree = T[1];
      for (int j = 18; j >= 0; --j) if (tree.w[tree.f[e[i]][j]] <= r[i]) e[i] = tree.f[e[i]][j];
    }
    Q[s[i]].push_back({e[i], i});
  }
  f.n = T[1].it;
  
  dfs(T[0].it - 1);
  return vector<int>(answer, answer + q);
}

#ifdef LOCAL
int32_t main() { 
  cin.tie(0)->sync_with_stdio(0);

  int n_, m_, q_; cin >> n_ >> m_ >> q_;
  vector<int> x_(m_), y_(m_), s_(q_), e_(q_), l_(q_), r_(q_);
  for (int j = 0; j < m_; ++j) cin >> x_[j] >> y_[j];

  for (int i = 0; i < q_; ++i) cin >> s_[i] >> e_[i] >> l_[i] >> r_[i];

  for (const auto& x : check_validity(n_, x_, y_, s_, e_, l_, r_)) cerr << x << "\n";
}
#endif

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 55380 KB Output is correct
2 Correct 13 ms 55384 KB Output is correct
3 Correct 15 ms 55132 KB Output is correct
4 Correct 12 ms 55260 KB Output is correct
5 Correct 13 ms 55132 KB Output is correct
6 Correct 12 ms 55132 KB Output is correct
7 Correct 12 ms 55132 KB Output is correct
8 Correct 12 ms 55128 KB Output is correct
9 Correct 12 ms 55132 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 55380 KB Output is correct
2 Correct 13 ms 55384 KB Output is correct
3 Correct 15 ms 55132 KB Output is correct
4 Correct 12 ms 55260 KB Output is correct
5 Correct 13 ms 55132 KB Output is correct
6 Correct 12 ms 55132 KB Output is correct
7 Correct 12 ms 55132 KB Output is correct
8 Correct 12 ms 55128 KB Output is correct
9 Correct 12 ms 55132 KB Output is correct
10 Correct 17 ms 55900 KB Output is correct
11 Correct 17 ms 55900 KB Output is correct
12 Correct 19 ms 55644 KB Output is correct
13 Correct 17 ms 55896 KB Output is correct
14 Correct 20 ms 55900 KB Output is correct
15 Correct 19 ms 55888 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 808 ms 154692 KB Output is correct
2 Correct 622 ms 157268 KB Output is correct
3 Correct 577 ms 154380 KB Output is correct
4 Correct 532 ms 153388 KB Output is correct
5 Correct 560 ms 153652 KB Output is correct
6 Correct 687 ms 154352 KB Output is correct
7 Correct 739 ms 153712 KB Output is correct
8 Correct 517 ms 156988 KB Output is correct
9 Correct 459 ms 153980 KB Output is correct
10 Correct 459 ms 153144 KB Output is correct
11 Correct 491 ms 152976 KB Output is correct
12 Correct 565 ms 153036 KB Output is correct
13 Correct 709 ms 165616 KB Output is correct
14 Correct 711 ms 165572 KB Output is correct
15 Correct 688 ms 165768 KB Output is correct
16 Correct 710 ms 166012 KB Output is correct
17 Correct 721 ms 153664 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 55380 KB Output is correct
2 Correct 13 ms 55384 KB Output is correct
3 Correct 15 ms 55132 KB Output is correct
4 Correct 12 ms 55260 KB Output is correct
5 Correct 13 ms 55132 KB Output is correct
6 Correct 12 ms 55132 KB Output is correct
7 Correct 12 ms 55132 KB Output is correct
8 Correct 12 ms 55128 KB Output is correct
9 Correct 12 ms 55132 KB Output is correct
10 Correct 17 ms 55900 KB Output is correct
11 Correct 17 ms 55900 KB Output is correct
12 Correct 19 ms 55644 KB Output is correct
13 Correct 17 ms 55896 KB Output is correct
14 Correct 20 ms 55900 KB Output is correct
15 Correct 19 ms 55888 KB Output is correct
16 Correct 808 ms 154692 KB Output is correct
17 Correct 622 ms 157268 KB Output is correct
18 Correct 577 ms 154380 KB Output is correct
19 Correct 532 ms 153388 KB Output is correct
20 Correct 560 ms 153652 KB Output is correct
21 Correct 687 ms 154352 KB Output is correct
22 Correct 739 ms 153712 KB Output is correct
23 Correct 517 ms 156988 KB Output is correct
24 Correct 459 ms 153980 KB Output is correct
25 Correct 459 ms 153144 KB Output is correct
26 Correct 491 ms 152976 KB Output is correct
27 Correct 565 ms 153036 KB Output is correct
28 Correct 709 ms 165616 KB Output is correct
29 Correct 711 ms 165572 KB Output is correct
30 Correct 688 ms 165768 KB Output is correct
31 Correct 710 ms 166012 KB Output is correct
32 Correct 721 ms 153664 KB Output is correct
33 Correct 803 ms 157376 KB Output is correct
34 Correct 253 ms 90548 KB Output is correct
35 Correct 842 ms 164432 KB Output is correct
36 Correct 802 ms 156240 KB Output is correct
37 Correct 843 ms 162500 KB Output is correct
38 Correct 811 ms 157440 KB Output is correct
39 Correct 793 ms 162668 KB Output is correct
40 Correct 843 ms 166700 KB Output is correct
41 Correct 744 ms 160084 KB Output is correct
42 Correct 638 ms 154364 KB Output is correct
43 Correct 811 ms 169240 KB Output is correct
44 Correct 727 ms 161864 KB Output is correct
45 Correct 616 ms 161216 KB Output is correct
46 Correct 687 ms 161452 KB Output is correct
47 Correct 690 ms 165972 KB Output is correct
48 Correct 701 ms 165580 KB Output is correct
49 Correct 754 ms 165696 KB Output is correct
50 Correct 711 ms 165792 KB Output is correct
51 Correct 768 ms 167272 KB Output is correct
52 Correct 787 ms 167376 KB Output is correct