Submission #1196222

#	Time	Username	Problem	Language	Result	Execution time	Memory
1196222		Double_Slash	Bitaro’s Party (JOI18_bitaro)	C++20	100 / 100	1107 ms	420920 KiB

bitaro

#include <bits/stdc++.h>

using namespace std;
using pint = pair<int, int>;

int n, m, q, seen[100001], dist[100001];
vector<int> adj[100001], freq[100001];
vector<pint> dp[100001];

int dfs(int i) {
    if (seen[i] == -q) return dist[i];
    dist[i] = seen[i] == q ? -n : 0;
    seen[i] = -q;
    for (int j: adj[i]) dist[i] = max(dist[i], dfs(j) + 1);
    return dist[i];
}

int main() {
    cin >> n >> m >> q;
    while (m--) {
        int s, e;
        cin >> s >> e;
        adj[e].emplace_back(s);
    }
    for (int i = 1; i <= n; ++i) {
        int mx = 0;
        for (int j: adj[i]) {
            for (auto [d, k]: dp[j]) {
                mx = max(mx, ++d);
                freq[d].clear();
                if (seen[k] == i) dist[k] = max(dist[k], d);
                else {
                    seen[k] = i;
                    dist[k] = d;
                }
            }
        }
        for (int j: adj[i]) {
            for (auto [d, k]: dp[j]) {
                if (not seen[k]) continue;
                freq[dist[k]].emplace_back(k);
                seen[k] = 0;
            }
        }
        for (freq[0] = {i}; ~mx; --mx) {
            for (int j: freq[mx]) {
                dp[i].emplace_back(mx, j);
                if (dp[i].size() * dp[i].size() >= n) goto end;
            }
        }
        end:;
    }
    for (; q; --q) {
        int t, y;
        cin >> t >> y;
        for (int i = y; i--;) {
            int c;
            cin >> c;
            seen[c] = q;
        }
        if (y < dp[t].size()) {
            for (auto [d, j]: dp[t]) {
                if (seen[j] == q) continue;
                cout << d << endl;
                break;
            }
        } else {
            int ans = dfs(t);
            cout << (ans < 0 ? -1 : ans) << endl;
        }
    }
}

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