oj.uz

Submission #500195

# Submission time Handle Problem Language Result Execution time Memory
500195 2021-12-30T12:43:11 Z aymanrs Werewolf (IOI18_werewolf) C++14
34 / 100
 553 ms 70792 KB 
#include <bits/stdc++.h>
#include "werewolf.h"
using namespace std;
struct node {
    int id, t = -1;
    list<node*> l;
};
vector<node> g;
void dfs(node* n, int &t, int a[]){
  a[t] = n->id;
  n->t = t++;
  if(n->l.front()->t == -1) dfs(n->l.front(), t, a);
  else if (n->l.size() > 1) dfs(n->l.back(), t, a);
}
vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R){
  g.resize(N);
  for(int i = 0;i < N;i++) g[i].id=i;
  for(int i = 0;i < X.size();i++){
      g[X[i]].l.push_back(&g[Y[i]]);
      g[Y[i]].l.push_back(&g[X[i]]);
  }
  int a[N], t = 0;
  for(int i = 0;i < N;i++){
    if(g[i].l.size() == 1){
      dfs(&g[i], t, a);
      break;
    }
  }
  int x[N][20], m[N][20];
  for(int i = 0;i < N;i++) x[i][0] = m[i][0] = a[i];
  int d[N+1] = {0};
  for(int i = 2;i <= N;i++){
    d[i] = d[i-1];
    if((i&-i) == i) d[i]++;
  }
  for(int k = 1;k < 20;k++){
    for(int i = 0;i + (1<<k) <= N;i++){
      x[i][k] = max(x[i][k-1], x[i+(1<<(k-1))][k-1]);
      m[i][k] = min(m[i][k-1], m[i+(1<<(k-1))][k-1]);
    }
  }
  vector<int> ans(S.size(), 0);
  for(int i = 0;i < S.size();i++){
    if(g[S[i]].t < g[E[i]].t) {
      int l = g[S[i]].t, r = g[E[i]].t, mid, b = -1, k = 1e9;
      while(l <= r){
        mid = (l+r)/2;
        int f = mid-g[S[i]].t+1;
        if(min(m[g[S[i]].t][d[f]], m[mid - (1<<d[f]) + 1][d[f]]) < L[i]){
          r = mid-1;
        } else {
          b = mid;
          l = mid+1;
        }
      }
      l = g[S[i]].t; r = g[E[i]].t;
      while(l <= r){
        mid = (l+r)/2;
        int f = g[E[i]].t-mid+1;
        if(max(x[mid][d[f]], x[g[E[i]].t - (1<<d[f]) + 1][d[f]]) > R[i]){
          l = mid+1;
        } else {
          k = mid;
          r = mid-1;
        }
      }
      ans[i] = b >= k;
    } else {
      int l = g[E[i]].t, r = g[S[i]].t, mid, b = -1, k = 1e9;
      while(l <= r){
        mid = (l+r)/2;
        int f = mid-g[E[i]].t+1;
        if(max(x[g[E[i]].t][d[f]], x[mid - (1<<d[f]) + 1][d[f]]) > R[i]){
          r = mid-1;
        } else {
          b = mid;
          l = mid+1;
        }
      }
      l = g[E[i]].t; r = g[S[i]].t;
      while(l <= r){
        mid = (l+r)/2;
        int f = g[S[i]].t-mid+1;
        if(min(m[mid][d[f]], m[g[S[i]].t - (1<<d[f]) + 1][d[f]]) < L[i]){
          l = mid+1;
        } else {
          k = mid;
          r = mid-1;
        }
      }
      ans[i] = b >= k;
    }
  }
  return ans;
}
// int main(){
//   check_validity(5, {0, 1, 2, 3}, {1, 2, 3, 4}, {0, 1, 2}, {3, 2, 0}, {0, 1, 0}, {4, 2, 1});
// }

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:18:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |   for(int i = 0;i < X.size();i++){
      |                 ~~^~~~~~~~~~
werewolf.cpp:43:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |   for(int i = 0;i < S.size();i++){
      |                 ~~^~~~~~~~~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 467 ms 62156 KB Output is correct
2 Correct 472 ms 62156 KB Output is correct
3 Correct 473 ms 70516 KB Output is correct
4 Correct 481 ms 70596 KB Output is correct
5 Correct 514 ms 70576 KB Output is correct
6 Correct 495 ms 70572 KB Output is correct
7 Correct 553 ms 70580 KB Output is correct
8 Correct 493 ms 70584 KB Output is correct
9 Correct 347 ms 70524 KB Output is correct
10 Correct 338 ms 70528 KB Output is correct
11 Correct 344 ms 70580 KB Output is correct
12 Correct 363 ms 70792 KB Output is correct
13 Correct 510 ms 70536 KB Output is correct
14 Correct 532 ms 70708 KB Output is correct
15 Correct 516 ms 70576 KB Output is correct
16 Correct 487 ms 70580 KB Output is correct
17 Correct 541 ms 70648 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -