oj.uz

Submission #600747

# Submission time Handle Problem Language Result Execution time Memory
600747 2022-07-21T07:35:03 Z jack715 Werewolf (IOI18_werewolf) C++14
34 / 100
 1379 ms 524288 KB 
#include "werewolf.h"
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define pp pop_back
#define mp make_pair
#define bb back
#define ff first
#define ss second

using namespace std;

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();
  vector<int> A(Q, 0);
  vector<int> path[n];
  for (int i = 0; i < x.size(); i++) {
    path[x[i]].pb(y[i]);
    path[y[i]].pb(x[i]);
  }

  int level[n];
  int jump[n][20][3];
  memset(jump, -1, sizeof(jump));
  queue<pair<int, int> > bfs;
  bfs.push({0, 0});
  while (!bfs.empty()) {
    int now = bfs.front().ff;
    level[now] = bfs.front().ss;
    bfs.pop();

    for (int next : path[now]) {
      if (next == jump[now][0][1]) continue;
      jump[next][0][0] = min(now, next);
      jump[next][0][1] = now;
      jump[next][0][2] = max(now, next);
      bfs.push({next, level[now]+1});
    }
  }

  for (int j = 1; j < 20; j++) {
    for (int i = 0; i < n; i++) {
      if (jump[i][j-1][1] == -1) continue;
      jump[i][j][1] = jump[jump[i][j-1][1]][j-1][1];
      jump[i][j][0] = min(jump[i][j-1][0], jump[jump[i][j-1][1]][j-1][0]);
      jump[i][j][2] = max(jump[i][j-1][2], jump[jump[i][j-1][1]][j-1][2]);
    }
  }

  for (int q = 0; q < Q; q++) {
    if (s[q] < l[q] || e[q] > r[q]) continue;
    int a = s[q], b = e[q], c;
    if (level[a] > level[b])
      swap(a, b);
    for (int i = 19; i >= 0; i--) {
      if (level[b] - (1<<i) >= level[a])
        b = jump[b][i][1];
    }

    for (int i = 19; i >= 0; i--) {
      if (jump[b][i][1] != jump[a][i][1])
        b = jump[b][i][1], a = jump[a][i][1];
    }

    int mx = -1, mn = n+1, ta, tb;
    if (a != b)
      a = jump[a][0][1], b = jump[b][0][1];
    c = a;
    a = s[q], b = e[q];
    // cout << c << '\n';
    
    for (int i = 19; i >= 0; i--) {
      if (jump[a][i][0] < l[q] || level[a]-(1<<i) < level[c]) continue;
      a = jump[a][i][1];
    }

    // cout << "WUT\n";
    // cout << a << ' ';
    if (a >= l[q] && a <= r[q]) {
      for (int i = 19; i >= 0; i--) {
        if (level[a] - (1<<i) < level[c]) continue;
        mx = max(mx, jump[a][i][2]);
        a = jump[a][i][1];
      }

      for (int i = 19; i >= 0; i--) {
        if (level[b] - (1<<i) < level[c]) continue;
        mx = max(mx, jump[b][i][2]);
        b = jump[b][i][1];
      }

      if (mx <= r[q]) A[q] = 1;
    }

    a = s[q], b = e[q];
    for (int i = 19; i >= 0; i--) {
      if (jump[b][i][2] > r[q] || level[b]-(1<<i) < level[c]) continue;
      b = jump[b][i][1];
    }

    // cout << b << '\n';
    
    if (b >= l[q] && b <= r[q]) {
      for (int i = 19; i >= 0; i--) {
        if (level[b] - (1<<i) < level[c]) continue;
        mn = min(mn, jump[b][i][0]);
        b = jump[b][i][1];
      }
      for (int i = 19; i >= 0; i--) {
        if (level[a] - (1<<i) < level[c]) continue;
        mn = min(mn, jump[a][i][0]);
        a = jump[a][i][1];
      }
      if (mn >= l[q]) A[q] = 1;
    }
  }
  return A;
}

/*
6 6 3
5 1 
1 2
1 3
3 4
3 0 
5 2
4 2 1 2
4 2 2 2 
5 4 3 4
*/

Compilation message

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:19:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |   for (int i = 0; i < x.size(); i++) {
      |                   ~~^~~~~~~~~~
werewolf.cpp:67:28: warning: unused variable 'ta' [-Wunused-variable]
   67 |     int mx = -1, mn = n+1, ta, tb;
      |                            ^~
werewolf.cpp:67:32: warning: unused variable 'tb' [-Wunused-variable]
   67 |     int mx = -1, mn = n+1, ta, tb;
      |                                ^~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 1379 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 1379 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 899 ms 70868 KB Output is correct
2 Correct 700 ms 70740 KB Output is correct
3 Correct 763 ms 70812 KB Output is correct
4 Correct 811 ms 70804 KB Output is correct
5 Correct 844 ms 71052 KB Output is correct
6 Correct 838 ms 71052 KB Output is correct
7 Correct 1022 ms 71276 KB Output is correct
8 Correct 585 ms 71076 KB Output is correct
9 Correct 450 ms 71076 KB Output is correct
10 Correct 490 ms 71044 KB Output is correct
11 Correct 497 ms 70940 KB Output is correct
12 Correct 526 ms 70748 KB Output is correct
13 Correct 786 ms 70696 KB Output is correct
14 Correct 787 ms 70360 KB Output is correct
15 Correct 822 ms 70232 KB Output is correct
16 Correct 827 ms 70104 KB Output is correct
17 Correct 963 ms 70112 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Runtime error 1379 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -