Submission #1028770

#	Time	Username	Problem	Language	Result	Execution time	Memory
1028770		ngrace	Bitaro’s Party (JOI18_bitaro)	C++14	100 / 100	748 ms	148424 KiB

bitaro

#include <bits/stdc++.h>
using namespace std;
#define v vector
#define ii pair<int,int>
#define fi first
#define se second

const int SIZ = 100;

int main(){
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    int N,M,Q;
    cin>>N>>M>>Q;
    v<v<int>> adj(N);
    for(int i=0; i<M; i++){
        int s,e;
        cin>>s>>e;
        s--;
        e--;
        adj[e].push_back(s);
    }

    v<v<ii>> longest(N);
    v<int> used(N,-1);
    v<int> dists(N);
    for(int i=0; i<N; i++){
        for(int c:adj[i]){
            for(auto it:longest[c]){
                if(used[it.se]!=i) dists[it.se]=0;
                used[it.se]=i;
                dists[it.se] = max(dists[it.se], it.fi+1);
            }
        }
        longest[i].push_back({0, i});
        for(int c:adj[i]){
            for(auto it:longest[c]){
                if(used[it.se]==i){
                    used[it.se]=-1;
                    longest[i].push_back({dists[it.se], it.se});
                }
            }
        }
        sort(longest[i].rbegin(), longest[i].rend());
        while(longest[i].size()>SIZ+1) longest[i].pop_back();
    }

    v<int> Y(N,-1);
    for(int q=0; q<Q; q++){
        int t,y;
        cin>>t>>y;
        t--;
        for(int i=0; i<y; i++){
            int c;
            cin>>c;
            c--;
            Y[c] = q;
        }

        if(y<SIZ-2){
            bool done=false;
            for(ii it:longest[t]){
                if(Y[it.se]!=q){
                    cout<<it.fi<<endl;
                    done=true;
                    break;
                }
            }
            if(!done) cout<<-1<<endl;
        }
        else{
            v<int> dp(N,-1);
            dp[t] = 0;
            for(int i=t; i>=0; i--){
                if(dp[i]==-1) continue;
                for(int c:adj[i]) dp[c] = max(dp[c], dp[i]+1);
            }
            int out=-1;
            for(int i=0; i<=t; i++) if(Y[i]!=q) out = max(out, dp[i]);
            cout<<out<<endl;
        }
    }
}

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