oj.uz

Submission #972142

# Submission time Handle Problem Language Result Execution time Memory
972142 2024-04-30T07:21:12 Z duckindog Werewolf (IOI18_werewolf) C++17
100 / 100
 821 ms 161232 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 st[N << 1], ed[N << 1], rvs[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; rvs[it] = u;
    
    for (const auto& v : ad[u]) { 
      f[v][0] = u;
      dfs(v, u);
    }

    ed[u] = it;
  }

} T[2];

struct Query {
  int cst, 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;

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[T[0].st[s[i]] - 1].push_back({-1, e[i], i});
    Q[T[0].ed[s[i]]].push_back({1, e[i], i});
  }
  f.n = T[1].it;

  vector<int> answer(q);
  for (int i = 1; i <= T[0].it; ++i) { 
    const auto& id = T[0].rvs[i];
    if (id < n) f.upd(T[1].st[id], 1);
    for (const auto& [cst, v, idx] : Q[i]) { 
      answer[idx] += cst * (f.que(T[1].ed[v]) - f.que(T[1].st[v] - 1));
    }
  }
  for (int i = 0; i < q; ++i) answer[i] = (answer[i] > 0);

  return answer;
}

#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 11 ms 42844 KB Output is correct
2 Correct 11 ms 42844 KB Output is correct
3 Correct 11 ms 42716 KB Output is correct
4 Correct 11 ms 42588 KB Output is correct
5 Correct 10 ms 42712 KB Output is correct
6 Correct 11 ms 42588 KB Output is correct
7 Correct 10 ms 42848 KB Output is correct
8 Correct 11 ms 42584 KB Output is correct
9 Correct 11 ms 42584 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 42844 KB Output is correct
2 Correct 11 ms 42844 KB Output is correct
3 Correct 11 ms 42716 KB Output is correct
4 Correct 11 ms 42588 KB Output is correct
5 Correct 10 ms 42712 KB Output is correct
6 Correct 11 ms 42588 KB Output is correct
7 Correct 10 ms 42848 KB Output is correct
8 Correct 11 ms 42584 KB Output is correct
9 Correct 11 ms 42584 KB Output is correct
10 Correct 18 ms 43684 KB Output is correct
11 Correct 16 ms 43688 KB Output is correct
12 Correct 16 ms 43612 KB Output is correct
13 Correct 16 ms 41564 KB Output is correct
14 Correct 16 ms 41560 KB Output is correct
15 Correct 17 ms 41564 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 676 ms 155488 KB Output is correct
2 Correct 595 ms 157528 KB Output is correct
3 Correct 524 ms 155348 KB Output is correct
4 Correct 494 ms 153900 KB Output is correct
5 Correct 517 ms 153996 KB Output is correct
6 Correct 596 ms 155076 KB Output is correct
7 Correct 595 ms 153792 KB Output is correct
8 Correct 537 ms 157584 KB Output is correct
9 Correct 442 ms 154584 KB Output is correct
10 Correct 397 ms 153548 KB Output is correct
11 Correct 403 ms 151716 KB Output is correct
12 Correct 463 ms 151040 KB Output is correct
13 Correct 760 ms 156248 KB Output is correct
14 Correct 736 ms 156244 KB Output is correct
15 Correct 745 ms 156492 KB Output is correct
16 Correct 755 ms 156496 KB Output is correct
17 Correct 600 ms 151352 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 42844 KB Output is correct
2 Correct 11 ms 42844 KB Output is correct
3 Correct 11 ms 42716 KB Output is correct
4 Correct 11 ms 42588 KB Output is correct
5 Correct 10 ms 42712 KB Output is correct
6 Correct 11 ms 42588 KB Output is correct
7 Correct 10 ms 42848 KB Output is correct
8 Correct 11 ms 42584 KB Output is correct
9 Correct 11 ms 42584 KB Output is correct
10 Correct 18 ms 43684 KB Output is correct
11 Correct 16 ms 43688 KB Output is correct
12 Correct 16 ms 43612 KB Output is correct
13 Correct 16 ms 41564 KB Output is correct
14 Correct 16 ms 41560 KB Output is correct
15 Correct 17 ms 41564 KB Output is correct
16 Correct 676 ms 155488 KB Output is correct
17 Correct 595 ms 157528 KB Output is correct
18 Correct 524 ms 155348 KB Output is correct
19 Correct 494 ms 153900 KB Output is correct
20 Correct 517 ms 153996 KB Output is correct
21 Correct 596 ms 155076 KB Output is correct
22 Correct 595 ms 153792 KB Output is correct
23 Correct 537 ms 157584 KB Output is correct
24 Correct 442 ms 154584 KB Output is correct
25 Correct 397 ms 153548 KB Output is correct
26 Correct 403 ms 151716 KB Output is correct
27 Correct 463 ms 151040 KB Output is correct
28 Correct 760 ms 156248 KB Output is correct
29 Correct 736 ms 156244 KB Output is correct
30 Correct 745 ms 156492 KB Output is correct
31 Correct 755 ms 156496 KB Output is correct
32 Correct 600 ms 151352 KB Output is correct
33 Correct 759 ms 154280 KB Output is correct
34 Correct 281 ms 75560 KB Output is correct
35 Correct 806 ms 156784 KB Output is correct
36 Correct 704 ms 153620 KB Output is correct
37 Correct 800 ms 156020 KB Output is correct
38 Correct 720 ms 154324 KB Output is correct
39 Correct 689 ms 159752 KB Output is correct
40 Correct 769 ms 159992 KB Output is correct
41 Correct 586 ms 153936 KB Output is correct
42 Correct 522 ms 151624 KB Output is correct
43 Correct 787 ms 159440 KB Output is correct
44 Correct 675 ms 155376 KB Output is correct
45 Correct 536 ms 157956 KB Output is correct
46 Correct 541 ms 158292 KB Output is correct
47 Correct 771 ms 158576 KB Output is correct
48 Correct 821 ms 158676 KB Output is correct
49 Correct 770 ms 158528 KB Output is correct
50 Correct 783 ms 158604 KB Output is correct
51 Correct 724 ms 161232 KB Output is correct
52 Correct 715 ms 160372 KB Output is correct