oj.uz

Submission #827457

# Submission time Handle Problem Language Result Execution time Memory
827457 2023-08-16T13:39:28 Z WLZ Werewolf (IOI18_werewolf) C++17
100 / 100
 722 ms 92076 KB 
#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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 296 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 296 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 5 ms 1492 KB Output is correct
11 Correct 5 ms 1492 KB Output is correct
12 Correct 5 ms 1492 KB Output is correct
13 Correct 5 ms 1592 KB Output is correct
14 Correct 5 ms 1588 KB Output is correct
15 Correct 6 ms 1592 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 534 ms 81560 KB Output is correct
2 Correct 455 ms 86364 KB Output is correct
3 Correct 436 ms 83160 KB Output is correct
4 Correct 433 ms 81876 KB Output is correct
5 Correct 488 ms 81804 KB Output is correct
6 Correct 523 ms 81652 KB Output is correct
7 Correct 467 ms 81572 KB Output is correct
8 Correct 457 ms 86340 KB Output is correct
9 Correct 338 ms 83216 KB Output is correct
10 Correct 376 ms 81896 KB Output is correct
11 Correct 399 ms 81680 KB Output is correct
12 Correct 363 ms 81624 KB Output is correct
13 Correct 427 ms 86148 KB Output is correct
14 Correct 531 ms 86256 KB Output is correct
15 Correct 468 ms 86140 KB Output is correct
16 Correct 546 ms 86280 KB Output is correct
17 Correct 577 ms 81468 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 296 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 5 ms 1492 KB Output is correct
11 Correct 5 ms 1492 KB Output is correct
12 Correct 5 ms 1492 KB Output is correct
13 Correct 5 ms 1592 KB Output is correct
14 Correct 5 ms 1588 KB Output is correct
15 Correct 6 ms 1592 KB Output is correct
16 Correct 534 ms 81560 KB Output is correct
17 Correct 455 ms 86364 KB Output is correct
18 Correct 436 ms 83160 KB Output is correct
19 Correct 433 ms 81876 KB Output is correct
20 Correct 488 ms 81804 KB Output is correct
21 Correct 523 ms 81652 KB Output is correct
22 Correct 467 ms 81572 KB Output is correct
23 Correct 457 ms 86340 KB Output is correct
24 Correct 338 ms 83216 KB Output is correct
25 Correct 376 ms 81896 KB Output is correct
26 Correct 399 ms 81680 KB Output is correct
27 Correct 363 ms 81624 KB Output is correct
28 Correct 427 ms 86148 KB Output is correct
29 Correct 531 ms 86256 KB Output is correct
30 Correct 468 ms 86140 KB Output is correct
31 Correct 546 ms 86280 KB Output is correct
32 Correct 577 ms 81468 KB Output is correct
33 Correct 678 ms 82980 KB Output is correct
34 Correct 235 ms 40720 KB Output is correct
35 Correct 722 ms 86276 KB Output is correct
36 Correct 680 ms 82380 KB Output is correct
37 Correct 701 ms 85428 KB Output is correct
38 Correct 686 ms 83044 KB Output is correct
39 Correct 619 ms 91212 KB Output is correct
40 Correct 627 ms 91312 KB Output is correct
41 Correct 601 ms 84656 KB Output is correct
42 Correct 503 ms 82356 KB Output is correct
43 Correct 699 ms 89864 KB Output is correct
44 Correct 626 ms 85400 KB Output is correct
45 Correct 491 ms 91564 KB Output is correct
46 Correct 489 ms 91212 KB Output is correct
47 Correct 441 ms 86368 KB Output is correct
48 Correct 529 ms 86280 KB Output is correct
49 Correct 484 ms 86424 KB Output is correct
50 Correct 428 ms 86236 KB Output is correct
51 Correct 581 ms 91952 KB Output is correct
52 Correct 553 ms 92076 KB Output is correct