oj.uz

Submission #75012

# Submission time Handle Problem Language Result Execution time Memory
75012 2018-09-08T03:39:21 Z faustaadp Werewolf (IOI18_werewolf) C++17
49 / 100
 3574 ms 133980 KB 
#include "werewolf.h"
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
ll i,j,b[202020][2],ux,uy,nx,dep[202020],p[22][202020],mi[22][202020],ma[22][202020],LL,RR,C,bisa,ganti,CC,De[202020];
vector<ll> v[202020];
void dfs(ll aa,ll bb)
{
    dep[aa]=bb;
    ll ii;
    for(ii=0;ii<v[aa].size();ii++)
    {
        if(dep[v[aa][ii]]>0)
            continue;
        else
        {
            p[0][v[aa][ii]]=aa;
            dfs(v[aa][ii],bb+1);
        }
    }
}
ll P(ll aa,ll bb)
{
    ll ii;
    for(ii=20;ii>=0;ii--)
    {
        if(bb>=((1<<ii)))
        {
            aa=p[ii][aa];
            bb-=(1<<ii);
        }
    }
    return aa;
}
ll MI(ll aa,ll bb)
{
    if(dep[aa]<dep[bb])
        swap(aa,bb);
    ll ii,Mi=1e18;
    for(ii=20;ii>=0;ii--)
    {
        if((dep[aa]-(1<<ii))>=(dep[bb]))
        {
            Mi=min(Mi,mi[ii][aa]);
            aa=p[ii][aa];
        }
    }
    if(aa==bb)
        return min(Mi,mi[0][aa]);
    for(ii=20;ii>=0;ii--)
    {
        if(p[ii][aa]!=p[ii][bb])
        {
            Mi=min(Mi,mi[ii][aa]);
            Mi=min(Mi,mi[ii][bb]);
            aa=p[ii][aa];
            bb=p[ii][bb];
        }
    }
    return min(Mi,min(mi[1][aa],mi[1][bb]));
}
ll MA(ll aa,ll bb)
{
    if(dep[aa]<dep[bb])
        swap(aa,bb);
    ll ii,Ma=-1e18;
    for(ii=20;ii>=0;ii--)
    {
        if((dep[aa]-(1<<ii))>=(dep[bb]))
        {
            Ma=max(Ma,ma[ii][aa]);
            aa=p[ii][aa];
        }
    }
    if(aa==bb)
        return max(Ma,ma[0][aa]);
    for(ii=20;ii>=0;ii--)
    {
        if(p[ii][aa]!=p[ii][bb])
        {
            Ma=min(Ma,ma[ii][aa]);
            Ma=min(Ma,ma[ii][bb]);
            aa=p[ii][aa];
            bb=p[ii][bb];
        }
    }
    return max(Ma,max(ma[1][aa],ma[1][bb]));
}
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 Q = S.size();
        std::vector<int> A;
      for(i=0;i<X.size();i++)
      {
            v[X[i]].pb(Y[i]);
            v[Y[i]].pb(X[i]);
            De[X[i]]++;
            De[Y[i]]++;
      }
        int M=X.size();
      if(M<=6000&&N<=3000&&Q<=3000)
      {
          for(i=0;i<Q;i++)
          {
                memset(b,0,sizeof(b));
                queue<pair<ll,ll> > q;
                if(S[i]>=L[i]||1)
                {
                    q.push(mp(S[i],0));
                    b[S[i]][0]=1;
                }
                while(!q.empty())
                {
                    ux=q.front().fi;
                    uy=q.front().se;
               //     cout<<ux<<" "<<uy<<"\n";
                    q.pop();
                    for(j=0;j<v[ux].size();j++)
                    {
                        nx=v[ux][j];
                        if((b[nx][uy]==0)&&((uy==0&&nx>=L[i])||(uy==1&&nx<=R[i])))
                        {
                            b[nx][uy]=1;
                            q.push(mp(nx,uy));
                        }
                    }
                    if(L[i]<=ux&&ux<=R[i]&&uy==0)
                    {
                        b[ux][1]=1;
                        q.push(mp(ux,1));
                    }
                }
                A.pb(b[E[i]][1]);
          }
      }
      else
        if(X.size()==N-1)
      {
            ll NOO=0;
            for(i=0;i<N;i++)
                if(De[i]==1)
                    NOO=i;
            p[0][NOO]=NOO;
            dfs(NOO,1);
            for(i=0;i<N;i++)
            {
                mi[0][i]=i;
                ma[0][i]=i;
            }
            for(i=1;i<=20;i++)
                for(j=0;j<N;j++)
                {
                    p[i][j]=p[i-1][p[i-1][j]];
                    mi[i][j]=min(mi[i-1][j],mi[i-1][p[i-1][j]]);
                    ma[i][j]=max(ma[i-1][j],ma[i-1][p[i-1][j]]);
                }
            /*while(1)
            {
                ll ta,tb;
                cin>>ta>>tb;
                cout<<MI(ta,tb)<<"\n";
            }*/
           // cout<<NOO<<"\n";
            for(i=0;i<Q;i++)
            {
                if(dep[S[i]]>dep[E[i]])
                {
                    ganti=-1;
                    LL=0;
                    RR=dep[S[i]]-dep[E[i]];
                    while(LL<=RR)
                    {
                        C=(LL+RR)/2;
                        CC=P(S[i],C);
                        if((MI(S[i],CC)>=L[i]))
                        {
                            ganti=CC;
                            LL=C+1;
                        }
                        else
                            RR=C-1;
                    }
                    if(ganti!=-1&&(MA(ganti,E[i])<=R[i]))
                    {
                        A.pb(1);
                        continue;
                    }
                }
                else
                {
                    ganti=-1;
                    LL=0;
                    RR=dep[E[i]]-dep[S[i]];
                    while(LL<=RR)
                    {
                        C=(LL+RR)/2;
                        CC=P(E[i],C);
                        if((MA(E[i],CC)<=R[i]))
                        {
                            ganti=CC;
                            LL=C+1;
                        }
                        else
                            RR=C-1;
                    }
                    if(ganti!=-1&&(MI(ganti,S[i])>=L[i]))
                    {
                        A.pb(1);
                        continue;
                    }
                }
                A.pb(0);
            }

      }
      return A;
}

Compilation message

werewolf.cpp: In function 'void dfs(long long int, long long int)':
werewolf.cpp:15:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(ii=0;ii<v[aa].size();ii++)
              ~~^~~~~~~~~~~~~
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:99:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(i=0;i<X.size();i++)
               ~^~~~~~~~~
werewolf.cpp:124:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                     for(j=0;j<v[ux].size();j++)
                             ~^~~~~~~~~~~~~
werewolf.cpp:143:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(X.size()==N-1)
            ~~~~~~~~^~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 8312 KB Output is correct
2 Correct 28 ms 8428 KB Output is correct
3 Correct 27 ms 8428 KB Output is correct
4 Correct 26 ms 8428 KB Output is correct
5 Correct 27 ms 8472 KB Output is correct
6 Correct 27 ms 8472 KB Output is correct
7 Correct 28 ms 8472 KB Output is correct
8 Correct 26 ms 8536 KB Output is correct
9 Correct 27 ms 8536 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 8312 KB Output is correct
2 Correct 28 ms 8428 KB Output is correct
3 Correct 27 ms 8428 KB Output is correct
4 Correct 26 ms 8428 KB Output is correct
5 Correct 27 ms 8472 KB Output is correct
6 Correct 27 ms 8472 KB Output is correct
7 Correct 28 ms 8472 KB Output is correct
8 Correct 26 ms 8536 KB Output is correct
9 Correct 27 ms 8536 KB Output is correct
10 Correct 1193 ms 9164 KB Output is correct
11 Correct 937 ms 9164 KB Output is correct
12 Correct 561 ms 9164 KB Output is correct
13 Correct 1110 ms 9164 KB Output is correct
14 Correct 909 ms 9164 KB Output is correct
15 Correct 896 ms 9340 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 3405 ms 133768 KB Output is correct
2 Correct 3206 ms 133768 KB Output is correct
3 Correct 3255 ms 133904 KB Output is correct
4 Correct 3405 ms 133904 KB Output is correct
5 Correct 3453 ms 133904 KB Output is correct
6 Correct 3574 ms 133904 KB Output is correct
7 Correct 3527 ms 133904 KB Output is correct
8 Correct 3103 ms 133904 KB Output is correct
9 Correct 1140 ms 133904 KB Output is correct
10 Correct 1054 ms 133904 KB Output is correct
11 Correct 1222 ms 133972 KB Output is correct
12 Correct 1783 ms 133972 KB Output is correct
13 Correct 3222 ms 133972 KB Output is correct
14 Correct 3377 ms 133980 KB Output is correct
15 Correct 3568 ms 133980 KB Output is correct
16 Correct 3152 ms 133980 KB Output is correct
17 Correct 3545 ms 133980 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 8312 KB Output is correct
2 Correct 28 ms 8428 KB Output is correct
3 Correct 27 ms 8428 KB Output is correct
4 Correct 26 ms 8428 KB Output is correct
5 Correct 27 ms 8472 KB Output is correct
6 Correct 27 ms 8472 KB Output is correct
7 Correct 28 ms 8472 KB Output is correct
8 Correct 26 ms 8536 KB Output is correct
9 Correct 27 ms 8536 KB Output is correct
10 Correct 1193 ms 9164 KB Output is correct
11 Correct 937 ms 9164 KB Output is correct
12 Correct 561 ms 9164 KB Output is correct
13 Correct 1110 ms 9164 KB Output is correct
14 Correct 909 ms 9164 KB Output is correct
15 Correct 896 ms 9340 KB Output is correct
16 Correct 3405 ms 133768 KB Output is correct
17 Correct 3206 ms 133768 KB Output is correct
18 Correct 3255 ms 133904 KB Output is correct
19 Correct 3405 ms 133904 KB Output is correct
20 Correct 3453 ms 133904 KB Output is correct
21 Correct 3574 ms 133904 KB Output is correct
22 Correct 3527 ms 133904 KB Output is correct
23 Correct 3103 ms 133904 KB Output is correct
24 Correct 1140 ms 133904 KB Output is correct
25 Correct 1054 ms 133904 KB Output is correct
26 Correct 1222 ms 133972 KB Output is correct
27 Correct 1783 ms 133972 KB Output is correct
28 Correct 3222 ms 133972 KB Output is correct
29 Correct 3377 ms 133980 KB Output is correct
30 Correct 3568 ms 133980 KB Output is correct
31 Correct 3152 ms 133980 KB Output is correct
32 Correct 3545 ms 133980 KB Output is correct
33 Incorrect 833 ms 133980 KB Output isn't correct
34 Halted 0 ms 0 KB -