Submission #1050732

#	Time	Username	Problem	Language	Result	Execution time	Memory
1050732		Sharky	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	856 ms	414940 KiB

bitaro

#include <bits/stdc++.h>
using namespace std;

const int N = 100005;
const int B = 350;
const int INF = 1e7;
#define sz(x) (int)x.size()

vector<pair<int, int>> dp[N];
vector<int> radj[N];
int ptr[N], e[N];
bool b[N];

int32_t main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, m, q;
    cin >> n >> m >> q;
    for (int i = 1; i <= m; i++) {
        int s, e;
        cin >> s >> e;
        radj[e].push_back(s);
    }
    for (int u = 1; u <= n; u++) {
        for (auto v : radj[u]) ptr[v] = 0;
        while (sz(dp[u]) < B) {
            bool emp = 1;
            int mx = -1, id;
            for (auto v : radj[u]) {
                while (ptr[v] < sz(dp[v]) && e[dp[v][ptr[v]].second]) ptr[v]++;
                if (ptr[v] < sz(dp[v])) {
                    emp = 0;
                    if (dp[v][ptr[v]].first > mx) {
                        mx = dp[v][ptr[v]].first;
                        id = v;
                    }
                }
            }
            if (emp) break;
            dp[u].push_back({dp[id][ptr[id]].first + 1, dp[id][ptr[id]].second});
            e[dp[id][ptr[id]].second] = 1;
            ptr[id]++;
        }
        if (sz(dp[u]) < B) dp[u].push_back({0, u});
        for (auto& [x, y] : dp[u]) e[y] = 0;
    }
    while (q--) {
        int t, y, ans = -1;
        cin >> t >> y;
        vector<int> f(y);
        for (int i = 0; i < y; i++) {
            cin >> f[i];
            b[f[i]] = 1;
        }
        if (y < sz(dp[t]) || sz(dp[t]) < B) {
            for (auto& [dist, node] : dp[t]) {
                if (!b[node]) {
                    ans = dist;
                    break;
                }
            }
        } else {
            vector<int> g(n+1, -INF);
            for (int i = 1; i <= n; i++) if (!b[i]) g[i] = 0;
            for (int i = 1; i <= n; i++) for (int v : radj[i]) g[i] = max(g[i], g[v] + 1);
            ans = max(ans, g[t]);
        }
        cout << ans << '\n';
        for (int i = 0; i < y; i++) b[f[i]] = 0;
    }
}

Compilation message (stderr)

bitaro.cpp: In function 'int32_t main()':
bitaro.cpp:41:20: warning: 'id' may be used uninitialized in this function [-Wmaybe-uninitialized]
   41 |             ptr[id]++;
      |             ~~~~~~~^~

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