oj.uz

Submission #392508

# Submission time Handle Problem Language Result Execution time Memory
392508 2021-04-21T09:22:10 Z uacoder123 Werewolf (IOI18_werewolf) C++14
100 / 100
 1035 ms 149372 KB 
#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

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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 42564 KB Output is correct
2 Correct 26 ms 42576 KB Output is correct
3 Correct 27 ms 42616 KB Output is correct
4 Correct 25 ms 42568 KB Output is correct
5 Correct 26 ms 42572 KB Output is correct
6 Correct 25 ms 42572 KB Output is correct
7 Correct 26 ms 42572 KB Output is correct
8 Correct 25 ms 42572 KB Output is correct
9 Correct 25 ms 42588 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 42564 KB Output is correct
2 Correct 26 ms 42576 KB Output is correct
3 Correct 27 ms 42616 KB Output is correct
4 Correct 25 ms 42568 KB Output is correct
5 Correct 26 ms 42572 KB Output is correct
6 Correct 25 ms 42572 KB Output is correct
7 Correct 26 ms 42572 KB Output is correct
8 Correct 25 ms 42572 KB Output is correct
9 Correct 25 ms 42588 KB Output is correct
10 Correct 33 ms 44120 KB Output is correct
11 Correct 34 ms 44108 KB Output is correct
12 Correct 34 ms 44128 KB Output is correct
13 Correct 33 ms 44240 KB Output is correct
14 Correct 33 ms 44132 KB Output is correct
15 Correct 36 ms 44200 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 897 ms 130676 KB Output is correct
2 Correct 829 ms 143236 KB Output is correct
3 Correct 810 ms 139448 KB Output is correct
4 Correct 830 ms 137248 KB Output is correct
5 Correct 825 ms 137104 KB Output is correct
6 Correct 873 ms 139308 KB Output is correct
7 Correct 745 ms 133460 KB Output is correct
8 Correct 788 ms 143044 KB Output is correct
9 Correct 686 ms 133004 KB Output is correct
10 Correct 650 ms 135740 KB Output is correct
11 Correct 700 ms 136732 KB Output is correct
12 Correct 770 ms 136112 KB Output is correct
13 Correct 743 ms 135776 KB Output is correct
14 Correct 758 ms 135812 KB Output is correct
15 Correct 743 ms 135600 KB Output is correct
16 Correct 753 ms 135852 KB Output is correct
17 Correct 747 ms 133616 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 42564 KB Output is correct
2 Correct 26 ms 42576 KB Output is correct
3 Correct 27 ms 42616 KB Output is correct
4 Correct 25 ms 42568 KB Output is correct
5 Correct 26 ms 42572 KB Output is correct
6 Correct 25 ms 42572 KB Output is correct
7 Correct 26 ms 42572 KB Output is correct
8 Correct 25 ms 42572 KB Output is correct
9 Correct 25 ms 42588 KB Output is correct
10 Correct 33 ms 44120 KB Output is correct
11 Correct 34 ms 44108 KB Output is correct
12 Correct 34 ms 44128 KB Output is correct
13 Correct 33 ms 44240 KB Output is correct
14 Correct 33 ms 44132 KB Output is correct
15 Correct 36 ms 44200 KB Output is correct
16 Correct 897 ms 130676 KB Output is correct
17 Correct 829 ms 143236 KB Output is correct
18 Correct 810 ms 139448 KB Output is correct
19 Correct 830 ms 137248 KB Output is correct
20 Correct 825 ms 137104 KB Output is correct
21 Correct 873 ms 139308 KB Output is correct
22 Correct 745 ms 133460 KB Output is correct
23 Correct 788 ms 143044 KB Output is correct
24 Correct 686 ms 133004 KB Output is correct
25 Correct 650 ms 135740 KB Output is correct
26 Correct 700 ms 136732 KB Output is correct
27 Correct 770 ms 136112 KB Output is correct
28 Correct 743 ms 135776 KB Output is correct
29 Correct 758 ms 135812 KB Output is correct
30 Correct 743 ms 135600 KB Output is correct
31 Correct 753 ms 135852 KB Output is correct
32 Correct 747 ms 133616 KB Output is correct
33 Correct 972 ms 141252 KB Output is correct
34 Correct 343 ms 100016 KB Output is correct
35 Correct 1000 ms 144060 KB Output is correct
36 Correct 922 ms 139868 KB Output is correct
37 Correct 991 ms 143180 KB Output is correct
38 Correct 954 ms 140592 KB Output is correct
39 Correct 896 ms 149328 KB Output is correct
40 Correct 945 ms 145240 KB Output is correct
41 Correct 883 ms 141228 KB Output is correct
42 Correct 702 ms 129072 KB Output is correct
43 Correct 1035 ms 149372 KB Output is correct
44 Correct 914 ms 143260 KB Output is correct
45 Correct 793 ms 148392 KB Output is correct
46 Correct 747 ms 147292 KB Output is correct
47 Correct 762 ms 136324 KB Output is correct
48 Correct 750 ms 135732 KB Output is correct
49 Correct 780 ms 136352 KB Output is correct
50 Correct 775 ms 139068 KB Output is correct
51 Correct 905 ms 147928 KB Output is correct
52 Correct 912 ms 148036 KB Output is correct