Submission #1226357

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226357		Lemser	Werewolf (IOI18_werewolf)	C++20	100 / 100	1510 ms	370728 KiB

werewolf

#include "werewolf.h"

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx2")
#pragma GCC target("popcnt")
using namespace std;
 
using ll = long long;
using ull = unsigned long long;
using lld = long double;
using ii = pair<int,int>;
using pll = pair<ll, ll>;
 
using vi = vector<int>;
using vll = vector<ll>;
using vii = vector<ii>;
using vpll = vector<pll>;
using vlld = vector<lld>;
 
#define all(x) x.begin(),x.end()
#define lsb(x) x&(-x)
#define gcd(a,b) __gcd(a,b)
#define sz(x) (int)x.size()
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define fls cout.flush()
 
#define fore(i, l, r) for (auto i = l; i < r; i++)
#define fo(i, n) fore (i, 0, n)
#define forex(i, r, l) for (auto i = r-1; i >= l; i--)
#define ffo(i, n) forex (i, n, 0)
 
bool cmin(ll &a, ll b) { if (b < a) { a=b; return 1; } return 0; }
bool cmax(ll &a, ll b) { if (b > a) { a=b; return 1; } return 0; }
 
const ll INF = 1e18;
const int LOG = 20;

struct SegTree {
  
  vector<vll> st;
  ll n;

  SegTree () {}
  SegTree (ll n):n(n), st(4*n+4) {}

  void build (vll &a) { build(1, 0, n-1, a); }
  void build (ll id, ll l, ll r, vll &a) {
      fore (i, l, r+1) st[id].pb(a[i]);
      sort(all(st[id]));
      if (l == r) return;
      ll m = (l+r)/2;
      build(id*2, l, m, a);
      build(id*2+1, m+1, r, a);
  }

  ll query (ll l, ll r, ll a, ll b) { return query(1, 0, n-1, l, r, a, b); }
  ll query (ll id, ll l, ll r, ll i, ll j, ll a, ll b){
      if(l>j || r<i) return 0;
      if(l>=i && r<=j) {
          b = upper_bound(all(st[id]), b) - st[id].begin();
          a = lower_bound(all(st[id]), a) - st[id].begin();
          return b - a;
      }
      ll m = (l+r)/2;
      return query(id*2, l, m, i, j, a, b) + query(id*2+1, m+1, r, i, j, a, b);
  }
};

struct DSU {

  vector<vll> graph, up;
  vll pa, tin, tout;
  ll n, tr;

  DSU (ll n): n(n), tr(0), pa(n), graph(n), up(n, vll(LOG)), tin(n, 0), tout(n, 0) { iota(all(pa), 0); }

  ll find (ll i) { return (i == pa[i] ? i : pa[i] = find(pa[i])); }
  void unite (ll a, ll b) {
    a = find(a);
    b = find(b);
    if (a == b) return;
    graph[a].pb(b);
    pa[b] = a;
  }

  void dfs (ll u, ll p) {
    up[u][0] = p;
    fore (i, 1, LOG) {
      up[u][i] = up[up[u][i-1]][i-1];
    }
    tin[u] = tr++;
    for (ll v: graph[u]) {
      if (v == p) continue;
      dfs(v, u);
    }
    tout[u] = tr-1;
  }

  void build (vll &ottin, vll &a) {
    fo (i, n) a[i] = INF;
    fo (i, n/2) {
      a[tin[i]] = ottin[i];
    }
  }

  void print () {
    cout << "Tree\n";
    fo (x, n) {
      for (ll v: graph[x]) {
        cout << x << ' ' << v << '\n';
      }
    }
    cout << "Tour\n";
    fo (x, n) cout << tin[x] << ' ' << tout[x] << '\n';
  }
};

vector<vll> graph;

vector<int> check_validity(int n, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
  int Q = S.size(), m = X.size();
  graph = vector<vll>(n);
  fo (i, m) {
    graph[X[i]].pb(Y[i]);
    graph[Y[i]].pb(X[i]);
  }
  DSU hum(2*n), wolf(2*n);
  SegTree st(2*n);
  ffo (x, n-1) {
    // x+n es el nuevo padre
    hum.unite(x+n, x);
    for (ll y: graph[x]) {
      if (y < x) continue;
      hum.unite(x+n, y); 
    }
  }
  fore (x, 1, n) {
    wolf.unite(x+n, x);
    for (ll y: graph[x]) {
      if (y > x) continue;
      wolf.unite(x+n, y);
    }
  }
  hum.dfs(n, n);
  wolf.dfs(2*n-1, 2*n-1);
  vll a(2*n);
  hum.build(wolf.tin, a);
  st.build(a);
  vector<int> ans(Q, 0);
  fo (qi, Q) {
    ll A = S[qi], B = E[qi];
    ffo (i, LOG) {
      if (hum.up[A][i] >= L[qi]+n) 
        A = hum.up[A][i];
    }
    ffo (i, LOG) {
      if (wolf.up[B][i] <= R[qi]+n)
        B = wolf.up[B][i];
    }
    ans[qi] = ((st.query(hum.tin[A], hum.tout[A], wolf.tin[B], wolf.tout[B])) >= 1);
  }
  return ans;
}

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