Submission #1245715

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245715		simplemind_31	Werewolf (IOI18_werewolf)	C++20	0 / 100	312 ms	589824 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
vector<vi> graph,sparsemaxi,sparsemini;
int n,m,q,timer;
vi pos,nums,res;
void dfs(int now,int ante){
  pos[now]=timer++;
  for(auto u:graph[now]){
    if(u!=ante){
      dfs(u,now);
    }
  }
}
vi check_validity(int N,vi X,vi Y,vi S,vi E,vi L,vi R) {
  n=N;
  m=X.size();
  q=S.size();
  graph.resize(n);
  pos.resize(n);
  nums.resize(n);
  res.resize(q);
  sparsemini.assign(n,vi(21,-1));
  for(int i=0;i<m;i++){
    graph[X[i]].push_back(Y[i]);
    graph[Y[i]].push_back(X[i]);
  }
  for(int i=0;i<n;i++){
    if(graph[i].size()==1){
      dfs(i,-1);
    }
  }
  for(int i=0;i<n;i++){
    nums[pos[i]]=i;
  }
  for(int i=0;i<n;i++){
    sparsemini[i][0]=nums[i];
  }
  sparsemaxi=sparsemini;
  for(int j=1;j<=20;j++){
    for(int i=0;i<n;i++){
      if(i+(1<<(j-1))<n){
        sparsemaxi[i][j]=max(sparsemaxi[i][j-1],sparsemaxi[i+(1<<(j-1))][j-1]);
        sparsemini[i][j]=min(sparsemini[i][j-1],sparsemini[i+(1<<(j-1))][j-1]);
      }
    }
  }
  for(int i=0;i<q;i++){
    if(S[i]<L[i] || E[i]>R[i]){
      res[i]=0;
    }
    int poshuma=pos[S[i]],poslobo=pos[E[i]];
    if(poshuma<poslobo){
      // humano ... lobo;
      // humano no menos que L[i];
      int posicion=poshuma;
      for(int j=20;j>0;j--){
        if(posicion+(1<<j)-1>=n){
          continue;
        }
        if(sparsemini[posicion][j]==-1){
          continue;
        }
        if(sparsemini[posicion][j]>=L[i]){
          posicion=posicion+(1<<(j))-1;
          j++;
        }
      }
      int termina=poslobo;
      for(int j=20;j>0;j--){
        if(posicion-(1<<j)+1<0){
          continue;
        }
        if(sparsemaxi[posicion-(1<<j)+1][j]==-1){
          continue;
        }
        if(sparsemaxi[posicion-(1<<j)+1][j]<=R[i]){
          posicion=posicion-(1<<(j))+1;
          j++;
        }
      }
      if(posicion>poshuma && termina<poslobo && termina<=posicion){
        res[i]=1;
      }else{
        res[i]=0;
      }
    }else{
      // lobo ... humano
      int posicion=poslobo;
      for(int j=20;j>0;j--){
        if(posicion+(1<<j)-1>=n){
          continue;
        }
        if(sparsemaxi[posicion][j]==-1){
          continue;
        }
        if(sparsemaxi[posicion][j]<=R[i]){
          posicion=posicion+(1<<(j))-1;
          j++;
        }
      }
      int termina=poshuma;
      for(int j=20;j>0;j--){
        if(posicion-(1<<j)+1<0){
          continue;
        }
        if(sparsemini[posicion-(1<<j)+1][j]==-1){
          continue;
        }
        if(sparsemini[posicion-(1<<j)+1][j]>=L[i]){
          posicion=posicion-(1<<(j))+1;
          j++;
        }
      }
      if(posicion>poslobo && termina<poshuma && termina<=posicion){
        res[i]=1;
      }else{
        res[i]=0;
      }
    }
  }
  return res;
}

• Subtask 1: 0 / 7
• Subtask 2: 0 / 8
• Subtask 3: 0 / 34
• Subtask 4: 0 / 51