Submission #827457

#	Time	Username	Problem	Language	Result	Execution time	Memory
827457		WLZ	Werewolf (IOI18_werewolf)	C++17	100 / 100	722 ms	92076 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;

const int INF = 0x3f3f3f3f;

struct query {
  int from, to, l, r, idx;
};

int n, m, q, dfs_cnt;
vector< vector<int> > g, g2;
vector<query> queries;
vector<int> ans, p, ord_l, ord_r;
vector< pair<int, int> > range;

int root(int u) {
  if (p[u] == -1) return u;
  return p[u] = root(p[u]);
}

int connect(int u, int v) {
  u = root(u); v = root(v);
  if (u == v) return u;
  p[v] = p[u] = (int) p.size();
  p.push_back(-1);
  g2.push_back({u, v});
  return (int) p.size() - 1;
}

pair<int, int> dfs(int u, bool phase) {
  if (g2[u].empty()) {
    if (phase) ord_l[u] = dfs_cnt++;
    else ord_r[u] = dfs_cnt++;
    return range[u] = {dfs_cnt - 1, dfs_cnt - 1};
  }
  range[u] = {INF, -INF};
  for (auto &v : g2[u]) {
    int l, r;
    tie(l, r) = dfs(v, phase);
    range[u].first = min(range[u].first, l);
    range[u].second = max(range[u].second, r);
  }
  return range[u];
}

struct node {
  int l, r, val;
  node *left, *right;
};

node *build(int l, int r) {
  if (l == r) return new node{l, r, -INF, nullptr, nullptr};
  node *left = build(l, (l + r) / 2), *right = build((l + r) / 2 + 1, r);
  return new node{l, r, -INF, left, right};
}

void update(node *cur, int idx, int v) {
  if (cur->l == cur->r) {
    cur->val = v;
    return;
  }
  if (idx <= cur->left->r) update(cur->left, idx, v);
  else update(cur->right, idx, v);
  cur->val = max(cur->left->val, cur->right->val);
}

int query_max(node *cur, int l, int r) {
  if (cur->l > r || cur->r < l) return -INF;
  if (l <= cur->l && cur->r <= r) return cur->val;
  return max(query_max(cur->left, l, r), query_max(cur->right, l, r));
}

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 = (int) X.size(); q = (int) S.size();
  g.resize(n);
  for (int i = 0; i < m; i++) {
    g[X[i]].push_back(Y[i]);
    g[Y[i]].push_back(X[i]);
  }
  vector<int> rep_l(q + 1), rep_r(q + 1);
  vector< pair<int, int> > range_l(q + 1), range_r(q + 1);
  for (int i = 0; i < q; i++) queries.push_back({S[i], E[i], L[i], R[i], i});
  queries.push_back({0, n - 1, 0, n - 1, q}); q++;
  sort(queries.begin(), queries.end(), [](const query &a, const query &b) {
    return a.l > b.l;
  });
  ans.resize(q);
  g2.assign(n, vector<int>());
  int u = n;
  p.assign(n, -1);
  vector<bool> used(n, false);
  for (auto &[from, to, l, r, idx] : queries) {
    while (u > l) {
      u--;
      used[u] = true;
      for (auto &v : g[u]) if (used[v]) connect(u, v);
    }
    rep_l[idx] = root(from);
  }
  ord_l.resize((int) p.size());
  dfs_cnt = 0;
  range.resize((int) p.size());
  dfs((int) p.size() - 1, true);
  for (auto &[from, to, l, r, idx] : queries) range_l[idx] = range[rep_l[idx]];

  sort(queries.begin(), queries.end(), [](const query &a, const query &b) {
    return a.r < b.r;
  });
  ans.resize(q);
  g2.assign(n, vector<int>());
  u = -1;
  p.assign(n, -1);
  used.assign(n, false);
  for (auto &[from, to, l, r, idx] : queries) {
    while (u < r) {
      u++;
      used[u] = true;
      for (auto &v : g[u]) if (used[v]) connect(u, v);
    }
    rep_r[idx] = root(to);
  }
  ord_r.resize((int) p.size());
  dfs_cnt = 0;
  range.resize((int) p.size());
  dfs((int) p.size() - 1, false);
  for (auto &[from, to, l, r, idx] : queries) range_r[idx] = range[rep_r[idx]];
  vector<int> ord(n); iota(ord.begin(), ord.end(), 0);
  sort(ord.begin(), ord.end(), [&](int a, int b) {
    return ord_r[a] < ord_r[b];
  });
  sort(queries.begin(), queries.end(), [&](const query &a, const query &b) {
    return range_r[a.idx].second < range_r[b.idx].second;
  });
  u = -1;
  node *root = build(0, n - 1);
  for (auto &[from, to, l, r, idx] : queries) {
    while (u < range_r[idx].second) {
      u++;
      update(root, ord_l[ord[u]], ord_r[ord[u]]);
    }
    ans[idx] = query_max(root, range_l[idx].first, range_l[idx].second) >= range_r[idx].first;
  }
  ans.pop_back();
  return move(ans);
}

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