Submission #1126478

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126478		KK_1729	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	709 ms	143760 KiB

bitaro

#include <bits/stdc++.h>
using namespace std;

// #define int long long 
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define pb push_back 
#define all(a) a.begin(), a.end()
#define endl "\n"

void printVector(vector<int> a){
    for (auto x: a) cout << x << " ";
    cout << endl;
}

void solve(){
    int n, m, q; cin >> n >> m >> q;
    vector<vector<int>> graph(n+1);


    FOR(i,0,m){
        int s, e; cin >> s >> e;
        graph[e].pb(s);
    }

    vector<vector<pair<int, int>>> path_sizes(n+1);
    vector<int> from(n+1, -1);

    for (int i = 1; i <= n; ++i){
        path_sizes[i].pb({0, i});
        vector<int> ind;

        for (auto x: graph[i]){
            for (auto [dist, node]: path_sizes[x]){
                if (from[node] == -1){
                    ind.pb(node);
                    from[node] = dist+1;
                }else{
                    from[node] = max(from[node], dist+1);
                }
            }
        }

        for (auto x: ind){
            path_sizes[i].pb({from[x], x});
        }

        sort(all(path_sizes[i]));
        reverse(all(path_sizes[i]));
        
        while (path_sizes[i].size() > 100){
            path_sizes[i].pop_back();
        }

        for (auto x: ind) from[x] = -1;
    }

    vector<int> blocked(n+1);

    while (q--){
        int t, y; cin >> t >> y;

        vector<int> c(y);
        FOR(i,0,y){
            cin >> c[i];
            blocked[c[i]] = 1;
        }

        int ans = -1;
        if (y >= 100){
            vector<int> dp(t+1, -1);
            dp[t] = 0;
            
            for (int i = t; i >= 0; i--){
                if (dp[i] == -1) continue;
                if (!blocked[i]) ans = max(ans, dp[i]);
                for (auto x: graph[i]) dp[x] = max(dp[x], dp[i]+1);
            }
        }else{

            for (auto [dist, node]: path_sizes[t]){
                if (!blocked[node]){
                    ans = dist;
                    break;
                }
            }
        }
        cout << ans << endl;
        for (auto x: c) blocked[x] = 0;
    }

}
int32_t main(){
    ios::sync_with_stdio(false);cin.tie(nullptr);
    int t = 1;// cin >> t;
    while (t--) solve();
}

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