Submission #972142

#	Time	Username	Problem	Language	Result	Execution time	Memory
972142		duckindog	Werewolf (IOI18_werewolf)	C++17	100 / 100	821 ms	161232 KiB

werewolf

#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 / 7
• Subtask 2: 8 / 8
• Subtask 3: 34 / 34
• Subtask 4: 51 / 51