oj.uz

Submission #957286

# Submission time Handle Problem Language Result Execution time Memory
957286 2024-04-03T11:58:36 Z abczz Werewolf (IOI18_werewolf) C++14
100 / 100
 1078 ms 182320 KB 
#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

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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 45656 KB Output is correct
2 Correct 12 ms 45764 KB Output is correct
3 Correct 9 ms 45660 KB Output is correct
4 Correct 9 ms 45684 KB Output is correct
5 Correct 10 ms 45656 KB Output is correct
6 Correct 10 ms 45656 KB Output is correct
7 Correct 9 ms 45660 KB Output is correct
8 Correct 9 ms 45656 KB Output is correct
9 Correct 9 ms 45660 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 45656 KB Output is correct
2 Correct 12 ms 45764 KB Output is correct
3 Correct 9 ms 45660 KB Output is correct
4 Correct 9 ms 45684 KB Output is correct
5 Correct 10 ms 45656 KB Output is correct
6 Correct 10 ms 45656 KB Output is correct
7 Correct 9 ms 45660 KB Output is correct
8 Correct 9 ms 45656 KB Output is correct
9 Correct 9 ms 45660 KB Output is correct
10 Correct 15 ms 46608 KB Output is correct
11 Correct 14 ms 46428 KB Output is correct
12 Correct 15 ms 46428 KB Output is correct
13 Correct 15 ms 46936 KB Output is correct
14 Correct 14 ms 46684 KB Output is correct
15 Correct 14 ms 46684 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 629 ms 168156 KB Output is correct
2 Correct 852 ms 170324 KB Output is correct
3 Correct 720 ms 168648 KB Output is correct
4 Correct 595 ms 168892 KB Output is correct
5 Correct 607 ms 168532 KB Output is correct
6 Correct 585 ms 168056 KB Output is correct
7 Correct 525 ms 168376 KB Output is correct
8 Correct 735 ms 170680 KB Output is correct
9 Correct 459 ms 168836 KB Output is correct
10 Correct 500 ms 168276 KB Output is correct
11 Correct 470 ms 168120 KB Output is correct
12 Correct 430 ms 168160 KB Output is correct
13 Correct 906 ms 176028 KB Output is correct
14 Correct 848 ms 175192 KB Output is correct
15 Correct 873 ms 174992 KB Output is correct
16 Correct 844 ms 175312 KB Output is correct
17 Correct 525 ms 168408 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 45656 KB Output is correct
2 Correct 12 ms 45764 KB Output is correct
3 Correct 9 ms 45660 KB Output is correct
4 Correct 9 ms 45684 KB Output is correct
5 Correct 10 ms 45656 KB Output is correct
6 Correct 10 ms 45656 KB Output is correct
7 Correct 9 ms 45660 KB Output is correct
8 Correct 9 ms 45656 KB Output is correct
9 Correct 9 ms 45660 KB Output is correct
10 Correct 15 ms 46608 KB Output is correct
11 Correct 14 ms 46428 KB Output is correct
12 Correct 15 ms 46428 KB Output is correct
13 Correct 15 ms 46936 KB Output is correct
14 Correct 14 ms 46684 KB Output is correct
15 Correct 14 ms 46684 KB Output is correct
16 Correct 629 ms 168156 KB Output is correct
17 Correct 852 ms 170324 KB Output is correct
18 Correct 720 ms 168648 KB Output is correct
19 Correct 595 ms 168892 KB Output is correct
20 Correct 607 ms 168532 KB Output is correct
21 Correct 585 ms 168056 KB Output is correct
22 Correct 525 ms 168376 KB Output is correct
23 Correct 735 ms 170680 KB Output is correct
24 Correct 459 ms 168836 KB Output is correct
25 Correct 500 ms 168276 KB Output is correct
26 Correct 470 ms 168120 KB Output is correct
27 Correct 430 ms 168160 KB Output is correct
28 Correct 906 ms 176028 KB Output is correct
29 Correct 848 ms 175192 KB Output is correct
30 Correct 873 ms 174992 KB Output is correct
31 Correct 844 ms 175312 KB Output is correct
32 Correct 525 ms 168408 KB Output is correct
33 Correct 785 ms 168768 KB Output is correct
34 Correct 279 ms 78308 KB Output is correct
35 Correct 1018 ms 170836 KB Output is correct
36 Correct 721 ms 169020 KB Output is correct
37 Correct 965 ms 170256 KB Output is correct
38 Correct 846 ms 170024 KB Output is correct
39 Correct 718 ms 175032 KB Output is correct
40 Correct 741 ms 182320 KB Output is correct
41 Correct 712 ms 170452 KB Output is correct
42 Correct 482 ms 169400 KB Output is correct
43 Correct 1078 ms 178176 KB Output is correct
44 Correct 891 ms 169916 KB Output is correct
45 Correct 662 ms 175568 KB Output is correct
46 Correct 849 ms 175308 KB Output is correct
47 Correct 890 ms 175032 KB Output is correct
48 Correct 855 ms 174940 KB Output is correct
49 Correct 915 ms 175376 KB Output is correct
50 Correct 890 ms 174904 KB Output is correct
51 Correct 617 ms 181624 KB Output is correct
52 Correct 653 ms 180332 KB Output is correct