Submission #602723

#	Time	Username	Problem	Language	Result	Execution time	Memory
602723		elkernos	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	1145 ms	331152 KiB

bitaro

#include <bits/stdc++.h>

using namespace std;

int32_t main()
{
    cin.tie(0)->sync_with_stdio(0);
    int n, m, q;
    cin >> n >> m >> q;
    vector<vector<int>> g(n + 1), gr(n + 1);
    for(int i = 1; i <= m; i++) {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        gr[b].push_back(a);
    }
    const int sz = 250;
#define T vector<pair<int, int>>
    vector<bool> used(n + 1);
    auto merge = [&](T a, T b) {
        T ret;
        int j = 0;
        for(int i = 0; i < (int)b.size(); i++) {
            b[i].first++;
            while(j < (int)a.size() && a[j].first >= b[i].first) {
                if(used[a[j].second]) {
                    j++;
                    continue;
                }
                used[a[j].second] = 1;
                ret.push_back(a[j++]);
            }
            if(used[b[i].second]) {
                continue;
            }
            used[b[i].second] = 1;
            ret.push_back(b[i]);
        }
        while(j < (int)a.size()) {
            if(used[a[j].second]) {
                j++;
                continue;
            }
            used[a[j].second] = 1;
            ret.push_back(a[j++]);
        }
        for(int i = 0; i < (int)ret.size(); i++) {
            used[ret[i].second] = 0;
        }
        while((int)ret.size() > sz) {
            ret.pop_back();
        }
        return ret;
    };
    vector<T> cand(n + 1);
    for(int i = 1; i <= n; i++) {
        cand[i].push_back({0, i});
        for(int from : gr[i]) {
            cand[i] = merge(cand[i], cand[from]);
        }
    }
    const int oo = 1e9;
    for(int i = 1; i <= q; i++) {
        int v, k;
        cin >> v >> k;
        vector<int> cant(k + 1);
        for(int j = 1; j <= k; j++) {
            cin >> cant[j];
            used[cant[j]] = 1;
        }
        int ans = -1;
        if(k >= sz) {
            vector<int> dp(n + 1, -oo);
            dp[v] = 0;
            for(int j = v; j >= 1; j--) {
                for(int to : g[j]) {
                    dp[j] = max(dp[j], dp[to] + 1);
                }
                if(!used[j]) {
                    ans = max(ans, dp[j]);
                }
            }
        }
        else {
            for(int j = 0; j < (int)cand[v].size(); j++) {
                if(!used[cand[v][j].second]) {
                    ans = cand[v][j].first;
                    break;
                }
            }
        }
        cout << ans << '\n';
        for(int j = 1; j <= k; j++) {
            used[cant[j]] = 0;
        }
    }
}

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