Submission #1265757

#	Time	Username	Problem	Language	Result	Execution time	Memory
1265757		canhnam357	Bitaro’s Party (JOI18_bitaro)	C++20	7 / 100	2059 ms	217400 KiB

bitaro

#include <bits/stdc++.h>
using namespace std;
#define N 100'001
int dp[N], mark[N]{};
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, m, q;
    cin >> n >> m >> q;
    vector<pair<int, int>> e(m);
    vector<vector<int>> adj(n + 1);
    for (auto &[u, v] : e) cin >> v >> u, adj[u].push_back(v);
    sort(e.rbegin(), e.rend());
    const int B = 150;
    vector<vector<pair<int, int>>> p(n + 1);
    for (int i = 1; i <= n; i++) {
        p[i].emplace_back(i, 0);
        for (int v : adj[i]) {
            for (auto [id, d] : p[v]) {
                p[i].emplace_back(id, d + 1);
            }
        }
        sort(p[i].begin(), p[i].end());
        int l = 0;
        for (int r = 1; r < p[i].size(); r++) {
            if (p[i][r].first == p[i][l].first) {
                p[i][l] = p[i][r];
            }
            else {
                p[i][++l] = p[i][r];
            }
        }
        l++;
        p[i].resize(l);
        l = min(l, B);
        sort(p[i].begin(), p[i].end(), [&](auto i, auto j) {
            return i.second > j.second;
        });
        p[i].resize(l);
    }
    int timer = 0;
    while (q--) {
        timer++;
        int t;
        cin >> t;
        int k;
        cin >> k;
        vector<int> c(k);
        for (int &i : c) cin >> i;
        while (k > 0 && c[k - 1] > t) {
            c.pop_back();
            k--;
        }
        for (int i : c) mark[i] = timer;
        if (k >= B) {
            memset(dp, -1, sizeof dp);
            dp[t] = 0;
            for (auto [u, v] : e) {
                if (dp[u] >= 0) {
                    dp[v] = max(dp[v], dp[u] + 1);
                }
            }
            int ans = -1, j = 0;
            for (int i = 1; i <= n; i++) {
                if (j < k && c[j] == i) j++;
                else if (dp[i] >= 0) {
                    ans = max(ans, dp[i]);
                }
            }
            cout << ans << '\n';
        }
        else {
            int ans = -1;
            for (auto [id, d] : p[t]) {
                if (mark[id] != timer) {
                    ans = d;
                    break;
                }
            }
            cout << ans << '\n';
        }
    }   
    return 0;
}

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