Submission #227440

#	Time	Username	Problem	Language	Result	Execution time	Memory
227440		MKopchev	Bitaro’s Party (JOI18_bitaro)	C++14	100 / 100	1708 ms	120184 KiB

bitaro

#include<bits/stdc++.h>
using namespace std;

const int nmax=1e5+42,CUT=100;

vector<int> adj[nmax],bck[nmax];

int n,m,q;

int sz,where;

int blocked[nmax];

bool is_blocked[nmax];

int dp[nmax];

int slow()
{
    for(int i=1;i<=n;i++)
        dp[i]=-1e9;

    dp[where]=0;

    for(int i=where-1;i>=1;i--)
    {
        for(auto k:adj[i])
            dp[i]=max(dp[i],dp[k]+1);
    }

    int mx=-1;
    for(int i=where;i>=1;i--)
        if(is_blocked[i]==0)mx=max(mx,dp[i]);

    return mx;
}

vector< pair<int/*distance*/,int/*start*/> > best[nmax];

int main()
{
    scanf("%i%i%i",&n,&m,&q);

    for(int i=1;i<=m;i++)
    {
        int u,v;
        scanf("%i%i",&u,&v);
        adj[u].push_back(v);
        bck[v].push_back(u);
    }

    vector< pair<int/*distance*/,int/*start*/> > help={};

    for(int i=1;i<=n;i++)
    {
        help={};

        for(auto node_back:bck[i])
            for(auto k:best[node_back])
            help.push_back({k.first+1,k.second});

        help.push_back({0,i});

        sort(help.begin(),help.end());

        reverse(help.begin(),help.end());

        for(auto k:help)
        {
            if(is_blocked[k.second]==0)
            {
                is_blocked[k.second]=1;
                best[i].push_back(k);

                if(best[i].size()==CUT)break;
            }
        }

        for(auto k:best[i])
            is_blocked[k.second]=0;
    }
    for(int i=1;i<=q;i++)
    {
        scanf("%i%i",&where,&sz);
        for(int j=1;j<=sz;j++)
        {
            scanf("%i",&blocked[j]);
            is_blocked[blocked[j]]=1;
        }

        if(sz>=CUT)printf("%i\n",slow());
        else
        {
            int mx=-1;
            for(auto k:best[where])
                if(is_blocked[k.second]==0)mx=max(mx,k.first);
            printf("%i\n",mx);
        }
        for(int j=1;j<=sz;j++)
        {
            is_blocked[blocked[j]]=0;
        }
    }
    return 0;
}

Compilation message (stderr)

bitaro.cpp: In function 'int main()':
bitaro.cpp:42:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%i%i%i",&n,&m,&q);
     ~~~~~^~~~~~~~~~~~~~~~~~~
bitaro.cpp:47:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%i%i",&u,&v);
         ~~~~~^~~~~~~~~~~~~~
bitaro.cpp:84:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%i%i",&where,&sz);
         ~~~~~^~~~~~~~~~~~~~~~~~~
bitaro.cpp:87:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%i",&blocked[j]);
             ~~~~~^~~~~~~~~~~~~~~~~~

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