제출 #1219654

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1219654		onbert	Bitaro’s Party (JOI18_bitaro)	C++20	7 / 100	1626 ms	589824 KiB

bitaro

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 1e5 + 5, sq = 320, 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();
        ans[u] = 0;
        for (int v:adj[u]) if (on[v] || ans[v]) 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) {
    return mn[x.first] < mn[y.first];
}

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

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

    while (q--) {
        int u, sz;
        cin >> u >> sz;
        vector<int> off(sz);
        for (int &i:off) {
            cin >> i;
            on[i] = false;
        }
        if (sz >= sq) {
            int ret = solve()[u];
            if (!ret && !on[u]) cout << "-1\n";
            else cout << ret << "\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