Submission #547382

#	Time	Username	Problem	Language	Result	Execution time	Memory
547382		krit3379	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	1450 ms	414540 KiB

bitaro

#include<bits/stdc++.h>
using namespace std;
#define N 100005
#define K 333

int ma[N],c[N],dpp[N],ans;
vector<int> g[N],v;
vector<pair<int,int>> dp[N];
bitset<N> vis;

int main(){
    int n,m,q,i,j,a,b,t,y;
    scanf("%d %d %d",&n,&m,&q);
    for(i=1;i<=m;i++){
        scanf("%d %d",&a,&b);
        g[b].push_back(a);
    }
    for(i=1;i<=n;i++){
        v.push_back(i);
        for(auto x:g[i]){
            for(auto [val,idx]:dp[x]){
                if(!ma[idx])v.push_back(idx);
                ma[idx]=max(ma[idx],val+1);
            }
        }
        sort(v.begin(),v.end(),[&ma](int a,int b){return ma[a]>ma[b];});
        for(j=0;j<min((int)v.size(),K);j++)dp[i].push_back({ma[v[j]],v[j]});
        for(auto x:v)ma[x]=0;
        v.clear();
    }
    while(q--){
        scanf("%d %d",&t,&y);
        for(i=1;i<=y;i++)scanf("%d",&c[i]),vis[c[i]]=true;
        ans=-1;
        if(y>=K){
            for(i=1;i<=t;i++){
                dpp[i]=vis[i]?-1e9:0;
                for(auto x:g[i])dpp[i]=max(dpp[i],dpp[x]+1);
            }
            ans=max(ans,dpp[t]);
        }
        else for(auto [val,idx]:dp[t])if(!vis[idx])ans=max(ans,val);
        printf("%d\n",ans);
        for(i=1;i<=y;i++)vis[c[i]]=false;
    }
    return 0;
}

Compilation message (stderr)

bitaro.cpp: In function 'int main()':
bitaro.cpp:26:34: warning: capture of variable 'ma' with non-automatic storage duration
   26 |         sort(v.begin(),v.end(),[&ma](int a,int b){return ma[a]>ma[b];});
      |                                  ^~
bitaro.cpp:6:5: note: 'int ma [100005]' declared here
    6 | int ma[N],c[N],dpp[N],ans;
      |     ^~
bitaro.cpp:13:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |     scanf("%d %d %d",&n,&m,&q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~
bitaro.cpp:15:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |         scanf("%d %d",&a,&b);
      |         ~~~~~^~~~~~~~~~~~~~~
bitaro.cpp:32:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |         scanf("%d %d",&t,&y);
      |         ~~~~~^~~~~~~~~~~~~~~
bitaro.cpp:33:31: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |         for(i=1;i<=y;i++)scanf("%d",&c[i]),vis[c[i]]=true;
      |                          ~~~~~^~~~~~~~~~~~

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