Submission #82919

#	Time	Username	Problem	Language	Result	Execution time	Memory
82919		Bodo171	Bitaro’s Party (JOI18_bitaro)	C++14	100 / 100	1545 ms	286672 KiB

bitaro

#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
const int nmax=100005;
typedef pair<int,int> P;
vector<int> v[nmax];
P l[nmax][350],all[1000];
int viz[nmax],block[nmax],rep[nmax],nr[nmax],dp[nmax],ap[nmax];
int N,n,m,q,i,j,k,a,b,x,nod,p,spec;
bool comp(P unu,P doi)
{
    return unu.first>doi.first;
}
void dfs(int x)
{
    viz[x]=1;
    for(int i=0;i<v[x].size();i++)
      if(!viz[v[x][i]])
        dfs(v[x][i]);
    rep[++N]=x;
}
int cat,merges;
void mrg(int a,int b)
{
    ++merges;
    merge(l[a]+1,l[a]+nr[a]+1,l[b]+1,l[b]+nr[b]+1,all+1,comp);
    cat=nr[a]+nr[b];nr[a]=0;
    for(int it=1;it<=cat&&nr[a]<=k;it++)
    {
        if(ap[all[it].second]!=merges)
        {
            l[a][++nr[a]]=all[it];
            ap[all[it].second]=merges;
        }
    }
}
int main()
{
    //freopen("data.in","r",stdin);
    ios_base::sync_with_stdio(false);
    cin>>n>>m>>q;
    for(k=1;k*k<=n;k++);
    for(i=1;i<=m;i++)
    {
        cin>>a>>b;
        v[a].push_back(b);
    }
    for(int id=1;id<=n;id++)
        if(!viz[id])
          dfs(id);
    for(int id=N;id>=1;id--)
    {
        x=rep[id];
        for(int i=1;i<=nr[x];i++)
            l[x][i].first++;
        if(nr[x]<=k) l[x][++nr[x]]={1,x};
        for(int i=0;i<v[x].size();i++)
            mrg(v[x][i],x);
    }
    for(int cnt=1;cnt<=q;cnt++)
    {
        cin>>spec>>N;
        for(int i=1;i<=N;i++)
        {
            cin>>x;
            block[x]=cnt;
        }
        if(N<=k)
        {
            p=1;
            while(block[l[spec][p].second]==cnt)
                p++;
            cout<<l[spec][p].first-1<<'\n';
        }
        else
        {
            for(i=1;i<=n;i++)
                if(block[i]==cnt) dp[i]=0;
                else dp[i]=1;
            for(int id=n; id>=1; id--)
            {
                x=rep[id];
                if(dp[x])
                for(int i=0; i<v[x].size(); i++)
                    dp[v[x][i]]=max(dp[v[x][i]],dp[x]+1);
            }
            cout<<dp[spec]-1<<'\n';
        }
    }
    return 0;
}

Compilation message (stderr)

bitaro.cpp: In function 'void dfs(int)':
bitaro.cpp:19:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<v[x].size();i++)
                 ~^~~~~~~~~~~~
bitaro.cpp: In function 'int main()':
bitaro.cpp:59:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0;i<v[x].size();i++)
                     ~^~~~~~~~~~~~
bitaro.cpp:86:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for(int i=0; i<v[x].size(); i++)
                              ~^~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 7 / 7
• Subtask 3: 86 / 86