Submission #1094236

#	Time	Username	Problem	Language	Result	Execution time	Memory
1094236		icchou233	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	776 ms	146288 KiB

bitaro

#include <bits/stdc++.h>
using namespace std;
using PII = pair<int,int>;
#define rall(a) rbegin(a), rend(a)
#define f first
#define s second
constexpr int maxN = 1e5, step = 100;
vector<int> edges[maxN + 1];
vector<PII> dp[maxN + 1];
int dist[maxN + 1];
bitset<maxN + 1> busy;
int main() {
  	cin.tie(0) -> sync_with_stdio(0);
  	int n, m, q; cin >> n >> m >> q;
    for (int i = 0; i < m; i++) {
        int a, b; cin >> a >> b;
        edges[b].push_back(a);
    }
    for (int i = 1; i <= n; i++) dist[i] = -1;
    for (int i = 1; i <= n; i++) {
        dp[i].push_back({0, i});
        vector<int> indices;
        for (int e: edges[i]) {
            for (auto& [x, ind]: dp[e]) {
                if (dist[ind] == -1) {
                    indices.push_back(ind);
                    dist[ind] = x + 1;
                } else {
                    dist[ind] = max(dist[ind], x + 1);
                }
            }
        }
        for (int ind: indices) dp[i].push_back({dist[ind], ind});
        sort(rall(dp[i]));
        while (dp[i].size() > step) dp[i].pop_back();
        for (int ind: indices) dist[ind] = -1;
    } 
    while (q--) {
        int t, y, ans = -1; cin >> t >> y;
        for (int i = 0; i < y; i++) {
            int b; cin >> b;
            busy[b] = true;
        }
        if (y < step) { // search through dp
            for (auto& [x, ind]: dp[t]) {
                if (!busy[ind]) {
                    ans = x;
                    break;
                }
            }
        } else {
            vector<int> maxDist(t + 1, -1);
            maxDist[t] = 0;
            for (int i = t; i >= 0; i--) {
				if (maxDist[i] == -1) { continue; }
				if (!busy[i]) { ans = max(ans, maxDist[i]); }
				for (int j : edges[i]) { maxDist[j] = max(maxDist[j], maxDist[i] + 1); }
			}
        }
        cout << ans << '\n';
        busy.reset();
    }
}

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