Submission #1245685

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

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> V;
vector<vector<int>> adj;
vector<vector<int>> T;
int n;
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){
    int ans=upper_bound(T[i].begin(),T[i].end(),x)-T[i].begin();
    return ans;
  }
  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;
  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;
  for(auto x:M){
    if(x.second==1){
      start=x.first;
      break;
    }
  }
  dfs(0,-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;
  }
  for(int i=0;i<S.size();i++){
    int a=M1[S[i]];
    int b=M1[E[i]];
    if(a>b){
      swap(a,b);
    }
    int c=qu(a,b,L[i]-1);
    int d=qu(a,b,R[i]);
    if(c>1){
      ans.push_back(0);
      continue;
    }else if(c<1){
      if(d>0){
        ans.push_back(1);
      }else{
        ans.push_back(0);
      }
    }else{
      ans.push_back(1);
      continue;
    }
  }
  return ans;
}

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