Submission #1130557

#TimeUsernameProblemLanguageResultExecution timeMemory
1130557faricaBitaro’s Party (JOI18_bitaro)C++20
7 / 100
2099 ms91872 KiB
#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);
            }
        }
    }
    vi blk(n+1, -1);
    for(int i=0; i<q; ++i) {
        int t, num;
        cin >> t >> num;
        if(num >= B) {
            vi dp(t+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);
                }
            }
            for(int j=0; j<num; ++j) {
                int tmp;
                cin >> tmp;
                blk[tmp] = i;
            }
            int ans = -1;
            for(int j=1; j<=t; ++j) {
                if(blk[j] != i && dp[j]) {
                    ans = max(ans, dp[j]);
                }
            }
            if(ans == -1 && blk[t] != i) ans = 0;
            cout << ans << endl;
        } else {
            int ans = -1;
            for(int j=0; j<num; ++j) {
                int tmp;
                cin >> tmp;
                blk[tmp] = i;
            }
            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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...