oj.uz

Submission #971756

# Submission time Handle Problem Language Result Execution time Memory
971756 2024-04-29T09:00:50 Z duckindog Werewolf (IOI18_werewolf) C++17
15 / 100
 4000 ms 158816 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];

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[2];
int idxB;

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[0].clear(); f[1].clear();
  for (const auto& v : T[0].ad[u]) { 
    dfs(v);
    f[idxB ^ 1].clear();
    swap(f[idxB], f[idxB ^ 1]);
    idxB ^= 1;
  }

  node.clear();
  for (const auto& v : T[0].ad[u]) if (v != heavy) get(v);

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

  for (const auto& [v, idx] : Q[u]) { 
    answer[idx] = f[idxB].que(T[1].ed[v]) - f[idxB].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[0].n = f[1].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 69 ms 62024 KB Output is correct
2 Correct 67 ms 62012 KB Output is correct
3 Correct 25 ms 61788 KB Output is correct
4 Correct 17 ms 61784 KB Output is correct
5 Correct 79 ms 62012 KB Output is correct
6 Correct 71 ms 61784 KB Output is correct
7 Correct 70 ms 61788 KB Output is correct
8 Correct 71 ms 61784 KB Output is correct
9 Correct 73 ms 61784 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 62024 KB Output is correct
2 Correct 67 ms 62012 KB Output is correct
3 Correct 25 ms 61788 KB Output is correct
4 Correct 17 ms 61784 KB Output is correct
5 Correct 79 ms 62012 KB Output is correct
6 Correct 71 ms 61784 KB Output is correct
7 Correct 70 ms 61788 KB Output is correct
8 Correct 71 ms 61784 KB Output is correct
9 Correct 73 ms 61784 KB Output is correct
10 Correct 1716 ms 62948 KB Output is correct
11 Correct 1678 ms 62908 KB Output is correct
12 Correct 1942 ms 62608 KB Output is correct
13 Correct 1826 ms 62896 KB Output is correct
14 Correct 1750 ms 62604 KB Output is correct
15 Correct 1735 ms 63020 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4022 ms 158816 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 62024 KB Output is correct
2 Correct 67 ms 62012 KB Output is correct
3 Correct 25 ms 61788 KB Output is correct
4 Correct 17 ms 61784 KB Output is correct
5 Correct 79 ms 62012 KB Output is correct
6 Correct 71 ms 61784 KB Output is correct
7 Correct 70 ms 61788 KB Output is correct
8 Correct 71 ms 61784 KB Output is correct
9 Correct 73 ms 61784 KB Output is correct
10 Correct 1716 ms 62948 KB Output is correct
11 Correct 1678 ms 62908 KB Output is correct
12 Correct 1942 ms 62608 KB Output is correct
13 Correct 1826 ms 62896 KB Output is correct
14 Correct 1750 ms 62604 KB Output is correct
15 Correct 1735 ms 63020 KB Output is correct
16 Execution timed out 4022 ms 158816 KB Time limit exceeded
17 Halted 0 ms 0 KB -