Submission #80183

#	Time	Username	Problem	Language	Result	Execution time	Memory
80183		Bodo171	Werewolf (IOI18_werewolf)	C++14	100 / 100	1283 ms	405488 KiB

werewolf

#include "werewolf.h"
#include <iostream>
using namespace std;
const int nmax=200005;
int i,j,n,nr,m;
int tt[nmax],rg[nmax],T[nmax];
int finds(int x)
{
    while(x!=tt[x])
        x=tt[x];
    return x;
}
void unite(int A,int B)
{
    if(rg[A]<rg[B]) swap(A,B);
    tt[B]=A;rg[A]+=rg[B];
}
vector<int> v[nmax];
struct arbore
{
    int t[20][nmax],l[nmax],r[nmax],rep[nmax];
    vector<int> ad[nmax];
    void dfs(int x)
    {
     ++nr;l[x]=nr;rep[nr]=x;
     for(int i=0;i<ad[x].size();i++)
        dfs(ad[x][i]);
     r[x]=nr;
    }
    void solve()
    {
        for(i=1;i<=18;i++)
            for(j=0;j<n;j++)
             {
                 if(t[i-1][j]!=-1)t[i][j]=t[i-1][t[i-1][j]];
                 else t[i][j]=-1;
             }
        int rad=0;
        for(i=0;i<n;i++)
            if(t[0][i]!=-1) ad[t[0][i]].push_back(i);
            else rad=i;
        nr=0;
        dfs(rad);
    }
    int cb(int x,int lim,int par)
    {
        for(int p=18;p>=0;p--)
            if(t[p][x]!=-1&&((t[p][x]>=lim&&par==0)||(t[p][x]<=lim&&par==1)))
              x=t[p][x];
        return x;
    }
}mic,mare;
int aib[nmax],pica[nmax];
inline int lbit(int x)
{
    return ((x^(x-1))&x);
}
void update(int poz,int val)
{
    for(int idx=poz;idx<=n;idx+=lbit(idx))
        aib[idx]+=val;
}
int compute(int poz)
{
    int ret=0;
    for(int idx=poz;idx>0;idx-=lbit(idx))
        ret+=aib[idx];
    return ret;
}
struct ev
{
    int ll,rr,wh,sgn;
};
vector<ev> qr[nmax];
int cat[nmax];
void sweep()
{
    for(i=1;i<=n;i++)
    {
        pica[mic.rep[i]]=i;
    }
    for(i=1;i<=n;i++)
    {
        update(pica[mare.rep[i]],1);
        for(j=0;j<qr[i].size();j++)
            cat[qr[i][j].wh]+=(compute(qr[i][j].rr)-compute(qr[i][j].ll-1))*qr[i][j].sgn;
    }
}
vector<int> check_validity(int N, vector<int> X, vector<int> Y,
                                vector<int> S, vector<int> E,
                                vector<int> L, vector<int> R) {
  int Q = S.size();
  m=X.size();n=N;
  std::vector<int> A(Q);
  for(int i=0;i<m;i++)
  {
        v[X[i]].push_back(Y[i]);
        v[Y[i]].push_back(X[i]);
  }
  for(i=0;i<n;i++)
    mic.t[0][i]=mare.t[0][i]=-1;
  for(i=0;i<n;i++)
  {
      tt[i]=i;rg[i]=1;T[i]=i;
      for(j=0;j<v[i].size();j++)
        if(v[i][j]<i&&finds(v[i][j])!=finds(i))
      {
          mic.t[0][T[finds(v[i][j])]]=i;
          unite(finds(i),finds(v[i][j]));
      }
      T[finds(i)]=i;
  }
  mic.solve();
  for(i=n-1;i>=0;i--)
  {
      tt[i]=i;rg[i]=1;T[i]=i;
      for(j=0;j<v[i].size();j++)
        if(v[i][j]>i&&finds(v[i][j])!=finds(i))
      {
          mare.t[0][T[finds(v[i][j])]]=i;
          unite(finds(i),finds(v[i][j]));
      }
      T[finds(i)]=i;
  }
  mare.solve();
  int q=L.size(),ss,ee;
  for(i=0;i<q;i++)
  {
      ss=mare.cb(S[i],L[i],0);ee=mic.cb(E[i],R[i],1);
      qr[mare.l[ss]-1].push_back({mic.l[ee],mic.r[ee],i,-1});
      qr[mare.r[ss]].push_back({mic.l[ee],mic.r[ee],i,1});
  }
  sweep();
  for(i=0;i<q;i++)
  {
      if(cat[i]) A[i]=1;
      else A[i]=0;
  }
  return A;
}

Compilation message (stderr)

werewolf.cpp: In member function 'void arbore::dfs(int)':
werewolf.cpp:26:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      for(int i=0;i<ad[x].size();i++)
                  ~^~~~~~~~~~~~~
werewolf.cpp: In function 'void sweep()':
werewolf.cpp:85:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(j=0;j<qr[i].size();j++)
                 ~^~~~~~~~~~~~~
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:105:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(j=0;j<v[i].size();j++)
               ~^~~~~~~~~~~~
werewolf.cpp:117:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(j=0;j<v[i].size();j++)
               ~^~~~~~~~~~~~

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