Submission #1316679

#	Time	Username	Problem	Language	Result	Execution time	Memory
1316679		aaaaaaaa	Bitaro’s Party (JOI18_bitaro)	C++20	7 / 100	1053 ms	589824 KiB

bitaro

#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
const int mxN = 1e5 + 2;
const int mxB = 1000;
vector<pair<int, int>> path[mxN];
vector<int> radj[mxN];
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(nullptr); cout.tie(nullptr);
    int n, m, q;
    cin >> n >> m >> q;
    vector<int> mn(n + 1, -1), vis(n + 1, 0), dp(n + 1, -1);
    for(int i = 0, u, v; i < m; ++i){
        cin >> u >> v; --u, --v;
        radj[v].push_back(u);
    }
    for(int i = 0; i < n; ++i){
        path[i].push_back({i, 0});
        vector<int> all_node;
        for(auto it : radj[i]){
            for(auto [v, w] : path[it]){
                if(mn[v] == -1){
                    all_node.push_back(v);
                    mn[v] = w + 1;
                }else if(mn[v] < w + 1){
                    mn[v] = w + 1;
                }
            }
        }
        for(auto it : all_node){
            path[i].push_back({it, mn[it]});
        }
        sort(all(path[i]), [&](pair<int, int> p1, pair<int, int> p2){
            return p1.second > p2.second;
        });
        while(path[i].size() > mxB) path[i].pop_back();
        for(auto it : all_node) mn[it] = -1;
    }
    while(q--){
        int x, y;
        cin >> x >> y;
        --x;
        vector<int> ban;
        for(int j = 0; j < n; ++j) vis[j] = 0;
        while(y--){
            int u;
            cin >> u;
            --u;
            vis[u] = 1;
            ban.push_back(u);
        }
        if((int) ban.size() >= (int) path[x].size()){
            priority_queue<pair<int, int>> pq;
            int ans = -1;
            pq.push({0, x}), dp[x] = 0;
            while(pq.size()){
                auto [w, u] = pq.top();
                pq.pop();
                for(auto it : radj[u]){
                    if(dp[it] < w + 1){
                        dp[it] = w + 1;
                        pq.push({dp[it], it});
                    }
                }
            }
            for(int j = 0; j <= x; ++j){
                if(!vis[j]) ans = max(ans, dp[j]);
                dp[j] = -1;
            }
            cout << ans << "\n";
        }else{
            int ans = -1;
            for(auto [u, w] : path[x]){
                if(vis[u] == 0){
                    ans = max(ans, w);
                }
            }
            cout << ans << "\n";
        }
        for(auto it : ban) vis[it] = 0;
    }
    return 0;
}

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