Submission #957286

#	Time	Username	Problem	Language	Result	Execution time	Memory
957286		abczz	Werewolf (IOI18_werewolf)	C++14	100 / 100	1078 ms	182320 KiB

werewolf

#include "werewolf.h"
#include <iostream>
#include <array>
#include <algorithm>
#include <vector>
#define ll long long

using namespace std;

ll n;
struct MST{
  vector <ll> adj[200000];
  array <ll, 2> R[200000];
  ll P[200000], bl[200000][18], dfn[200000], ord[200000], cur = -1;
  ll dsu(ll u) {
    if (P[u] == u) return u;
    else return P[u] = dsu(P[u]);
  }
  void construct_lift() {
    for (int k=1; k<18; ++k) {
      for (int i=0; i<n; ++i) {
        bl[i][k] = bl[bl[i][k-1]][k-1];
      }
    }
  }
  ll find_ancestor(ll u, ll x) {
    for (int k=17; k>=0; --k) {
      if (u != x && (bl[u][k] == x || !((u < x) ^ (bl[u][k] < x)))) {
        u = bl[u][k];
      }
    }
    return u;
  }
  void dfs(ll u) {
    R[u][0] = ++cur;
    ord[cur] = u;
    dfn[u] = cur;
    for (auto v : adj[u]) {
      dfs(v);
    }
    R[u][1] = cur;
  }
}MN, MX;
struct SegTree{
  vector <ll> st[800000];
  void build(ll id, ll l, ll r) {
    st[id].resize(r-l+1);
    ll sz = 0;
    if (l == r) {
      st[id][sz++] = MN.dfn[MX.ord[l]];
      return;
    }
    ll mid = (l+r)/2;
    build(id*2, l, mid);
    build(id*2+1, mid+1, r);
    int i = 0, j = 0;
    while (i < st[id*2].size() && j < st[id*2+1].size()) {
      if (st[id*2][i] <= st[id*2+1][j]) st[id][sz++] = st[id*2][i++];
      else st[id][sz++] = st[id*2+1][j++];
    }
    while (i < st[id*2].size()) st[id][sz++] = st[id*2][i++];
    while (j < st[id*2+1].size()) st[id][sz++] = st[id*2+1][j++];
  }
  bool query(ll id, ll l, ll r, ll ql, ll qr, ll qx, ll qy) {
    if (qr < l || r < ql) return 0;
    else if (ql <= l && r <= qr) {
      auto it = lower_bound(st[id].begin(), st[id].end(), qx);
      if (it != st[id].end() && *it <= qy) return 1;
      else return 0;
    }
    ll mid = (l+r)/2;
    return query(id*2, l, mid, ql, qr, qx, qy) | query(id*2+1, mid+1, r, ql, qr, qx, qy);
  }
}ST;
vector <array<ll, 2>> edge;
std::vector<int> check_validity(int N, std::vector<int> X, std::vector<int> Y,
                                std::vector<int> S, std::vector<int> E,
                                std::vector<int> L, std::vector<int> R) {
  n = N;
  for (int i=0; i<N; ++i) {
    MN.P[i] = MX.P[i] = MN.bl[i][0] = MX.bl[i][0] = i;
  }
  for (int i=0; i<X.size(); ++i) {
    edge.push_back({X[i], Y[i]});
  }
  sort(edge.begin(), edge.end(), [](auto a, auto b) {
    return max(a[0], a[1]) < max(b[0], b[1]);
  });
  for (auto [u, v] : edge) {
    auto a = MN.dsu(u), b = MN.dsu(v);
    if (a != b) {
      if (a > b) swap(a, b);
      MN.P[a] = b;
      MN.adj[b].push_back(a);
      MN.bl[a][0] = b;
    }
  }
  MN.construct_lift();
  MN.dfs(n-1);
  sort(edge.begin(), edge.end(), [](auto a, auto b) {
    return min(a[0], a[1]) > min(b[0], b[1]);
  });
  for (auto [u, v] : edge) {
    auto a = MX.dsu(u), b = MX.dsu(v);
    if (a != b) {
      if (a < b) swap(a, b);
      MX.P[a] = b;
      MX.adj[b].push_back(a);
      MX.bl[a][0] = b;
    }
  }
  MX.construct_lift();
  MX.dfs(0);
  ST.build(1, 0, n-1);
  vector <int> Q;
  for (int i=0; i<S.size(); ++i) {
    auto a = MX.find_ancestor(S[i], L[i]);
    auto b = MN.find_ancestor(E[i], R[i]);
    Q.push_back(ST.query(1, 0, n-1, MX.R[a][0], MX.R[a][1], MN.R[b][0], MN.R[b][1]));
  }
  return Q;
}

Compilation message (stderr)

werewolf.cpp: In member function 'void SegTree::build(long long int, long long int, long long int)':
werewolf.cpp:57:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |     while (i < st[id*2].size() && j < st[id*2+1].size()) {
      |            ~~^~~~~~~~~~~~~~~~~
werewolf.cpp:57:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |     while (i < st[id*2].size() && j < st[id*2+1].size()) {
      |                                   ~~^~~~~~~~~~~~~~~~~~~
werewolf.cpp:61:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |     while (i < st[id*2].size()) st[id][sz++] = st[id*2][i++];
      |            ~~^~~~~~~~~~~~~~~~~
werewolf.cpp:62:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |     while (j < st[id*2+1].size()) st[id][sz++] = st[id*2+1][j++];
      |            ~~^~~~~~~~~~~~~~~~~~~
werewolf.cpp: In function 'std::vector<int> check_validity(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
werewolf.cpp:83:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |   for (int i=0; i<X.size(); ++i) {
      |                 ~^~~~~~~~~
werewolf.cpp:89:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   89 |   for (auto [u, v] : edge) {
      |             ^
werewolf.cpp:103:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  103 |   for (auto [u, v] : edge) {
      |             ^
werewolf.cpp:116:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  116 |   for (int i=0; i<S.size(); ++i) {
      |                 ~^~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 8 / 8
• Subtask 3: 34 / 34
• Subtask 4: 51 / 51