Submission #75012

#	Time	Username	Problem	Language	Result	Execution time	Memory
75012		faustaadp	늑대인간 (IOI18_werewolf)	C++17	49 / 100	3574 ms	133980 KiB

werewolf

#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 (stderr)

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 / 7
• Subtask 2: 8 / 8
• Subtask 3: 34 / 34
• Subtask 4: 0 / 51