Submission #1219701

#	Time	Username	Problem	Language	Result	Execution time	Memory
1219701		onbert	Bitaro’s Party (JOI18_bitaro)	C++20	7 / 100	2051 ms	224344 KiB

bitaro

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5, sq = 150, INF = 1e9;
int n, m;
vector<int> adj[maxn], radj[maxn];

bool on[maxn];

vector<int> solve() {
    int left[n+1];
    queue<int> q;
    vector<int> ans(n+1);
    for (int i=1;i<=n;i++) {
        left[i] = adj[i].size();
        if (!left[i]) q.push(i);
    }
    while (q.size()) {
        int u = q.front();
        q.pop();
        if (on[u]) ans[u] = 0;
        else ans[u] = -1;
        for (int v:adj[u]) if (ans[v] != -1) ans[u] = max(ans[v] + 1, ans[u]);
        for (int v:radj[u]) {
            left[v]--;
            if (!left[v]) q.push(v);
        }
    }
    return ans;
}

vector<int> ori_ans;

vector<pair<int,int>> vec[maxn];
int mn[maxn];

bool cmp(pair<int,int> x, pair<int,int> y) {
    if (mn[x.first] != mn[y.first]) return mn[x.first] < mn[y.first];
    else return x < y;
}

void pre() {
    int left[n+1];
    queue<int> q;
    for (int i=1;i<=n;i++) {
        left[i] = adj[i].size();
        if (!left[i]) q.push(i);
    }
    while (q.size()) {
        int u = q.front();
        q.pop();
        vec[u].push_back({u, 0});
        mn[u] = ori_ans[u] + 1;
        for (int v:adj[u]) for (auto [x, y]:vec[v]) mn[x] = INF;
        int sz = adj[u].size();
        for (int v:adj[u]) {
            for (auto [x, y]:vec[v]) {
                mn[x] = min(ori_ans[u] - ori_ans[v] - 1 + y, mn[x]);
                vec[u].push_back({x, 0});
            }
        }
        sort(vec[u].begin(), vec[u].end(), cmp);
        vec[u].erase(unique(vec[u].begin(), vec[u].end()), vec[u].end());
        while (vec[u].size() > sq) vec[u].pop_back();
        for (auto &[x, y]:vec[u]) y = mn[x];

        for (int v:radj[u]) {
            left[v]--;
            if (!left[v]) q.push(v);
        }
    }
}

signed main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int q;
    cin >> n >> m >> q;
    for (int i=1;i<=m;i++) {
        int u, v;
        cin >> u >> v;
        radj[u].push_back(v); adj[v].push_back(u);
    }
    for (int i=1;i<=n;i++) on[i] = true;
    ori_ans = solve();
    pre();

    while (q--) {
        int u, sz;
        cin >> u >> sz;
        if (!sz) {
            cout << ori_ans[u] << "\n";
            continue;
        }
        vector<int> off(sz);
        for (int &i:off) {
            cin >> i;
            on[i] = false;
        }
        if (sz >= sq) cout << solve()[u] << "\n";
        else {
            // cout << u << endl;
            bool flag = true;
            for (auto [x, y]:vec[u]) {
                // cout << x << " " << y << endl;
                if (on[x]) {
                    cout << ori_ans[u] - y + 1 << "\n";
                    flag = false;
                    break;
                }
            }
            if (flag) cout << "-1\n";
        }
        for (int i:off) on[i] = true;
    }
}

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