제출 #1359248

#제출 시각아이디문제언어결과실행 시간메모리
1359248njoopBitaro’s Party (JOI18_bitaro)C++20
100 / 100
768 ms149960 KiB
#include <bits/stdc++.h>

using namespace std;

vector<vector<int>> g, rg;
vector<vector<pair<int, int>>> path;
vector<int> dp, mark;
int n, m, q;

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> m >> q;
    g.assign(n+2, vector<int>());
    rg.assign(n+2, vector<int>());
    path.assign(n+2, vector<pair<int, int>>());
    mark.assign(n+2, -1);
    while(m--) {
        int u, v;
        cin >> u >> v;
        if(u > v) swap(u, v);
        g[u].push_back(v);
        rg[v].push_back(u);
    }
    for(int i=1; i<=n; i++) {
        path[i].push_back({0, i});
        vector<int> idx;
        mark[i] = 0;
        idx.push_back(i);
        for(auto j: rg[i]) {
            for(auto k: path[j]) {
                if(mark[k.second] == -1) idx.push_back(k.second);
                mark[k.second] = max(mark[k.second], k.first+1);
            }
        }
        for(auto j: idx) {
            path[i].push_back({mark[j], j});
        }
        sort(path[i].begin(), path[i].end(), greater<pair<int, int>>());
        while(path[i].size() > 100) {
            path[i].pop_back();
        }
        for(auto i: idx) {
            mark[i] = -1;
        }
    }
    mark.assign(n+2, -1);
    while(q--) {
        int t, y;
        set<int> blk;
        cin >> t >> y;
        for(int i=1; i<=y; i++) {
            int in;
            cin >> in;
            mark[in] = 1;
            blk.insert(in);
        }
        if(y >= 100) {
            dp.assign(n+2, -1);
            for(int i=1; i<=t; i++) {
                if(mark[i] == -1) dp[i] = max(dp[i], 0);
                if(dp[i] == -1) continue;
                for(auto j: g[i]) {
                    dp[j] = max(dp[j], dp[i]+1);
                }
            }
            cout << dp[t] << "\n";
        } else {
            vector<pair<int, int>> v = path[t];
            int ans = -1;
            for(auto i: v) {
                if(mark[i.second] == -1) {
                    ans = max(ans, i.first);
                }
            }
            cout << ans << "\n";
        }
        for(auto i: blk) mark[i] = -1;
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...