Submission #928004

#	Time	Username	Problem	Language	Result	Execution time	Memory
928004		Aiperiii	Bitaro’s Party (JOI18_bitaro)	C++14	7 / 100	1543 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;
int cnt[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 < pair <int,int> > cct[n+1];
    vector <int> d(n+1),ld(n+1);
    
    for(int i=1;i<=n;i++){
        d[i]=0;
        vector <int> cctv;
        cctv.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{
                    cctv.pb(x.ss);
                    ld[x.ss]=i;
                    d[x.ss]=x.ff+1;
                }
            }
        }
        for(auto x : cctv){
            cct[i].pb({d[x],x});
        }
        sort(all(cct[i]));
        reverse(all(cct[i]));
        while(cct[i].size()>sq)cct[i].pop_back();
    }
    vector <int> no(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;
        }
        if(s<sq){
            int ans=-1;
            for(auto x : cct[t]){
                if(!no[x.ss]){
                    ans=x.ff;
                    break;
                }
            }
            cout<<ans<<"\n";
        }
        else{
            vector <int> dp(n+1);
            for(int i=0;i<s;i++){
                dp[a[i]]=-1e9;
            }
            for(int i=1;i<=n;i++){
                for(auto edg : g[i]){
                    dp[i]=max(dp[i],dp[edg]+1);
                }
            }
            /*for(int i=1;i<=n;i++){
                cout<<dp[i]<<" ";
            }*/
            cout<<max(-1ll,dp[t])<<"\n";
        }
        for(int i=0;i<s;i++){
            no[a[i]]=0;
        }
    }
}
/*

 */

Compilation message (stderr)

bitaro.cpp: In function 'int main()':
bitaro.cpp:44: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]
   44 |         while(cct[i].size()>sq)cct[i].pop_back();
      |               ~~~~~~~~~~~~~^~~

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