Submission #1219739

#	Time	Username	Problem	Language	Result	Execution time	Memory
1219739		onbert	Bitaro’s Party (JOI18_bitaro)	C++20	0 / 100	8 ms	8008 KiB

bitaro

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5, sq = 320, INF = 1e6;
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];
int cnt[maxn];

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();
        for (int v:radj[u]) {
            left[v]--;
            if (!left[v]) q.push(v);
        }

        int sz = adj[u].size();
        if (sz == 0) {
            vec[u] = {{ori_ans[u] + 1, u}};
            continue;
        }

        for (int v:adj[u]) for (auto [y, x]:vec[v]) mn[x] = INF;
        for (int v:adj[u]) for (auto [y, x]:vec[v]) {
            mn[x] = min(ori_ans[u] - ori_ans[v] - 1 + y, mn[x]);
        }

        int pt[sz];
        for (int i=0;i<sz;i++) pt[i] = -1;
        int l[sz], r[sz];
        for (int i=0;i<sz;i++) l[i] = i-1, r[i] = i+1;
        int start = 0;
        for (int i=1;i<=ori_ans[u] + 1;i++) {
            int j = start;
            while (j != sz) {
                int v = adj[u][j], jsz = vec[v].size();
                while (pt[j] + 1 < jsz && mn[vec[v][pt[j]+1].second] <= i) {
                    pt[j]++;
                    int x = vec[v][pt[j]].second;
                    if (cnt[x] == u) continue;
                    cnt[x] = u;
                    vec[u].push_back({i, x});
                    if (vec[u].size() == sq) break;
                }
                if (vec[u].size() == sq) break;
                if (pt[j] == jsz-1) {
                    r[l[j]] = r[j], l[r[j]] = l[j];
                    if (j == start) start = r[j];
                }
                j = r[j];
            }
            if (vec[u].size() == sq) break;
        }
        if (vec[u].size() < sq) vec[u].push_back({ori_ans[u] + 1, u});
    }
}

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();

    // for (int i=1;i<=n;i++) {
    //     for (auto [x, y]:vec[i]) cout << x << "." << y << " "; cout << endl;
    // }

    for (int i=1;i<=n;i++) {
        int last = 0;
        for (auto [y, x]:vec[i]) {
            if (y != last) {
                last = y;
                assert(solve()[i] == ori_ans[i] - y + 1);
            }
            on[x] = false;
        }
        for (auto [y, x]:vec[i]) on[x] = true;
    }

    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 [y, x]: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: 0 / 7
• Subtask 2: 0 / 7
• Subtask 3: 0 / 86