Submission #340955

#	Time	Username	Problem	Language	Result	Execution time	Memory
340955		a_player	Werewolf (IOI18_werewolf)	C++14	0 / 100	249 ms	43588 KiB

werewolf

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

using namespace std;

const int nax=2e5+5;

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

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);
    ini=-1;
    if(!v[grafo[ini][0]])ini=grafo[ini][0];
    else if(grafo[ini].size()>1)ini=grafo[ini][1];
  }//-------------
  for(int i=0;i<Q;i++)o.emplace_back(L[i],i);
  sort(o.begin(),o.end());
  int j=0;
  for(auto p:o){
    while(j<N&&j<p.f){
      update(ind[j]);
      j++;
    }
    int l=ind[S[p.s]],r=ind[E[p.s]];
    if(l<r){
    int x=l-1;
    for(int b=r-l;b>=1;b/=2)
    while(x+b<=r&&query(x+b)-query(l-1)==0)x+=b;
    ans[p.s].f=x+1;
  }
  else{
    int x=l+1;
    for(int b=l-r;b>=1;b/=2)
    while(x-b>=r&&query(l)-query(x-b-1)==0)x-=b;
    ans[p.s].f=x-1;
  }
  }
  o.clear();
  for(int i=0;i<=N;i++)fi[i]=0;
  for(int i=0;i<Q;i++)o.emplace_back(R[i],i);
  sort(o.begin(),o.end(),greater<pair<int,int> >());
  j=0;
  for(auto p:o){
    while(j<N&&j>p.f){
      update(ind[j]);
      j++;
    }
    int l=ind[S[p.s]],r=ind[E[p.s]];
    if(l>r){
    int x=r-1;
    for(int b=r-l;b>=1;b/=2)
    while(x+b<=l&&query(x+b)-query(r-1)==0)x+=b;
    ans[p.s].s=x+1;
  }
  else{
    int x=r+1;
    for(int b=r-l;b>=1;b/=2)
    while(x-b>=l&&query(r)-query(x-b-1)==0)x-=b;
    ans[p.s].s=x-1;
  }
  }

  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].s-1==ans[q].f)A[q]=0;
      else A[q]=1;
    }

  }
return A;

}

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:61:23: warning: array subscript -3 is outside array bounds of 'std::vector<int> [200005]' [-Warray-bounds]
   61 |     if(!v[grafo[ini][0]])ini=grafo[ini][0];
      |                       ^
werewolf.cpp:13:13: note: while referencing 'grafo'
   13 | vector<int> grafo[nax];
      |             ^~~~~
werewolf.cpp:62:28: warning: array subscript -2 is outside array bounds of 'std::vector<int> [200005]' [-Warray-bounds]
   62 |     else if(grafo[ini].size()>1)ini=grafo[ini][1];
      |             ~~~~~~~~~~~~~~~^~
werewolf.cpp:13:13: note: while referencing 'grafo'
   13 | vector<int> grafo[nax];
      |             ^~~~~

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