Submission #1039412

#	Time	Username	Problem	Language	Result	Execution time	Memory
1039412		vnm06	Werewolf (IOI18_werewolf)	C++14	100 / 100	580 ms	164552 KiB

werewolf

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

using namespace std;

int n, m, q;
int fenw[400005];
void update(int pos)
{
  pos++;
    //cout<<"upd "<<pos<<endl;
  while(pos<=n+2)
  {
    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++;
  //cout<<le<<" "<<ri<<" "<<query(ri)-query(le-1)<<endl;
  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));
  memset(nom_comp, -1, sizeof(nom_comp));
  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[old_comp][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[old_comp][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);

      }
    }
    //for(int i=0; i<n; i++) cout<<nom_comp[i]<<" ";
    //cout<<endl;
  }
  build_tree_1();
  for(int i=0; i<=brcomp+2; i++) {compn[i].resize(0); nom_comp[i]=-1; 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[old_comp][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[old_comp][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_1[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]]<<endl;
    ////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]]]);
    ////cout<<"op "<<ans[0]<<" "<<be[S[id_las[i][0]]]<<" "<<en[S[id_las[i][0]]]<<endl;
      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;
}
/**
15 14 1
10 8
8 13
13 3
3 12
12 4
4 2
2 6
6 7
7 5
5 0
0 1
1 14
14 9
9 11
3 4 0 5


(10 8 13) 3 (12 4) 2 (6 7 5) 0 1 (14 9 11)
*/

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:152:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  152 |         for(int k=0; k<compn[old_comp].size(); k++)
      |                      ~^~~~~~~~~~~~~~~~~~~~~~~
werewolf.cpp:164:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  164 |         for(int k=0; k<compn[old_comp].size(); k++)
      |                      ~^~~~~~~~~~~~~~~~~~~~~~~
werewolf.cpp:197:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  197 |         for(int k=0; k<compn[old_comp].size(); k++)
      |                      ~^~~~~~~~~~~~~~~~~~~~~~~
werewolf.cpp:209:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  209 |         for(int k=0; k<compn[old_comp].size(); k++)
      |                      ~^~~~~~~~~~~~~~~~~~~~~~~
werewolf.cpp:250:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  250 |   for(int i=0; i<Eut.size(); i++)
      |                ~^~~~~~~~~~~
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_beg[i].size(); j++)
      |                  ~^~~~~~~~~~~~~~~~~
werewolf.cpp:261:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  261 |     for(int j=0; j<id_las[i].size(); j++)
      |                  ~^~~~~~~~~~~~~~~~~

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