Submission #1039264

#	Time	Username	Problem	Language	Result	Execution time	Memory
1039264		vnm06	Werewolf (IOI18_werewolf)	C++14	0 / 100	324 ms	136136 KiB

werewolf

#include<bits/stdc++.h>
#include "werewolf.h"

using namespace std;

int n, m, q;
int fenw[400005];
void update(int pos)
{
  pos++;
  while(pos<=n)
  {
    fenw[pos]++;
    pos+=(pos&(-pos));
  }
}

int query(int pos)
{
  int res=0;
  while(pos)
  {
    res+=fenw[pos];
    pos-=(pos&(-pos));
  }
  return res;
}

int query(int le, int ri)
{
  le++;
  ri++;
  return query(ri)-query(le-1);
}

int brcomp=0;
vector<int> compn[400005], gr[400005];
int nom_comp[400005], par[400005], par_comp[400005];

int new_nom[400005], tek_nom=1;
int be_id[400005], en_id[400005];



vector<int> spis_1[400005], spis_2[400005];
int tree_1[20][400005], tree_2[20][400005];

void build_tree_1()
{
  for(int j=n-1; j>=0; j--) tree_1[0][j]=par[j];
  for(int j=n-1; j>=0; j--) 
  {
    if(par[j]!=-1) spis_1[par[j]].push_back(j);
  }
  for(int lvl=1; lvl<20; lvl++)
  {
    for(int v=0; v<n; v++)
    {
      if(tree_1[lvl-1][v]==-1) tree_1[lvl][v]=-1;
      else tree_1[lvl][v]=tree_1[lvl-1][tree_1[lvl-1][v]];
    }
  }
}

void build_tree_2()
{
  for(int j=n-1; j>=0; j--) tree_2[0][j]=par[j];
  for(int j=n-1; j>=0; j--) 
  {
    if(par[j]!=-1) spis_2[par[j]].push_back(j);
  }
  for(int lvl=1; lvl<20; lvl++)
  {
    for(int v=0; v<n; v++)
    {
      if(tree_2[lvl-1][v]==-1) tree_2[lvl][v]=-1;
      else tree_2[lvl][v]=tree_2[lvl-1][tree_2[lvl-1][v]];
    }
  }
}

int be[400005], en[400005];

void renumerate(int v)
{
  new_nom[v]=tek_nom;
  be[v]=tek_nom;
  tek_nom++;
  int brs=spis_1[v].size();
  for(int i=0; i<brs; i++)
  {
    renumerate(spis_1[v][i]);
  }
  en[v]=tek_nom-1;
}

int brv=0;
vector<int> Eut;
int fir[400005], las[400005];

void euler_tour(int v)
{
  Eut.push_back(v);
  fir[v]=brv;
  las[v]=brv;
  brv++;
  int brs=spis_2[v].size();
  for(int i=0; i<brs; i++)
  {
    euler_tour(spis_2[v][i]);
    Eut.push_back(v);
    las[v]=brv;
    brv++;
  }
}

int ans[400005];
vector<int> id_beg[400005], id_las[400005];

std::vector<int> check_validity(int N, std::vector<int> X, std::vector<int> Y,
                                std::vector<int> S, std::vector<int> E,
                                std::vector<int> L, std::vector<int> R) 
{
  q=S.size();
  n=N;
  m=X.size();
  for(int i=0; i<m; i++)
  {
    gr[X[i]].push_back(Y[i]);
    gr[Y[i]].push_back(X[i]);
  }

  memset(par, -1, sizeof(par));
  for(int j=n-1; j>=0; j--)
  {
    compn[brcomp].push_back(j);
    nom_comp[j]=brcomp;
    par_comp[brcomp]=j;
    brcomp++;
    int brs=gr[j].size();
    for(int i=0; i<brs; i++)
    {
      int nv=gr[j][i];
      if(nv<j || nom_comp[j]==nom_comp[nv]) continue;
      par[par_comp[nom_comp[nv]]]=j;
      if(compn[nom_comp[j]].size()>compn[nom_comp[nv]].size())
      {
        int old_comp=nom_comp[nv];
        for(int k=0; k<compn[old_comp].size(); k++)
        {
          int tv=compn[nom_comp[nv]][k];
          nom_comp[tv]=nom_comp[j];
          compn[nom_comp[j]].push_back(tv);
        }
        par_comp[nom_comp[j]]=j;
        compn[old_comp].resize(0);
      }
      else
      {
        int old_comp=nom_comp[j];
        for(int k=0; k<compn[old_comp].size(); k++)
        {
          int tv=compn[nom_comp[j]][k];
          nom_comp[tv]=nom_comp[nv];
          compn[nom_comp[nv]].push_back(tv);
        }
        par_comp[nom_comp[j]]=j;
        compn[old_comp].resize(0);

      }
    }
  }
  build_tree_1();
  for(int i=0; i<=brcomp+2; i++) {compn[i].resize(0); nom_comp[i]=0; par[i]=par_comp[i]=-1;}
  brcomp=0;

  for(int j=0; j<n; j++)
  {
    compn[brcomp].push_back(j);
    nom_comp[j]=brcomp;
    par_comp[brcomp]=j;
    brcomp++;
    int brs=gr[j].size();
    for(int i=0; i<brs; i++)
    {
      int nv=gr[j][i];
      if(nv>j || nom_comp[j]==nom_comp[nv]) continue;
      par[par_comp[nom_comp[nv]]]=j;
      if(compn[nom_comp[j]].size()>compn[nom_comp[nv]].size())
      {
        int old_comp=nom_comp[nv];
        for(int k=0; k<compn[old_comp].size(); k++)
        {
          int tv=compn[nom_comp[nv]][k];
          nom_comp[tv]=nom_comp[j];
          compn[nom_comp[j]].push_back(tv);
        }
        par_comp[nom_comp[j]]=j;
        compn[old_comp].resize(0);
      }
      else
      {
        int old_comp=nom_comp[j];
        for(int k=0; k<compn[old_comp].size(); k++)
        {
          int tv=compn[nom_comp[j]][k];
          nom_comp[tv]=nom_comp[nv];
          compn[nom_comp[nv]].push_back(tv);
        }
        par_comp[nom_comp[j]]=j;
        compn[old_comp].resize(0);

      }
    }
  }
  build_tree_2();

  renumerate(0);
  euler_tour(n-1);

  for(int i=0; i<q; i++)
  {
    for(int lvl=19; lvl>=0; lvl--)
    {
      if(tree_1[lvl][S[i]]==-1) continue;
      else if(tree_1[lvl][S[i]]>=L[i]) S[i]=tree_1[lvl][S[i]];
    }
    for(int lvl=19; lvl>=0; lvl--)
    {
      if(tree_2[lvl][E[i]]==-1) continue;
      else if(tree_2[lvl][E[i]]<=R[i]) E[i]=tree_2[lvl][E[i]];
    }
    //cout<<S[i]<<' '<<E[i]<<endl;
    if(fir[E[i]]) id_beg[fir[E[i]]-1].push_back(i);
    id_las[las[E[i]]].push_back(i);
    //cout<<fir[E[i]]<<" "<<las[E[i]]<<endl;
  }
  ///for(int i=0; i<n; i++) //cout<<fir[i]<<" "<<las[i]<<" ";
  //cout<<endl;
  ///for(int i=0; i<n; i++) //cout<<new_nom[i]<<" ";
  //cout<<endl;
  ///for(int i=0; i<n; i++) //cout<<tree_2[0][i]<<" ";
  //cout<<endl;
  int totbr1=0, totbr2=0;
  for(int i=0; i<Eut.size(); i++)
  {
    update(new_nom[Eut[i]]);
    //cout<<new_nom[Eut[i]]<<" ";
    for(int j=0; j<id_beg[i].size(); j++)
    {
      ans[id_beg[i][j]]-=query(be[S[id_beg[i][j]]], en[S[id_beg[i][j]]]);
      totbr1++;
      //cout<<id_beg[i][j]<<" "<<be[S[id_beg[i][j]]]<<" "<<en[S[id_beg[i][j]]]<<endl;
    }
    for(int j=0; j<id_las[i].size(); j++)
    {
      ans[id_las[i][j]]+=query(be[S[id_las[i][j]]], en[S[id_las[i][j]]]);
      totbr2++;
      //cout<<id_las[i][j]<<" "<<be[S[id_las[i][j]]]<<" "<<en[S[id_las[i][j]]]<<endl;
    }
  }
  vector<int> A;
  A.resize(q);
  for(int i=0; i<q; i++) A[i]=bool(ans[i]);
  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:149:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  149 |         for(int k=0; k<compn[old_comp].size(); k++)
      |                      ~^~~~~~~~~~~~~~~~~~~~~~~
werewolf.cpp:161:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  161 |         for(int k=0; k<compn[old_comp].size(); k++)
      |                      ~^~~~~~~~~~~~~~~~~~~~~~~
werewolf.cpp:192:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  192 |         for(int k=0; k<compn[old_comp].size(); k++)
      |                      ~^~~~~~~~~~~~~~~~~~~~~~~
werewolf.cpp:204:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  204 |         for(int k=0; k<compn[old_comp].size(); k++)
      |                      ~^~~~~~~~~~~~~~~~~~~~~~~
werewolf.cpp:245:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  245 |   for(int i=0; i<Eut.size(); i++)
      |                ~^~~~~~~~~~~
werewolf.cpp:249:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  249 |     for(int j=0; j<id_beg[i].size(); j++)
      |                  ~^~~~~~~~~~~~~~~~~
werewolf.cpp:255:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  255 |     for(int j=0; j<id_las[i].size(); j++)
      |                  ~^~~~~~~~~~~~~~~~~

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