Submission #928329

#	Time	Username	Problem	Language	Result	Execution time	Memory
928329		Aiperiii	Bitaro’s Party (JOI18_bitaro)	C++14	7 / 100	1882 ms	524288 KiB

bitaro

#include <bits/stdc++.h>
#define int long long
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
#define pb push_back
using namespace std;
const int N=1e5+5;
vector <pair <int,int> > cct[N];
vector <int> g[N];
signed main(){
    
    int n,m,q;
    cin>>n>>m>>q;
    for(int i=0;i<m;i++){
        int u,v;
        cin>>u>>v;
        g[v].pb(u);
    }
    int sq=sqrt(n);
    vector <int> d(n+1),ld(n+1),can;
    for(int i=1;i<=n;i++){
        d[i]=0;
        can.pb(i);
        for(auto edg : g[i]){
            for(auto x : cct[edg]){
                if(ld[x.ss]==i){
                    d[x.ss]=max(d[x.ss],x.ff+1);
                }
                else{
                    d[x.ss]=x.ff+1;
                    ld[x.ss]=i;
                    can.pb(x.ss);
                }
            }
        }
        for(auto x : can){
            cct[i].pb({d[x],x});
        }
        sort(cct[i].rbegin(),cct[i].rend());
        while(cct[i].size()>sq)cct[i].pop_back();
        /*cout<<i<<"\n";
        for(auto x :cct[i])cout<<x.ff<<" "<<x.ss<<"\n";
        cout<<"\n";*/
        can.clear();
    }
    
    vector <int> no(n+1),dp(n+1);
    while(q--){
        int t,s;
        cin>>t>>s;
        vector <int> a(s);
        for(int i=0;i<s;i++){
            cin>>a[i];
            no[a[i]]=1;
            dp[a[i]]=-1e9;
        }
        int ans=-1;
        if(s<sq){
            for(auto x : cct[t]){
                if(!no[x.ss]){
                    ans=x.ff;
                    break;
                }
            }
        }
        else{
            for(int i=1;i<=t;i++){
                for(auto edg : g[i]){
                    dp[i]=max(dp[i],dp[edg]+1);
                }
                
            }
            ans=max(ans,dp[t]);
            for(int i=1;i<=t;i++){
                dp[i]=0;
            }
            
        }
        cout<<ans<<"\n";
        for(int i=0;i<s;i++){
            no[a[i]]=0;
            dp[a[i]]=0;
        }
    }
}
/*

 */

Compilation message (stderr)

bitaro.cpp: In function 'int main()':
bitaro.cpp:41:28: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   41 |         while(cct[i].size()>sq)cct[i].pop_back();
      |               ~~~~~~~~~~~~~^~~

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