Submission #1320527

#	Time	Username	Problem	Language	Result	Execution time	Memory
1320527		AMel0n	Bitaro’s Party (JOI18_bitaro)	C++20	7 / 100	2098 ms	214328 KiB

bitaro

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 1e9 + 7;
const int SQRT = 300;

// bitarooo

int N, M, Q;
signed main() {
    cin.tie(0); ios::sync_with_stdio(false);
    cin >> N >> M >> Q;
    vector<vector<int>> adj(N); // reversed
    for(int i = 0; i < M; i++) {
        int a, b;
        cin >> a >> b;
        a--; b--;
        adj[b].push_back(a); // topo sorted alr
    }
    vector<vector<pair<int,int>>> dp(N);
    for(int v = 0; v < N; v++) {
        dp[v].emplace_back(0, v);
        unordered_map<int, int> victor;
        for(int &u: adj[v]) {
            for(auto &[dist, start]: dp[u]) { // MsqrtN
                victor[start] = max(victor[start], dist + 1);
            }
        }
        for(auto &[start, dist]: victor) {
            dp[v].emplace_back(dist, start);
        }
        sort(dp[v].begin(), dp[v].end());
        reverse(dp[v].begin(), dp[v].end());
        while(dp[v].size() > SQRT) dp[v].pop_back(); 
    }
    for(int i = 0; i < Q; i++) {
        int t, y;
        cin >> t >> y;
        t--;
        unordered_set<int> cant;
        for(int j = 0; j < y; j++) {
            int x;
            cin >> x;
            x--;
            cant.insert(x);
        }
        if (y < SQRT) {
            bool yes = false;
            for(int k = 0; k < dp[t].size(); k++) {
                if (cant.find(dp[t][k].second) == cant.end()) {
                    yes = true;
                    cout << dp[t][k].first << endl;
                    break;
                }
            }
            if (!yes) cout << -1 << endl;
        } else {
            vector<int> dp2(N, -INF);
            for(int v = 0; v <= t; v++) {
                if (cant.find(v) == cant.end()) dp2[v] = 0;
                for(int &u: adj[v]) {
                    dp2[v] = max(dp2[v], dp2[u] + 1);
                }
            }
            if (dp2[t] >= 0) cout << dp2[t] << endl;
            else cout << -1;
        }
    }
}

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