Submission #600747

#	Time	Username	Problem	Language	Result	Execution time	Memory
600747		jack715	Werewolf (IOI18_werewolf)	C++14	34 / 100	1379 ms	524288 KiB

werewolf

#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 (stderr)

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
• Subtask 2: 0 / 8
• Subtask 3: 34 / 34
• Subtask 4: 0 / 51