Submission #1147819

#	Time	Username	Problem	Language	Result	Execution time	Memory
1147819		weakweakweak	Bitaro’s Party (JOI18_bitaro)	C++20	100 / 100	1127 ms	517740 KiB

bitaro

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;
#define fs first 
#define sc second

int n, m, Q, y, ed, ein[510000] = {0}, tt = 1, bad[510000], dp[510000];
int B = 500, vis[510000]={0}, tt2=8;
vector<int> e[510000], topo;
vector<pii> ans[510000];


void bruteforce() {
    memset(dp, -63, sizeof(dp));
    for (int i : topo) {
        if (bad[i] != tt) dp[i] = max(dp[i], 0);
        for (int j : e[i]) dp[j] = max(dp[i]+1, dp[j]); 
    }
}


vector<pii> func(vector<pii> a, vector<pii> b) { 
    // 類似 merge sort
    vector<pii> c;
    tt2++;
    int i = 0, j = 0;
    while (i < a.size() or j < b.size()) {
        if (i != a.size() and (j == b.size() or a[i] > b[j])) {
            if (vis[a[i].sc] != tt2) {
                vis[a[i].sc] = tt2;
                c.push_back(a[i]);
            }
            i++;
        }
        else {
            if (vis[b[j].sc] != tt2) {
                vis[b[j].sc] = tt2;
                c.push_back(b[j]);
            }
            j++;
        }
    }
    if (c.size() > B) c.resize(B);
    return c;
}


int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
    cin >> n >> m >> Q;
    while (m--) {
        int x, y;
        cin >> x >> y;
        e[x].push_back(y);
        ein[y]++;
    }
    queue<int> q;
    for (int i = 1; i <= n; i++) if (!ein[i]) q.push(i);
    while (q.size()) {
        int i = q.front(); q.pop();
        topo.push_back(i);
        for (int j : e[i]) {
            if (!--ein[j]) q.push(j);
        }
    }

    
    for (int i : topo) {
        ans[i] = func(ans[i], vector<pii>(1,make_pair(0,i)));
        for (auto &[dis, id] : ans[i]) dis++;
        for (int j : e[i]) {
            ans[j] = func(ans[j], ans[i]);
        }
        for (auto &[dis, id] : ans[i]) dis--;
    }


    while (Q--) {
        tt++;
        cin >> ed >> y;
        vector<int> badv(y);
        for (int & x : badv) {
            cin >> x;
            bad[x] = tt;
        }
        if (y >= B) {
            bruteforce();
            if (dp[ed] < 0) dp[ed] = -1;
            cout << dp[ed] << '\n';
        }
        else {
            bool y = 0;
            for (auto [dis,i] : ans[ed]) {
                if (bad[i] == tt) continue;
                y = 1;
                cout << dis << '\n'; break;
            }
            if (!y) cout << "-1\n";
        }
    }

    return 0;
}

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