제출 #423226

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
423226		snasibov05	Bitaro’s Party (JOI18_bitaro)	C++14	100 / 100	1968 ms	323308 KiB

bitaro

#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 = 250;

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

void dfs(int v){

    for (auto to : ed[v]){
        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 = max(x.f, dist[x.s]); dist[x.s] = 0;
        }
        for (auto x : mx[to]){
            if (dist[x.s] == 0) continue;
            mx[v].pb({x.f+1, 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){
    if (busy[v]) dp[v] = -1;
    for (auto to : ed[v]){
        if (dp[to] == -1) continue;
        dp[v] = max(dp[v], dp[to] + 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);
    dist.resize(n+1);
    busy.resize(n+1);
    dp.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) {
        dfs(i);
    }

    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{
            dp.assign(n+1, 0);
            for (int j = 1; j <= t; ++j) {
                calc(j);
            }
            cout << dp[t] << "\n";
        }

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

    return 0;
}

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