Submission #388718

#	Time	Username	Problem	Language	Result	Execution time	Memory
388718		denkendoemeer	Bitaro’s Party (JOI18_bitaro)	C++14	100 / 100	1608 ms	73972 KiB

bitaro

#include<bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
using namespace std;
vector<int>g[200005];
vector<pair<int,int>>dp[200005];
pair<int,int>mp[200005];
int dp2[200005];
bool viz[200005];
int main()
{
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    int n,m,q;
    scanf("%d%d%d",&n,&m,&q);
    int i;
    for(i=0;i<m;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        x--;
        y--;
        g[y].push_back(x);
    }
    for(i=0;i<n;i++)
        dp[i].push_back(make_pair(0,i));
    for(i=0;i<n;i++)
        mp[i]=make_pair(-inf,-1);
    for(i=0;i<n;i++){
        for(auto it:g[i]){
            for(auto &it2:dp[it]){
                if (mp[it2.second].second!=i){
                    mp[it2.second]=make_pair(it2.first+1,i);
                }
                else{
                    mp[it2.second]=max(mp[it2.second],make_pair(it2.first+1,i));
                }
                viz[it2.second]=0;
            }
        }
        for(auto it:g[i]){
            for(auto &it2:dp[it]){
                if (viz[it2.second]==0){
                    dp[i].push_back(make_pair(mp[it2.second].first,it2.second));
                    viz[it2.second]=1;
                }
            }
        }
        sort(dp[i].begin(),dp[i].end(),greater<pair<int,int>>());
        while(dp[i].size()>40)
            dp[i].pop_back();
    }
    memset(viz,0,sizeof(viz));
    for(i=0;i<q;i++){
        int t,y;
        scanf("%d%d",&t,&y);
        t--;
        vector<int>v;
        int j;
        for(j=0;j<y;j++){
            int auxi;
            scanf("%d",&auxi);
            auxi--;
            v.push_back(auxi);
        }
        if (y<40){
            for(auto it:v)
                viz[it]=1;
            for(auto &it:dp[t]){
                if (viz[it.second]==0){
                    printf("%d\n",it.first);
                    goto flag;
                }
            }
            printf("-1\n");
            flag:;
            for(auto it:v)
                viz[it]=0;
        }
        else{
            fill(dp2,dp2+t+1,0);
            for(auto it:v)
                dp2[it]=-inf;
            for(j=0;j<t+1;j++){
                for(auto it:g[j])
                    dp2[j]=max(dp2[j],dp2[it]+1);
            }
            printf("%d\n",dp2[t]<0?-1:dp2[t]);
        }
    }
return 0;
}

Compilation message (stderr)

bitaro.cpp: In function 'int main()':
bitaro.cpp:15:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   15 |     scanf("%d%d%d",&n,&m,&q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
bitaro.cpp:19:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   19 |         scanf("%d%d",&x,&y);
      |         ~~~~~^~~~~~~~~~~~~~
bitaro.cpp:55:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   55 |         scanf("%d%d",&t,&y);
      |         ~~~~~^~~~~~~~~~~~~~
bitaro.cpp:61:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   61 |             scanf("%d",&auxi);
      |             ~~~~~^~~~~~~~~~~~

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