Submission #488692

#	Time	Username	Problem	Language	Result	Execution time	Memory
488692		dooompy	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	1528 ms	414648 KiB

bitaro

#include "bits/stdc++.h"

using namespace std;

using ll = long long;

const int SQRT = 350;
const int maxN = 1e5;

int dp[maxN + 5];
vector<int> adj[maxN + 5];
vector<pair<int, int>> root[maxN + 5];

int n, m, q;

void build() {
    vector<int> seen(n + 5, 0);
    vector<int> cost(n + 5, 0);

    for (int i = 1; i <= n; i++) {
        vector<int> r;

        for (auto a : adj[i]) {
            for (auto b : root[a]) {
                if (seen[b.first] == i) {
                    cost[b.first] = max(cost[b.first], b.second + 1);
                } else {
                    seen[b.first] = i;
                    cost[b.first] = b.second + 1;
                    r.push_back(b.first);
                }
            }
            if (seen[a] != i) {
                r.push_back(a);
                cost[a] = 1;
                seen[a] = i;
            }
        }

        r.push_back(i);

        sort(r.begin(), r.end(), [&](int a, int b) {
            return cost[a] > cost[b];
        });

        int sz = min(SQRT, (int) r.size());
        for (int j = 0; j < sz; j++) {
            root[i].emplace_back(r[j], cost[r[j]]);
        }
    }

}

int main() {
    cin >> n >> m >> q;

    for (int i = 0; i < m; i++) {
        int a, b; cin >> a >> b;
        adj[b].push_back(a);
    }

    build();

    vector<int> queries(n + 5);

    for (int i = 1; i <= q; i++) {
        int t, y; cin >> t >> y;
        for (int j = 1; j <= y; j++) {
            int x; cin >> x;
            queries[x] = i;
        }

        if (y < SQRT) {
            bool printed = false;
            for(auto a : root[t]) {
                if (queries[a.first] == i) continue;
                cout << a.second << "\n";
                printed = true;
                break;
            }
            if (!printed) cout << -1 << "\n";
        } else {
            for (int j = 1; j <= n; j++) {
                if (queries[j] != i) dp[j] = 0;
                else dp[j] = -1;

                for (auto k : adj[j]) {
                    if (dp[k] >= 0) dp[j] = max(dp[j], dp[k] + 1);
                }
            }
            cout << dp[t] << "\n";
        }

    }
}

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