Submission #341463

#	Time	Username	Problem	Language	Result	Execution time	Memory
341463		a_player	Werewolf (IOI18_werewolf)	C++14	0 / 100	567 ms	26336 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
#ifdef ALE
#include "grader.cpp"
#endif
#define f first
#define s second
#define debug cout<<"ok"<<endl

using namespace std;

const int nax=2e5+5;

vector<int> grafo[nax];
vector<int> l;
bitset<nax> v;
int f[nax];
int ind[nax];
int pos[nax];
pair<int,int> ans[nax];
int Ni;
void update(int k){
  k++;
  while(k<=Ni){
    f[k]++;
    k+=k&(-k);
  }
}
int query(int k){
  if(k<0)return 0;
  k++;
  int sol=0;
  while(k>0){
    sol+=f[k];
    k-=k&(-k);
  }
  return sol;

}

int leftmost(int u, int v){
  int sol=u-1;
  int q=query(u-1);
  for(int b=v-u;b>=1;b/=2)
  while(sol+b<=v&&query(sol+b)==q)sol+=b;
  return sol+1;
}
int rightmost(int u, int v){
  int sol=v+1;
  int q=query(v);
  for(int b=v-u;b>=1;b/=2)
  while(sol-b>=u&&query(sol-b-1)==q)sol-=b;
  return sol-1;
}



vector<int> check_validity(int N, vector<int> X, vector<int> Y,
                                vector<int> S, vector<int> E,
                                vector<int> L, vector<int> R) {

 Ni=N;
  int Q = S.size();
  int M=X.size();
  vector<int> A(Q);
  int ini=-1;
  for(int i=0;i<M;i++){
    grafo[X[i]].push_back(Y[i]);
    grafo[Y[i]].push_back(X[i]);
  }
  for(int i=0;i<N;i++)
    if(grafo[i].size()==1){
      ini=i;
      break;
  }
  while(ini!=-1){
    v[ini]=1;
    ind[ini]=l.size();
    l.push_back(ini);
    if(!v[grafo[ini][0]])ini=grafo[ini][0];
    else if(grafo[ini].size()>1)ini=grafo[ini][1];
    else ini=-1;
  }
  //-------------
  auto cmpl=[&](int x,int y){
    return L[x]<L[y];
  };
  auto cmpr=[&](int x, int y){
    return R[x]>R[y];
  };
  iota(pos,pos+Q,0);
  sort(pos,pos+Q,cmpl);
  int j=0;
  for(int i=0;i<Q;i++){
    int x=pos[i];
    while(j<N&&j<L[x])update(ind[j++]);
    if(ind[S[x]]<ind[E[x]]){
      ans[i].f=leftmost(ind[S[x]],ind[E[x]]);
    }else ans[i].f=rightmost(ind[E[x]],ind[S[x]]);

  }
  iota(pos,pos+Q,0);
  sort(pos,pos+Q,cmpr);
  for(int i=0;i<=N;i++)f[i]=0;
 j=N-1;
  for(int i=0;i<Q;i++){
    int x=pos[i];
    while(j>=0&&j>R[x])update(ind[j--]);
    if(ind[S[x]]<ind[E[x]]){
      ans[i].s=rightmost(ind[S[x]],ind[E[x]]);
    }else ans[i].s=leftmost(ind[E[x]],ind[S[x]]);

  }
//----------------------------
  for(int q=0;q<Q;q++){
    int s=ind[S[q]],e=ind[E[q]];
    if(s<e){
      if(ans[q].f<ans[q].s)A[q]=0;
      else if(ans[q].s+1==ans[q].f)A[q]=0;
      else A[q]=1;
    }else{
      if(ans[q].f>ans[q].s)A[q]=0;
      else if(ans[q].f+1==ans[q].s)A[q]=0;
      else A[q]=1;
    }
  }
return A;

}

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