Submission #1316659

#TimeUsernameProblemLanguageResultExecution timeMemory
1316659aaaaaaaaBitaro’s Party (JOI18_bitaro)C++20
0 / 100
4 ms824 KiB
#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
const int inf = -1;
const int binf = -1e9;
const int mxN = 2e5 + 100;
const int mxB = 343;
vector<pair<int, int>> path[mxN];
vector<int> adj[mxN], 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, inf), vis(n + 1, 0), dp(n + 1, binf);
    for(int i = 0, u, v; i < m; ++i){
        cin >> u >> v; --u, --v;
        adj[u].push_back(v);
        radj[v].push_back(u);
    }
    auto dfs = [&](auto &self, int u) -> int {
        if(vis[u]) return -1e9;
        if(dp[u] != binf) return 0;
        int ans = 0;
        for(auto it : radj[u]){
            ans = max(ans, self(self, it) + 1);
        }
        return dp[u] = ans;
    };
    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] == inf){
                    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;
        while(y--){
            int u;
            cin >> u;
            --u;
            vis[u] = 1;
            ban.push_back(u);
        }
        if(1){
            for(int j = 1; j <= n; ++j) dp[j] = binf;
            int ans = dfs(dfs, x);
            cout << max(ans, -1) << "\n";
        }else{
            int ans = inf;
            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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...