oj.uz

Submission #80183

# Submission time Handle Problem Language Result Execution time Memory
80183 2018-10-19T12:47:12 Z Bodo171 Werewolf (IOI18_werewolf) C++14
100 / 100
 1283 ms 405488 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 20 ms 19448 KB Output is correct
2 Correct 20 ms 19460 KB Output is correct
3 Correct 19 ms 19524 KB Output is correct
4 Correct 23 ms 19680 KB Output is correct
5 Correct 19 ms 19732 KB Output is correct
6 Correct 19 ms 19752 KB Output is correct
7 Correct 22 ms 19752 KB Output is correct
8 Correct 25 ms 19892 KB Output is correct
9 Correct 18 ms 19892 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 19448 KB Output is correct
2 Correct 20 ms 19460 KB Output is correct
3 Correct 19 ms 19524 KB Output is correct
4 Correct 23 ms 19680 KB Output is correct
5 Correct 19 ms 19732 KB Output is correct
6 Correct 19 ms 19752 KB Output is correct
7 Correct 22 ms 19752 KB Output is correct
8 Correct 25 ms 19892 KB Output is correct
9 Correct 18 ms 19892 KB Output is correct
10 Correct 26 ms 20940 KB Output is correct
11 Correct 26 ms 21220 KB Output is correct
12 Correct 26 ms 21228 KB Output is correct
13 Correct 26 ms 21444 KB Output is correct
14 Correct 28 ms 21552 KB Output is correct
15 Correct 26 ms 21692 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 1229 ms 93936 KB Output is correct
2 Correct 948 ms 103936 KB Output is correct
3 Correct 926 ms 110564 KB Output is correct
4 Correct 940 ms 117556 KB Output is correct
5 Correct 964 ms 126060 KB Output is correct
6 Correct 1041 ms 135856 KB Output is correct
7 Correct 1065 ms 142376 KB Output is correct
8 Correct 836 ms 154224 KB Output is correct
9 Correct 583 ms 158860 KB Output is correct
10 Correct 518 ms 167200 KB Output is correct
11 Correct 568 ms 175464 KB Output is correct
12 Correct 576 ms 183264 KB Output is correct
13 Correct 1190 ms 199192 KB Output is correct
14 Correct 1198 ms 206884 KB Output is correct
15 Correct 1226 ms 215100 KB Output is correct
16 Correct 1283 ms 223396 KB Output is correct
17 Correct 913 ms 224832 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 19448 KB Output is correct
2 Correct 20 ms 19460 KB Output is correct
3 Correct 19 ms 19524 KB Output is correct
4 Correct 23 ms 19680 KB Output is correct
5 Correct 19 ms 19732 KB Output is correct
6 Correct 19 ms 19752 KB Output is correct
7 Correct 22 ms 19752 KB Output is correct
8 Correct 25 ms 19892 KB Output is correct
9 Correct 18 ms 19892 KB Output is correct
10 Correct 26 ms 20940 KB Output is correct
11 Correct 26 ms 21220 KB Output is correct
12 Correct 26 ms 21228 KB Output is correct
13 Correct 26 ms 21444 KB Output is correct
14 Correct 28 ms 21552 KB Output is correct
15 Correct 26 ms 21692 KB Output is correct
16 Correct 1229 ms 93936 KB Output is correct
17 Correct 948 ms 103936 KB Output is correct
18 Correct 926 ms 110564 KB Output is correct
19 Correct 940 ms 117556 KB Output is correct
20 Correct 964 ms 126060 KB Output is correct
21 Correct 1041 ms 135856 KB Output is correct
22 Correct 1065 ms 142376 KB Output is correct
23 Correct 836 ms 154224 KB Output is correct
24 Correct 583 ms 158860 KB Output is correct
25 Correct 518 ms 167200 KB Output is correct
26 Correct 568 ms 175464 KB Output is correct
27 Correct 576 ms 183264 KB Output is correct
28 Correct 1190 ms 199192 KB Output is correct
29 Correct 1198 ms 206884 KB Output is correct
30 Correct 1226 ms 215100 KB Output is correct
31 Correct 1283 ms 223396 KB Output is correct
32 Correct 913 ms 224832 KB Output is correct
33 Correct 1218 ms 235020 KB Output is correct
34 Correct 407 ms 235020 KB Output is correct
35 Correct 1141 ms 256516 KB Output is correct
36 Correct 1068 ms 263432 KB Output is correct
37 Correct 1226 ms 272392 KB Output is correct
38 Correct 1178 ms 279672 KB Output is correct
39 Correct 1018 ms 293308 KB Output is correct
40 Correct 1067 ms 302372 KB Output is correct
41 Correct 863 ms 305628 KB Output is correct
42 Correct 594 ms 311360 KB Output is correct
43 Correct 1084 ms 327756 KB Output is correct
44 Correct 1052 ms 332508 KB Output is correct
45 Correct 671 ms 344064 KB Output is correct
46 Correct 762 ms 353044 KB Output is correct
47 Correct 1048 ms 360624 KB Output is correct
48 Correct 1149 ms 367932 KB Output is correct
49 Correct 1184 ms 376588 KB Output is correct
50 Correct 1212 ms 383780 KB Output is correct
51 Correct 868 ms 394172 KB Output is correct
52 Correct 977 ms 405488 KB Output is correct