제출 #1167525

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

bitaro

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 200200;
const int SQ = sqrt(N) + 1;
vector<int> adj[N], rev[N];
set<pair<int, int>, greater<pair<int, int>>> s[N]; // (distance, index)
int dp[N], cut[N], no[N];
int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n, m, q;
    cin >> n >> m >> q;
    while (m--) {
        int u, v;
        cin >> u >> v;
        adj[v].push_back(u);
        rev[u].push_back(v);
    }
    for (int i = 1;i <= n;i++) {
        s[i].insert({ 0, i });
        for (auto& x : adj[i]) {
            for (auto& [d, idx] : s[x]) {
                s[i].insert({ d + 1,idx });
                if (s[i].size() > SQ) s[i].erase(--s[i].end());
            }
        }
    }
    while (q--) {
        int t, y;
        cin >> t >> y;
        for (int j = 1;j <= y;j++) {
            cin >> cut[j];
            no[cut[j]] = 1;
        }
        if (y < SQ) {
            int ans = -1;
            for (auto& [d, idx] : s[t]) {
                if (no[idx]) continue;
                ans = max(ans, d);
            }
            cout << ans << '\n';
        }
        else {
            int ans = -1;
            memset(dp, 0xc0, sizeof dp);
            dp[t] = 0;
            for (int i = t;i >= 1;i--) {
                for (auto& x : rev[i]) {
                    dp[i] = max(dp[i], dp[x] + 1);
                }
                if (!no[i])
                    ans = max(ans, dp[i]);
            }
            cout << ans << '\n';
        }
        for (int j = 1;j <= y;j++) {
            no[cut[j]] = 0;
        }
    }
    return 0;
}

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