Submission #1130561

#	Time	Username	Problem	Language	Result	Execution time	Memory
1130561		farica	Bitaro’s Party (JOI18_bitaro)	C++20	100 / 100	1106 ms	278624 KiB

bitaro

#include <bits/stdc++.h>
#define int long long

using namespace std;
using vi = vector<int>;
using pi = pair<int,int>;
using ll = long long;

const int B = 100;

void solve() {
    int n, m, q;
    cin >> n >> m >> q;
    vector<vi>adjL(n+1);
    vector<vector<pi>>paths(n+1);
    for(int i=0; i<m; ++i) {
        int x, y;
        cin >> x >> y;
        adjL[y].push_back(x);
    }
    vi from(n+1, -1);
    for(int i=1; i<=n; ++i) {
        vi idx;
        for(int adj: adjL[i]) {
            for(pi p: paths[adj]) {
                if(from[p.second] == -1) idx.push_back(p.second);
                from[p.second] = max(from[p.second], p.first + 1);
            }
        }
        paths[i].push_back({0, i});
        for(int j: idx) paths[i].push_back({from[j], j});
        sort(paths[i].rbegin(), paths[i].rend());
        while(paths[i].size() > B) paths[i].pop_back();
        for(int j: idx) from[j] = -1;
    }
    vi blk(n+1, -1);
    for(int i=0; i<q; ++i) {
        int t, num;
        cin >> t >> num;
        for(int j=0; j<num; ++j) {
            int tmp;
            cin >> tmp;
            blk[tmp] = i;
        }
        int ans = -1;
        if(num >= B) {
            vi dp(t+1, 0);
            for(int j=t; j>=1; --j) {
                if(!dp[j] && j != t) continue;
                if(blk[j] != i) ans = max(ans, dp[j]);
                for(int adj: adjL[j]) {
                    dp[adj] = max(dp[adj], dp[j] + 1);
                }
            }
            cout << ans << endl;
        } else {
            for(int j=0; j<paths[t].size(); ++j) {
                int tmp = paths[t][j].second;
                if(blk[tmp] != i) {
                    ans = paths[t][j].first;
                    break;
                }
            }
            cout << ans << endl;
        }
    }
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int t = 1;
    while(t--) solve();

    return 0;
}

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