Submission #370783

#	Time	Username	Problem	Language	Result	Execution time	Memory
370783		rumen_m	Werewolf (IOI18_werewolf)	C++17	100 / 100	1062 ms	136516 KiB

werewolf

#include "werewolf.h"
# include <bits/stdc++.h>
using namespace std;
const int maxn = 200010;
const int MAXN = 400005;
const int logN = 20;
struct DSU
{
    int par[MAXN];

    DSU()
    {
        int i;
        for(i=0;i<maxn;i++)
        {
            par[i] = i;
        }
    }
    int root(int v)
    {
        if(par[v]==v)return v;
        par[v] = root(par[v]);
        return par[v];
    }
    void connect(int v, int u)
    {
        int v1 = root(v);
        int u1 = root(u);
        par[v1] = u1;
    }
};
struct Task
{
    int x, y1,y2,type,idx;
    Task(int __x, int __y)
    {
        x = __x;
        y1 = __y;
        type = 2;
    }
    Task(int __x, int __y1, int __y2, int __type, int __idx)
    {
        x = __x;
        y1 = __y1;
        y2 = __y2;
        type = __type;
        idx = __idx;
    }
};
vector <Task> q;
DSU du,dv;
vector <int> U[MAXN], V[MAXN];
vector <int> g[MAXN];
vector <int> eV,eU;
int inV[MAXN],outV[MAXN],inU[MAXN],outU[MAXN];
int upV[MAXN][21],upU[MAXN][21];
int pU[MAXN];
void dfsV(int v, int p)
{
    //cout<<v<<endl;
    eV.push_back(v);
    inV[v] = eV.size()-1;
    upV[v][0] = p;
    for(auto u:V[v])
    {
        if(u==p)continue;
        dfsV(u,v);
    }
    outV[v] = eV.size()-1;
    return ;
}
void dfsU(int v, int p)
{
   // cout<<v<<endl;
    eU.push_back(v);
    inU[v] = eU.size()-1;
    upU[v][0] = p;
    for(auto u:U[v])
    {
        if(u==p)continue;
        dfsU(u,v);
    }
    outU[v] = eU.size()-1;
    return ;
}
bool cmp(Task i, Task j)
{
    if(i.x==j.x)
    {
        if(i.type == 2)return true;
        if(j.type == 2)return false;
        return i.type<j.type;
    }
    return i.x<j.x;
}
struct Fenwik
{
    int fen[maxn];
    void update(int idx, int delta)
    {
        idx++;
        for(;idx<maxn;idx+= (idx&(-idx)))
        {
            fen[idx]+=delta;
        }
    }
    int query(int idx)
    {
        idx++;
        int ans = 0;
        for(;idx>0;idx-=(idx&(-idx)))
        {
            ans+=fen[idx];
        }
        return ans;
    }
    int diff(int a, int b)
    {

       // a++;
       // b++;
        if(a==0)
            return query(b);
            int ans  = query(b)-query(a-1);
          // cout<<"DIFF"<<a<<" "<<b<<" "<<ans<<endl;
        return ans;
    }
};
Fenwik f;
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) {


  int i,j;
  for(i=0;i<X.size();i++)
  {
      g[X[i]].push_back(Y[i]);
      g[Y[i]].push_back(X[i]);
  }
  for(i=0;i<N;i++)
  {
      for(auto v:g[i])
      {
          //cout<<v<<endl;
          if(v>=i)continue;
          int u1 = dv.root(i);
          int v1 = dv.root(v);
          if(u1==v1)continue;
          V[u1].push_back(v1);
          V[v1].push_back(u1);

          dv.connect(v1,u1);
      }
  }
  dfsV(N-1,N-1);

    for(i=N-1;i>=0;i--)
  {
      for(auto v:g[i])
      {
          if(v<=i)continue;
          int u1 = du.root(i);
          int v1 = du.root(v);
          if(u1==v1)continue;
          U[u1].push_back(v1);
          U[v1].push_back(u1);
         // cout<<"Edge "<<u1<<" "<<v1<<endl;
          du.connect(v1,u1);
      }
  }
  dfsU(0,0);
    /* for(i=0;i<N;i++)
        cout<<eU[i]<<" ";
    cout<<endl;
    for(i=0;i<N;i++)
        cout<<i<<" : "<<inU[i]<<" "<<outU[i]<<endl;*/
  for(i=1;i<logN;i++)
  {
      for(j=0;j<N;j++)
      {
          upV[j][i] = upV[upV[j][i-1]][i-1];
          upU[j][i] = upU[upU[j][i-1]][i-1];
      }
  }
  for(i=0;i<N;i++)
  {//cout<<eU[i]<<" "<<i<<endl;
      pU[eU[i]] = i;
  }
  for(i=0;i<N;i++)
  {
    //  cout<<i<<" & "<<pU[eV[i]]<<endl;
      q.push_back(Task(i,pU[eV[i]]));
  }

  for(i=0;i<S.size();i++)
  {
      int s = S[i];
      int e = E[i];
      int l = L[i];
      int r = R[i];
        for(j = logN-1;j>=0;j--)
        {
            if(upV[e][j]<=r)
            {
                e = upV[e][j];
            }
            if(upU[s][j]>=l)
            {
                s = upU[s][j];
            }
        }
    int l1 = inV[e];
    int r1 = outV[e];
    int l2 = inU[s];
    int r2 = outU[s];
   // cout<<i<<"  : "<<l1<<" "<<r1<<" "<<l2<<" "<<r2<<endl;
    q.push_back(Task(l1-1,l2,r2,0,i));
    q.push_back(Task(r1,l2,r2,1,i));
  }
  sort(q.begin(),q.end(),cmp);
  std::vector<int> A(S.size());
  for(i=0;i<q.size();i++)
  {
      Task cur = q[i];
     // cout<<cur.x<<" "<<cur.type<<endl;
      if(cur.type==2)
      {
         // cout<<"ADD "<<cur.y1<<endl;
          f.update(cur.y1,1);
      }
      if(cur.type==0)
      {
//cout<<cur.idx<<"|| "<<cur.x<<" "<<cur.type<<" "<<cur.y1<<" "<<cur.y2<<" "<<f.diff(cur.y1,cur.y2)<<endl;
          A[cur.idx]-=f.diff(cur.y1,cur.y2);
      }
      if(cur.type==1)
      {//cout<<cur.idx<<"&& "<<cur.x<<" "<<cur.type<<" "<<cur.y1<<" "<<cur.y2<<" "<<f.diff(cur.y1,cur.y2)<<endl;
          A[cur.idx]+=f.diff(cur.y1,cur.y2);
      }
  }
  for(i=0;i<S.size();i++)
  {
      if(A[i]>0)A[i] = 1;
      else
        A[i] = 0;
        if(S[i]<L[i]||E[i]>R[i])
            A[i] = 0;
    //  cout<<A[i]<<" ";

  } //cout<<endl;


  return A;
}
/*
6 6 3
5 1
1 2
1 3
3 4
3 0
5 2
4 2 1 2
4 2 2 2
5 4 3 4

*/

Compilation message (stderr)

werewolf.cpp: In member function 'int Fenwik::diff(int, int)':
werewolf.cpp:122:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  122 |         if(a==0)
      |         ^~
werewolf.cpp:124:13: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  124 |             int ans  = query(b)-query(a-1);
      |             ^~~
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:136:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  136 |   for(i=0;i<X.size();i++)
      |           ~^~~~~~~~~
werewolf.cpp:196:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  196 |   for(i=0;i<S.size();i++)
      |           ~^~~~~~~~~
werewolf.cpp:223:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Task>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  223 |   for(i=0;i<q.size();i++)
      |           ~^~~~~~~~~
werewolf.cpp:242:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  242 |   for(i=0;i<S.size();i++)
      |           ~^~~~~~~~~
werewolf.cpp:245:7: warning: this 'else' clause does not guard... [-Wmisleading-indentation]
  245 |       else
      |       ^~~~
werewolf.cpp:247:9: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'else'
  247 |         if(S[i]<L[i]||E[i]>R[i])
      |         ^~

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