Submission #1245389

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245389		enjeeeff	Bitaro’s Party (JOI18_bitaro)	C++20	14 / 100	2106 ms	413252 KiB

bitaro

#include<bits/stdc++.h>

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

const ll bl = 250;
const ll maxn = 1e5 + 1;
const ll maxm = 2e5 + 1;

ll dp[maxn];
ll busyWhole[maxn];
vec<ll> rev[maxn];
vec<pair<ll, ll> > topPaths[maxn];
ll pr[maxm];

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

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

    ll j;
    vec<ll> busyList;
    for (i = 1; i <= n; i++) {
        priority_queue<pair<ll, ll>, vec<pair<ll, ll> > > qu;
        fill_n(begin(pr), rev[i].size(), 0);
        for (j = 0; j < rev[i].size(); j++)
            qu.emplace(topPaths[rev[i][j]][0].first, j);
        while (qu.size() && topPaths[i].size() < bl) {
            auto [length, id] = qu.top();
            auto &revTop = topPaths[rev[i][id]][pr[id]].second;
            qu.pop();
            if (!busyWhole[revTop]) {
                busyList.push_back(revTop);
                busyWhole[revTop] = 1;
                topPaths[i].emplace_back(length + 1, revTop);
            }
            do pr[id]++; while (pr[id] < topPaths[rev[i][id]].size() && busyWhole[topPaths[rev[i][id]][pr[id]].second]);
            if (pr[id] < topPaths[rev[i][id]].size())
                qu.emplace(topPaths[rev[i][id]][pr[id]].first, id);
        }
        topPaths[i].emplace_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) {
            ranges::fill(dp, -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