제출 #423166

#제출 시각아이디문제언어결과실행 시간메모리
423166snasibov05Bitaro’s Party (JOI18_bitaro)C++14
0 / 100
4 ms844 KiB
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

#define pb push_back
#define pii pair<int, int>
#define f first
#define s second
#define oo 1000000000

const int b = 320;

vector<vector<int>> ed;
vector<vector<pii>> mx;
vector<bool> visited;
vector<int> dist;
vector<int> dp;

void dfs(int v){
    visited[v] = true;

    for (auto to : ed[v]){
        if (!visited[to]) dfs(to);
        for (auto x : mx[v]){
            dist[x.s] = x.f;
        }
        for (auto x : mx[to]) {
            dist[x.s] = max(dist[x.s], x.f + 1);
        }
        for (auto& x : mx[v]){
            x.f = dist[x.s]; dist[x.s] = 0;
        }
        for (auto x : mx[to]){
            if (dist[x.s] == 0) continue;
            mx[v].pb({dist[x.s], x.s}); dist[x.s] = 0;
        }
    }

    sort(mx[v].rbegin(), mx[v].rend());
    while (mx[v].size() > b) mx[v].pop_back();
    if (mx[v].size() < b) mx[v].pb({0, v});
}

void calc(int v, vector<bool>& busy){
    visited[v] = true;
    if (busy[v]) dp[v] = -oo;
    for (auto x : ed[v]){
        if (!visited[x]) calc(x, busy);
        if (busy[v]) continue;
        dp[v] = max(dp[v], dp[x] + 1);
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m, q; cin >> n >> m >> q;
    ed.resize(n+1);
    mx.resize(n+1);
    visited.resize(n+1);
    dist.resize(n+1);
    for (int i = 0; i < m; ++i) {
        int u, v; cin >> u >> v;
        ed[v].pb(u);
    }

    for (int i = 1; i <= n; ++i) {
        if (!visited[i]) dfs(i);
    }

    vector<bool> busy(n+1);

    for (int i = 0; i < q; ++i) {
        int t, y; cin >> t >> y;
        vector<int> cur(y);
        for (int j = 0; j < y; ++j) {
             cin >> cur[j];
             busy[cur[j]] = true;
        }

        if (y < b){
            int ans = -1;
            for (auto x : mx[t]){
                //cout << x.f << " " << x.s << "\n";
                if (!busy[x.s]) {
                    ans = x.f;
                    break;
                }
            }
            cout << ans << "\n";
        } else{
            visited.assign(n+1, false);
            dp.assign(n+1, 0);
            for (int j = 1; j <= n; ++j) {
                if (!visited[j]) calc(j, busy);
            }
            if (dp[t] < 0) dp[t] = -1;
            cout << dp[t] << "\n";
        }

        for (auto x : cur) busy[x] = false;
    }

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...