Submission #1245711

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245711		porquenomedejainiciarsesion	Werewolf (IOI18_werewolf)	C++20	0 / 100	1059 ms	589824 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> V,V1;
vector<vector<int>> adj;
vector<vector<int>> T,T2;
int n;
int maxi;
void dfs(int cur,int prev){
  V.push_back(cur);
  for(auto x:adj[cur]){
    if(x!=prev){
      dfs(x,cur);
    }
  }
}
void build(int i,int l,int r){
  if(l==r){
    T[i]={V[l]};
    return;
  }
  int m=(l+r)/2;
  build(2*i+1,l,m);
  build(2*i+2,m+1,r);
  merge(T[2*i+1].begin(),T[2*i+1].end(),T[2*i+2].begin(),T[2*i+2].end(),back_inserter(T[i]));
}
int query(int i,int tl,int tr,int l,int r,int x){
  if(tl>=l && tr<=r){
    auto ans=lower_bound(T[i].begin(),T[i].end(),x);
    if(*ans<=x){
      maxi=max(x,maxi);
    }
    int ans2=upper_bound(T[i].begin(),T[i].end(),x)-T[i].begin();
    return ans2;
  }
  if(tl>r || tr<l){
    return 0;
  }
  int m=(tl+tr)/2;
  return query(2*i+1,tl,m,l,r,x)+query(2*i+2,m+1,tr,l,r,x);
}
int qu(int l,int r,int x){
  return query(0,0,n-1,l,r,x);
}
vector<int> check_validity(int N,vector<int> X, std::vector<int> Y,std::vector<int> S, std::vector<int> E,std::vector<int> L, std::vector<int> R) {
  int q=S.size();
  unordered_map<int,int> M,M1,M2;
  adj.resize(N);
  n=N;
  for(int i=0;i<X.size();i++){
    M[X[i]]++;
    M[Y[i]]++;
    adj[X[i]].push_back(Y[i]);
    adj[Y[i]].push_back(X[i]);
  }
  int start=1000000000;
  for(auto x:M){
    if(x.second==1){
      start=min(start,x.first);
    }
  }
  dfs(start,-1);
  T.resize(4*N);
  vector<int> ans;
  build(0,0,n-1);
   for(int i=0;i<V.size();i++){
    M1[V[i]]=i;
    M2[i]=V[i];
  }
  for(int i=0;i<S.size();i++){
    int a=M1[S[i]];
    int b=M1[E[i]];
    if(a<b){
      maxi=0;
      int c=qu(a,b,L[i]-1);
      if(c>0){
        int jeje=M1[maxi];
        if(qu(jeje,b,R[i])==b-jeje+1){
          ans.push_back(1);
        }else{
          ans.push_back(0);
        }
      }else{
        if(M2[b]>=L[i] && M2[b]<=R[i]){
          ans.push_back(1);
        }else{
          ans.push_back(0);
        }
      }
    }else{
      swap(a,b);
      maxi=0;
      int c=qu(a,b,L[i]-1);
      if(c>0){
        int jeje=M1[maxi];
        if(qu(a,jeje,R[i])==jeje-a+1){
          ans.push_back(1);
        }else{
          ans.push_back(0);
        }
      }else{
        if(M2[a]>=L[i] && M2[a]<=R[i]){
          ans.push_back(1);
        }else{
          ans.push_back(0);
        }
      }
    }
  }
  return ans;
}

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