oj.uz

Submission #971776

# Submission time Handle Problem Language Result Execution time Memory
971776 2024-04-29T09:23:53 Z duckindog Werewolf (IOI18_werewolf) C++17
100 / 100
 926 ms 212048 KB 
#include <bits/stdc++.h>

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

using namespace std;

const int N = 400'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][20];
  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 <= 19; ++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 18 ms 82520 KB Output is correct
2 Correct 20 ms 82524 KB Output is correct
3 Correct 20 ms 86620 KB Output is correct
4 Correct 17 ms 82520 KB Output is correct
5 Correct 17 ms 82640 KB Output is correct
6 Correct 17 ms 84656 KB Output is correct
7 Correct 18 ms 82524 KB Output is correct
8 Correct 18 ms 82520 KB Output is correct
9 Correct 17 ms 82524 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 82520 KB Output is correct
2 Correct 20 ms 82524 KB Output is correct
3 Correct 20 ms 86620 KB Output is correct
4 Correct 17 ms 82520 KB Output is correct
5 Correct 17 ms 82640 KB Output is correct
6 Correct 17 ms 84656 KB Output is correct
7 Correct 18 ms 82524 KB Output is correct
8 Correct 18 ms 82520 KB Output is correct
9 Correct 17 ms 82524 KB Output is correct
10 Correct 24 ms 85336 KB Output is correct
11 Correct 23 ms 83292 KB Output is correct
12 Correct 23 ms 83292 KB Output is correct
13 Correct 23 ms 83292 KB Output is correct
14 Correct 23 ms 83292 KB Output is correct
15 Correct 24 ms 83372 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 850 ms 192840 KB Output is correct
2 Correct 660 ms 195660 KB Output is correct
3 Correct 558 ms 194644 KB Output is correct
4 Correct 607 ms 194196 KB Output is correct
5 Correct 590 ms 196688 KB Output is correct
6 Correct 706 ms 196148 KB Output is correct
7 Correct 816 ms 194008 KB Output is correct
8 Correct 570 ms 198800 KB Output is correct
9 Correct 489 ms 198088 KB Output is correct
10 Correct 479 ms 197116 KB Output is correct
11 Correct 495 ms 197156 KB Output is correct
12 Correct 584 ms 197072 KB Output is correct
13 Correct 758 ms 205636 KB Output is correct
14 Correct 704 ms 204280 KB Output is correct
15 Correct 725 ms 204308 KB Output is correct
16 Correct 708 ms 204468 KB Output is correct
17 Correct 783 ms 195160 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 82520 KB Output is correct
2 Correct 20 ms 82524 KB Output is correct
3 Correct 20 ms 86620 KB Output is correct
4 Correct 17 ms 82520 KB Output is correct
5 Correct 17 ms 82640 KB Output is correct
6 Correct 17 ms 84656 KB Output is correct
7 Correct 18 ms 82524 KB Output is correct
8 Correct 18 ms 82520 KB Output is correct
9 Correct 17 ms 82524 KB Output is correct
10 Correct 24 ms 85336 KB Output is correct
11 Correct 23 ms 83292 KB Output is correct
12 Correct 23 ms 83292 KB Output is correct
13 Correct 23 ms 83292 KB Output is correct
14 Correct 23 ms 83292 KB Output is correct
15 Correct 24 ms 83372 KB Output is correct
16 Correct 850 ms 192840 KB Output is correct
17 Correct 660 ms 195660 KB Output is correct
18 Correct 558 ms 194644 KB Output is correct
19 Correct 607 ms 194196 KB Output is correct
20 Correct 590 ms 196688 KB Output is correct
21 Correct 706 ms 196148 KB Output is correct
22 Correct 816 ms 194008 KB Output is correct
23 Correct 570 ms 198800 KB Output is correct
24 Correct 489 ms 198088 KB Output is correct
25 Correct 479 ms 197116 KB Output is correct
26 Correct 495 ms 197156 KB Output is correct
27 Correct 584 ms 197072 KB Output is correct
28 Correct 758 ms 205636 KB Output is correct
29 Correct 704 ms 204280 KB Output is correct
30 Correct 725 ms 204308 KB Output is correct
31 Correct 708 ms 204468 KB Output is correct
32 Correct 783 ms 195160 KB Output is correct
33 Correct 862 ms 198496 KB Output is correct
34 Correct 269 ms 118888 KB Output is correct
35 Correct 837 ms 207620 KB Output is correct
36 Correct 806 ms 201940 KB Output is correct
37 Correct 916 ms 207428 KB Output is correct
38 Correct 828 ms 197576 KB Output is correct
39 Correct 883 ms 205396 KB Output is correct
40 Correct 926 ms 212048 KB Output is correct
41 Correct 794 ms 204176 KB Output is correct
42 Correct 710 ms 199744 KB Output is correct
43 Correct 901 ms 211524 KB Output is correct
44 Correct 792 ms 206680 KB Output is correct
45 Correct 682 ms 206316 KB Output is correct
46 Correct 757 ms 206988 KB Output is correct
47 Correct 810 ms 208552 KB Output is correct
48 Correct 756 ms 208880 KB Output is correct
49 Correct 813 ms 208580 KB Output is correct
50 Correct 783 ms 208364 KB Output is correct
51 Correct 823 ms 211344 KB Output is correct
52 Correct 797 ms 211404 KB Output is correct