oj.uz

Submission #500184

# Submission time Handle Problem Language Result Execution time Memory
500184 2021-12-30T12:30:39 Z aymanrs Werewolf (IOI18_werewolf) C++14
0 / 100
 496 ms 90840 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);
    }
  }
  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;
}

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

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 460 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 460 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 456 ms 62260 KB Output is correct
2 Runtime error 496 ms 90840 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 460 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -