oj.uz

Submission #971774

# Submission time Handle Problem Language Result Execution time Memory
971774 2024-04-29T09:20:56 Z duckindog Werewolf (IOI18_werewolf) C++17
49 / 100
 878 ms 163488 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 idxM, idxS;

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);
    swap(idxM, idxS);
  }
  
  node.clear();
  for (const auto& v : T[0].ad[u]) if (v != heavy) get(v);

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

  for (const auto& [v, idx] : Q[u]) { 
    answer[idx] = f[idxM].que(T[1].ed[v]) - f[idxM].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 25 ms 56656 KB Output is correct
2 Correct 11 ms 56668 KB Output is correct
3 Correct 11 ms 56868 KB Output is correct
4 Correct 14 ms 56924 KB Output is correct
5 Correct 11 ms 56668 KB Output is correct
6 Correct 12 ms 56668 KB Output is correct
7 Correct 12 ms 56760 KB Output is correct
8 Correct 11 ms 56796 KB Output is correct
9 Correct 11 ms 56860 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 56656 KB Output is correct
2 Correct 11 ms 56668 KB Output is correct
3 Correct 11 ms 56868 KB Output is correct
4 Correct 14 ms 56924 KB Output is correct
5 Correct 11 ms 56668 KB Output is correct
6 Correct 12 ms 56668 KB Output is correct
7 Correct 12 ms 56760 KB Output is correct
8 Correct 11 ms 56796 KB Output is correct
9 Correct 11 ms 56860 KB Output is correct
10 Correct 17 ms 57436 KB Output is correct
11 Correct 17 ms 57476 KB Output is correct
12 Correct 17 ms 57180 KB Output is correct
13 Correct 18 ms 57436 KB Output is correct
14 Correct 17 ms 57432 KB Output is correct
15 Correct 20 ms 57436 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 878 ms 146244 KB Output is correct
2 Correct 588 ms 156168 KB Output is correct
3 Correct 561 ms 153516 KB Output is correct
4 Correct 585 ms 152628 KB Output is correct
5 Correct 614 ms 153172 KB Output is correct
6 Correct 706 ms 153500 KB Output is correct
7 Correct 756 ms 152820 KB Output is correct
8 Correct 557 ms 155988 KB Output is correct
9 Correct 482 ms 154052 KB Output is correct
10 Correct 495 ms 152152 KB Output is correct
11 Correct 507 ms 153272 KB Output is correct
12 Correct 605 ms 152980 KB Output is correct
13 Correct 727 ms 162512 KB Output is correct
14 Correct 744 ms 163488 KB Output is correct
15 Correct 734 ms 162692 KB Output is correct
16 Correct 744 ms 162464 KB Output is correct
17 Correct 763 ms 153560 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 56656 KB Output is correct
2 Correct 11 ms 56668 KB Output is correct
3 Correct 11 ms 56868 KB Output is correct
4 Correct 14 ms 56924 KB Output is correct
5 Correct 11 ms 56668 KB Output is correct
6 Correct 12 ms 56668 KB Output is correct
7 Correct 12 ms 56760 KB Output is correct
8 Correct 11 ms 56796 KB Output is correct
9 Correct 11 ms 56860 KB Output is correct
10 Correct 17 ms 57436 KB Output is correct
11 Correct 17 ms 57476 KB Output is correct
12 Correct 17 ms 57180 KB Output is correct
13 Correct 18 ms 57436 KB Output is correct
14 Correct 17 ms 57432 KB Output is correct
15 Correct 20 ms 57436 KB Output is correct
16 Correct 878 ms 146244 KB Output is correct
17 Correct 588 ms 156168 KB Output is correct
18 Correct 561 ms 153516 KB Output is correct
19 Correct 585 ms 152628 KB Output is correct
20 Correct 614 ms 153172 KB Output is correct
21 Correct 706 ms 153500 KB Output is correct
22 Correct 756 ms 152820 KB Output is correct
23 Correct 557 ms 155988 KB Output is correct
24 Correct 482 ms 154052 KB Output is correct
25 Correct 495 ms 152152 KB Output is correct
26 Correct 507 ms 153272 KB Output is correct
27 Correct 605 ms 152980 KB Output is correct
28 Correct 727 ms 162512 KB Output is correct
29 Correct 744 ms 163488 KB Output is correct
30 Correct 734 ms 162692 KB Output is correct
31 Correct 744 ms 162464 KB Output is correct
32 Correct 763 ms 153560 KB Output is correct
33 Correct 831 ms 156732 KB Output is correct
34 Runtime error 179 ms 132948 KB Execution killed with signal 11
35 Halted 0 ms 0 KB -