제출 #1245339

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1245339		enjeeeff	Bitaro’s Party (JOI18_bitaro)	C++20	14 / 100	2105 ms	413408 KiB

bitaro

#include<bits/stdc++.h>

typedef long long ll;
#define vec vector
using namespace std;

const ll bl = 200;

int main() {
    ll n, m, q;
    cin >> n >> m >> q;

    ll i;
    vec<vec<long long> > rev(n + 1);
    vec<vec<pair<ll, ll> > > topPaths(n + 1);

    for (i = 0; i < m; i++) {
        ll a, b;
        cin >> a >> b;
        rev[b].push_back(a);
    }

    ll j;
    vec<ll> busyWhole(n + 1);
    vec<ll> busyList;
    for (i = 1; i <= n; i++) {
        priority_queue<tuple<ll, ll, ll>, vec<tuple<ll, ll, ll> > > qu;
        for (j = 0; j < rev[i].size(); j++)
            qu.emplace(topPaths[rev[i][j]][0].first, j, 0);
        while (qu.size() && topPaths[i].size() < bl) {
            auto [length, id, ord] = qu.top();
            auto &revTops = topPaths[rev[i][id]];
            qu.pop();
            if (!busyWhole[revTops[ord].second]) {
                busyList.push_back(revTops[ord].second);
                busyWhole[revTops[ord].second] = 1;
                topPaths[i].emplace_back(length + 1, revTops[ord].second);
            }
            if (ord + 1 < revTops.size())
                qu.emplace(revTops[ord + 1].first, id, ord + 1);
        }
        topPaths[i].push_back({0, i});
        for (auto &el : busyList)
            busyWhole[el] = 0;
        busyList.clear();
    }
    
    while (q--) {
        ll t, y;
        cin >> t >> y;
        
        for (i = 0; i < y; i++) {
            ll b;
            cin >> b;
            busyList.push_back(b);
            busyWhole[b] = 1;
        }
        if (t >= bl) {
            vec<ll> dp(n + 1, -1);
            for (i = 1; i <= n; i++) {
                if (!busyWhole[i]) dp[i] = 0;
                for (auto &a : rev[i])
                    if (dp[a] != -1) dp[i] = max(dp[i], dp[a] + 1);
            }
            cout << dp[t] << '\n';
        }
        else {
            for (i = 0; i < topPaths[t].size() && busyWhole[topPaths[t][i].second]; i++);
            cout << (i < topPaths[t].size() ? topPaths[t][i].first : -1) << '\n';
        }
        for (auto &el : busyList)
            busyWhole[el] = 0;
        busyList.clear();
    }
}

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