Submission #392508

#	Time	Username	Problem	Language	Result	Execution time	Memory
392508		uacoder123	Werewolf (IOI18_werewolf)	C++14	100 / 100	1035 ms	149372 KiB

werewolf

#include <bits/stdc++.h>
#include "werewolf.h"
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#define F first
#define S second
#define FOR(i,a,b) for (auto i = (a); i <= (b); ++i)
#define NFOR(i,a,b) for(auto i = (a); i >= (b); --i)
#define all(x) (x).begin(), (x).end()
#define sz(x) lli(x.size())
#define mp(i,a) make_pair(i,a)
#define pb(a) push_back(a)
#define bit(x,b) (x&(1LL<<b))
typedef long long int lli;
typedef pair <lli,lli> ii;
typedef pair <ii,lli> iii;
typedef pair <ii,ii> iiii;
typedef vector <lli> vi;
typedef tree<lli,null_type,less<lli>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
int n,m,q,co1=0,co2=0;
vi al[2*100001],al1[5*100001],al2[5*100001];
vector<ii> qu1[2*100001],qu2[2*100001];
int r1[2*100001],r2[2*100001],par1[5*100001],par2[5*100001],preco1=0,preco2=0,pre1[2*100001],pre2[2*100001];
ii nr1[5*100001],nr2[5*100001];
int segt1[4*2*100001];
vector<ii> gr;
int find1(int f)
{
  if(par1[par1[f]]!=par1[f]) par1[f]=find1(par1[f]);
  return par1[f];
}
int find2(int f)
{
  if(par2[par2[f]]!=par2[f]) par2[f]=find2(par2[f]);
  return par2[f];
}
void add1(int v)
{
  al[v].pb(v);
  par1[co1]=co1;
  for(int i=0;i<al[v].size();++i)
  {
    if(al[v][i]>=v)
    {
      int p=find1(al[v][i]);
      if(p==co1)
        continue;
      al1[co1].pb(p);
      par1[p]=co1;
    }
  }
  co1++;
}
void answer1(int v)
{
  for(int j=0;j<qu1[v].size();++j)
    r1[qu1[v][j].S]=find1(qu1[v][j].F);
}

void add2(int v)
{
  par2[co2]=co2;
  al[v].pb(v);
  for(int i=0;i<al[v].size();++i)
  {
    if(al[v][i]<=v)
    {
      int p=find2(al[v][i]);
      if(p==co2)
        continue;
      al2[co2].pb(p);
      par2[p]=co2;
    }
  }
  co2++;
}
void answer2(int v)
{
  for(int j=0;j<qu2[v].size();++j)
    r2[qu2[v][j].S]=find2(qu2[v][j].F);
}
void dfs1(int node)
{
  if(al1[node].size()==0)
  {
    pre1[node]=preco1;
    nr1[node]=mp(preco1,preco1);
    preco1++;
  }
  else
    nr1[node]=mp(n+10,-1);
  for(int i=0;i<al1[node].size();++i)
  {
    dfs1(al1[node][i]);
    nr1[node].F=min(nr1[node].F,nr1[al1[node][i]].F);
    nr1[node].S=max(nr1[node].S,nr1[al1[node][i]].S);
  }
}
void dfs2(int node)
{
  if(al2[node].size()==0)
  {
    pre2[node]=preco2;
    nr2[node]=mp(preco2,preco2);
    preco2++;
  }
  else
    nr2[node]=mp(n+20,-2);
  for(int i=0;i<al2[node].size();++i)
  {
    dfs2(al2[node][i]);
    nr2[node].F=min(nr2[node].F,nr2[al2[node][i]].F);
    nr2[node].S=max(nr2[node].S,nr2[al2[node][i]].S);
  }
}
void up1(int node,int l,int r,int in)
{
  if(l==r)
  {
    segt1[node]+=1;
    return;
  }
  int mid=(l+r)/2;
  if(in<=mid)
    up1(2*node+1,l,mid,in);
  else
    up1(2*node+2,mid+1,r,in);
  segt1[node]=segt1[2*node+1]+segt1[2*node+2];
}
int query1(int node,int l,int r,int s,int e)
{
  if(l>e||r<s)
    return 0;
  if(l>=s&&r<=e)
    return segt1[node];
  int mid=(l+r)/2;
  int q1=query1(2*node+1,l,mid,s,e);
  int q2=query1(2*node+2,mid+1,r,s,e);
  return q1+q2;
}

vector<iiii> rqu1[2*100001];
int ans[5*100001];
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) 
{
  n=N;
  q=S.size();
  m=X.size();
  for(int i=0;i<n;++i)
  {
    par1[i]=i;
    par2[i]=i;
  }
  co1=n;
  co2=n;
  for(int i=0;i<m;++i)
  {
    al[X[i]].pb(Y[i]);
    al[Y[i]].pb(X[i]);
  }
  for(int i=0;i<q;++i)
  {
    qu1[L[i]].pb(mp(S[i],i));
    qu2[R[i]].pb(mp(E[i],i));
  }
  for(int i=n-1;i>=0;--i)
  {
    add1(i);
    answer1(i);
  }
  for(int i=0;i<n;++i)
  {
    add2(i);
    answer2(i);
  }
  dfs1(co1-1);
  dfs2(co2-1);
  for(int i=0;i<n;++i)
    gr.pb(mp(pre1[i],pre2[i]));
  sort(all(gr));
  for(int i=0;i<q;++i)
  {
    int x1=nr1[r1[i]].F,x2=nr1[r1[i]].S,y1=nr2[r2[i]].F,y2=nr2[r2[i]].S;
    if(x1-1>=0)
      rqu1[x1-1].pb(mp(mp(y1,y2),mp(i,1)));
      rqu1[x2].pb(mp(mp(y1,y2),mp(i,2)));

  }
  for(int i=0;i<n;++i)
  {
    up1(0,0,n-1,gr[i].S);
    while(rqu1[i].size())
    {
      if(rqu1[i].back().S.S==1)
        ans[rqu1[i].back().S.F]+=-query1(0,0,n-1,rqu1[i].back().F.F,rqu1[i].back().F.S);
      else
        ans[rqu1[i].back().S.F]+=+query1(0,0,n-1,rqu1[i].back().F.F,rqu1[i].back().F.S);
      rqu1[i].pop_back();
    }
  }
  vector<int> A;
  for(int i=0;i<q;++i)
  {
    if(ans[i]>0)
      A.pb(1);
    else
      A.pb(0);
  }
  return A;
}

Compilation message (stderr)

werewolf.cpp: In function 'void add1(int)':
werewolf.cpp:42:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |   for(int i=0;i<al[v].size();++i)
      |               ~^~~~~~~~~~~~~
werewolf.cpp: In function 'void answer1(int)':
werewolf.cpp:57:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |   for(int j=0;j<qu1[v].size();++j)
      |               ~^~~~~~~~~~~~~~
werewolf.cpp: In function 'void add2(int)':
werewolf.cpp:65:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |   for(int i=0;i<al[v].size();++i)
      |               ~^~~~~~~~~~~~~
werewolf.cpp: In function 'void answer2(int)':
werewolf.cpp:80:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |   for(int j=0;j<qu2[v].size();++j)
      |               ~^~~~~~~~~~~~~~
werewolf.cpp: In function 'void dfs1(int)':
werewolf.cpp:93:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |   for(int i=0;i<al1[node].size();++i)
      |               ~^~~~~~~~~~~~~~~~~
werewolf.cpp: In function 'void dfs2(int)':
werewolf.cpp:110:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |   for(int i=0;i<al2[node].size();++i)
      |               ~^~~~~~~~~~~~~~~~~
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:185:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  185 |     if(x1-1>=0)
      |     ^~
werewolf.cpp:187:7: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  187 |       rqu1[x2].pb(mp(mp(y1,y2),mp(i,2)));
      |       ^~~~

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