Submission #500195

#	Time	Username	Problem	Language	Result	Execution time	Memory
500195		aymanrs	Werewolf (IOI18_werewolf)	C++14	34 / 100	553 ms	70792 KiB

werewolf

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