oj.uz

Submission #971782

# Submission time Handle Problem Language Result Execution time Memory
971782 2024-04-29T09:27:08 Z duckindog Werewolf (IOI18_werewolf) C++17
100 / 100
 871 ms 167492 KB 
#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 11 ms 55128 KB Output is correct
2 Correct 11 ms 55132 KB Output is correct
3 Correct 11 ms 55132 KB Output is correct
4 Correct 11 ms 55132 KB Output is correct
5 Correct 11 ms 55132 KB Output is correct
6 Correct 11 ms 55128 KB Output is correct
7 Correct 11 ms 55128 KB Output is correct
8 Correct 12 ms 55228 KB Output is correct
9 Correct 11 ms 55272 KB Output is correct

Subtask #2
8.0 / 8.0

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

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 858 ms 156124 KB Output is correct
2 Correct 683 ms 158528 KB Output is correct
3 Correct 575 ms 155176 KB Output is correct
4 Correct 641 ms 154956 KB Output is correct
5 Correct 608 ms 155156 KB Output is correct
6 Correct 770 ms 155896 KB Output is correct
7 Correct 802 ms 155340 KB Output is correct
8 Correct 598 ms 158468 KB Output is correct
9 Correct 489 ms 155640 KB Output is correct
10 Correct 487 ms 154448 KB Output is correct
11 Correct 535 ms 154544 KB Output is correct
12 Correct 596 ms 154852 KB Output is correct
13 Correct 732 ms 164316 KB Output is correct
14 Correct 708 ms 164308 KB Output is correct
15 Correct 700 ms 164052 KB Output is correct
16 Correct 711 ms 164220 KB Output is correct
17 Correct 756 ms 155200 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 55128 KB Output is correct
2 Correct 11 ms 55132 KB Output is correct
3 Correct 11 ms 55132 KB Output is correct
4 Correct 11 ms 55132 KB Output is correct
5 Correct 11 ms 55132 KB Output is correct
6 Correct 11 ms 55128 KB Output is correct
7 Correct 11 ms 55128 KB Output is correct
8 Correct 12 ms 55228 KB Output is correct
9 Correct 11 ms 55272 KB Output is correct
10 Correct 17 ms 55900 KB Output is correct
11 Correct 19 ms 55896 KB Output is correct
12 Correct 17 ms 55644 KB Output is correct
13 Correct 17 ms 55900 KB Output is correct
14 Correct 18 ms 55804 KB Output is correct
15 Correct 20 ms 55900 KB Output is correct
16 Correct 858 ms 156124 KB Output is correct
17 Correct 683 ms 158528 KB Output is correct
18 Correct 575 ms 155176 KB Output is correct
19 Correct 641 ms 154956 KB Output is correct
20 Correct 608 ms 155156 KB Output is correct
21 Correct 770 ms 155896 KB Output is correct
22 Correct 802 ms 155340 KB Output is correct
23 Correct 598 ms 158468 KB Output is correct
24 Correct 489 ms 155640 KB Output is correct
25 Correct 487 ms 154448 KB Output is correct
26 Correct 535 ms 154544 KB Output is correct
27 Correct 596 ms 154852 KB Output is correct
28 Correct 732 ms 164316 KB Output is correct
29 Correct 708 ms 164308 KB Output is correct
30 Correct 700 ms 164052 KB Output is correct
31 Correct 711 ms 164220 KB Output is correct
32 Correct 756 ms 155200 KB Output is correct
33 Correct 807 ms 158032 KB Output is correct
34 Correct 266 ms 90708 KB Output is correct
35 Correct 816 ms 163244 KB Output is correct
36 Correct 794 ms 157272 KB Output is correct
37 Correct 833 ms 161852 KB Output is correct
38 Correct 829 ms 158300 KB Output is correct
39 Correct 781 ms 163644 KB Output is correct
40 Correct 871 ms 166468 KB Output is correct
41 Correct 680 ms 160104 KB Output is correct
42 Correct 671 ms 155524 KB Output is correct
43 Correct 777 ms 167492 KB Output is correct
44 Correct 776 ms 161104 KB Output is correct
45 Correct 627 ms 162480 KB Output is correct
46 Correct 650 ms 162640 KB Output is correct
47 Correct 762 ms 164356 KB Output is correct
48 Correct 727 ms 163760 KB Output is correct
49 Correct 737 ms 164232 KB Output is correct
50 Correct 733 ms 163792 KB Output is correct
51 Correct 789 ms 167156 KB Output is correct
52 Correct 828 ms 167368 KB Output is correct