oj.uz

Submission #370783

# Submission time Handle Problem Language Result Execution time Memory
370783 2021-02-24T15:27:03 Z rumen_m Werewolf (IOI18_werewolf) C++17
100 / 100
 1062 ms 136516 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 19 ms 30188 KB Output is correct
2 Correct 19 ms 30188 KB Output is correct
3 Correct 18 ms 30188 KB Output is correct
4 Correct 19 ms 30208 KB Output is correct
5 Correct 18 ms 30188 KB Output is correct
6 Correct 18 ms 30188 KB Output is correct
7 Correct 18 ms 30188 KB Output is correct
8 Correct 18 ms 30188 KB Output is correct
9 Correct 19 ms 30188 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 30188 KB Output is correct
2 Correct 19 ms 30188 KB Output is correct
3 Correct 18 ms 30188 KB Output is correct
4 Correct 19 ms 30208 KB Output is correct
5 Correct 18 ms 30188 KB Output is correct
6 Correct 18 ms 30188 KB Output is correct
7 Correct 18 ms 30188 KB Output is correct
8 Correct 18 ms 30188 KB Output is correct
9 Correct 19 ms 30188 KB Output is correct
10 Correct 26 ms 31700 KB Output is correct
11 Correct 25 ms 31700 KB Output is correct
12 Correct 25 ms 31704 KB Output is correct
13 Correct 26 ms 31828 KB Output is correct
14 Correct 25 ms 31848 KB Output is correct
15 Correct 32 ms 31828 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 822 ms 118136 KB Output is correct
2 Correct 827 ms 129992 KB Output is correct
3 Correct 766 ms 127540 KB Output is correct
4 Correct 751 ms 126664 KB Output is correct
5 Correct 742 ms 126460 KB Output is correct
6 Correct 809 ms 126408 KB Output is correct
7 Correct 834 ms 126280 KB Output is correct
8 Correct 761 ms 129756 KB Output is correct
9 Correct 728 ms 127420 KB Output is correct
10 Correct 646 ms 126460 KB Output is correct
11 Correct 661 ms 126588 KB Output is correct
12 Correct 774 ms 126440 KB Output is correct
13 Correct 830 ms 131144 KB Output is correct
14 Correct 840 ms 131124 KB Output is correct
15 Correct 870 ms 131016 KB Output is correct
16 Correct 859 ms 131016 KB Output is correct
17 Correct 786 ms 126396 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 30188 KB Output is correct
2 Correct 19 ms 30188 KB Output is correct
3 Correct 18 ms 30188 KB Output is correct
4 Correct 19 ms 30208 KB Output is correct
5 Correct 18 ms 30188 KB Output is correct
6 Correct 18 ms 30188 KB Output is correct
7 Correct 18 ms 30188 KB Output is correct
8 Correct 18 ms 30188 KB Output is correct
9 Correct 19 ms 30188 KB Output is correct
10 Correct 26 ms 31700 KB Output is correct
11 Correct 25 ms 31700 KB Output is correct
12 Correct 25 ms 31704 KB Output is correct
13 Correct 26 ms 31828 KB Output is correct
14 Correct 25 ms 31848 KB Output is correct
15 Correct 32 ms 31828 KB Output is correct
16 Correct 822 ms 118136 KB Output is correct
17 Correct 827 ms 129992 KB Output is correct
18 Correct 766 ms 127540 KB Output is correct
19 Correct 751 ms 126664 KB Output is correct
20 Correct 742 ms 126460 KB Output is correct
21 Correct 809 ms 126408 KB Output is correct
22 Correct 834 ms 126280 KB Output is correct
23 Correct 761 ms 129756 KB Output is correct
24 Correct 728 ms 127420 KB Output is correct
25 Correct 646 ms 126460 KB Output is correct
26 Correct 661 ms 126588 KB Output is correct
27 Correct 774 ms 126440 KB Output is correct
28 Correct 830 ms 131144 KB Output is correct
29 Correct 840 ms 131124 KB Output is correct
30 Correct 870 ms 131016 KB Output is correct
31 Correct 859 ms 131016 KB Output is correct
32 Correct 786 ms 126396 KB Output is correct
33 Correct 891 ms 127812 KB Output is correct
34 Correct 415 ms 71484 KB Output is correct
35 Correct 957 ms 130296 KB Output is correct
36 Correct 894 ms 127056 KB Output is correct
37 Correct 932 ms 129492 KB Output is correct
38 Correct 964 ms 127556 KB Output is correct
39 Correct 873 ms 136276 KB Output is correct
40 Correct 1062 ms 135948 KB Output is correct
41 Correct 849 ms 128960 KB Output is correct
42 Correct 769 ms 127048 KB Output is correct
43 Correct 967 ms 133956 KB Output is correct
44 Correct 876 ms 129444 KB Output is correct
45 Correct 789 ms 136516 KB Output is correct
46 Correct 803 ms 136128 KB Output is correct
47 Correct 835 ms 131276 KB Output is correct
48 Correct 822 ms 131044 KB Output is correct
49 Correct 836 ms 131144 KB Output is correct
50 Correct 813 ms 131144 KB Output is correct
51 Correct 983 ms 136392 KB Output is correct
52 Correct 991 ms 136412 KB Output is correct