Submission #1320538

#	Time	Username	Problem	Language	Result	Execution time	Memory
1320538		AMel0n	Bitaro’s Party (JOI18_bitaro)	C++20	14 / 100	1157 ms	411536 KiB

bitaro

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

// bitarooo

signed main() {
    cin.tie(0); ios::sync_with_stdio(false);
    int N, M, Q;
    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);
    vector<pair<int,int>> idx(N, {-1, -1});
    for(int v = 0; v < N; v++) {
        dp[v].push_back({0, v});
        for(int &u: adj[v]) {
            for(auto &[dist, start]: dp[u]) { // MsqrtN
                if (idx[start].first != v) {
                    dp[v].push_back({dist + 1, start});
                    idx[start] = {v, dp[v].size() - 1};
                } else dp[v][idx[start].second].first = max(dp[v][idx[start].second].first, dist + 1);
            }
        }
        sort(dp[v].begin(), dp[v].end());
        reverse(dp[v].begin(), dp[v].end());
        while(dp[v].size() > SQRT) dp[v].pop_back(); 
    }
    vector<int> cant(N, -1);
    vector<int> dp2;
    for(int i = 0; i < Q; i++) {
        int t, y;
        cin >> t >> y;
        t--;
        for(int j = 0; j < y; j++) {
            int x;
            cin >> x;
            x--;
            cant[x] = i;
        }
        if (y < SQRT) {
            bool yes = false;
            for(int k = 0; k < dp[t].size(); k++) {
                if (cant[dp[t][k].second] != i) {
                    yes = true;
                    cout << dp[t][k].first << endl;
                    break;
                }
            }
            if (!yes) cout << -1 << endl;
        } else {
            dp2.assign(N, -INF);
            for(int v = 0; v <= t; v++) {
                if (cant[v] != i) 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: 7 / 7
• Subtask 3: 0 / 86