Submission #1130551

#	Time	Username	Problem	Language	Result	Execution time	Memory
1130551		farica	Bitaro’s Party (JOI18_bitaro)	C++20	0 / 100	37 ms	6984 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;
const int MAX_N = 1e5 + 5;

vector<vi>adjL(MAX_N);
vector<vector<pi>>paths(MAX_N);

void solve() {
    int n, m, q;
    cin >> n >> m >> q;
    for(int i=0; i<m; ++i) {
        int x, y;
        cin >> x >> y;
        adjL[y].push_back(x);
    }
    for(int i=1; i<=n; ++i) {
        priority_queue<pi>pq;
        pq.push({0, i});
        set<int> added;
        for(int adj: adjL[i]) {
            for(pi p: paths[adj]) pq.push({p.first+1, p.second});
        }
        while(!pq.empty() && paths[i].size() < B) {
            pi cur = pq.top();
            pq.pop();
            auto it = find(added.begin(), added.end(), cur.second);
            if(it == added.end()) {
                paths[i].push_back(cur);
                added.insert(cur.second);
            }
        }
    }
    for(int i=0; i<q; ++i) {
        int t, num;
        cin >> t >> num;
        if(num >= B) {
            vi dp(n+1, 0);
            for(int j=t; j>=1; --j) {
                if(!dp[j] && j != t) continue;
                for(int adj: adjL[j]) {
                    dp[adj] = max(dp[adj], dp[j] + 1);
                }
            }
            vector<bool>blocked(n+1, 0);
            for(int j=0; j<num; ++j) {
                int tmp;
                cin >> tmp;
                blocked[tmp] = 1;
            }
            int ans = -1;
            for(int j=1; j<=t; ++j) {
                if(!blocked[j]) {
                    ans = max(ans, dp[j]);
                }
            }
            cout << ans << endl;
        } else {
            vi blocked(num);
            int ans = -1;
            for(int j=0; j<num; ++j) cin >> blocked[j];
            for(int j=0; j<paths[t].size(); ++j) {
                int tmp = paths[t][j].second;
                auto it = find(blocked.begin(), blocked.end(), tmp);
                if(it == blocked.end()) {
                    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: 0 / 7
• Subtask 2: 0 / 7
• Subtask 3: 0 / 86