Submission #476713

#	Time	Username	Problem	Language	Result	Execution time	Memory
476713		dooompy	Bitaro’s Party (JOI18_bitaro)	C++14	14 / 100	2101 ms	411600 KiB

bitaro

#include "bits/stdc++.h"


using namespace std;

using ll = long long;

const int SQRT = 350;

vector<int> adj[100005];
int dp[100005];
vector<pair<int, int>> root[100005];

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
//    freopen("", "r", stdin);
//    freopen("", "w", stdout);
    int n, m, q; cin >> n >> m >> q;
    for (int i = 0; i < m; i++) {
        int a, b; cin >> a >> b;
        adj[b].emplace_back(a);
    }

    vector<int> dist(n + 5, 0);
    vector<int> seen(n + 5, -1);
    for (int i = 1; i <= n; i++) {
        vector<int> temp;
        for (auto a : adj[i]) {
            for (auto b : root[a]) {
                if (seen[b.second] != i) {
                    seen[b.second] = i;
                    dist[b.second] = b.first + 1;
                    temp.push_back(b.second);
                } else {
                    dist[b.second] = max(dist[b.second], b.first + 1);
                }
            }
            if (seen[a] != i) {
                temp.push_back(a);
                dist[a] = 1;
                seen[a] = i;
            }
        }

        temp.push_back(i);

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

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

    vector<int> invalid(n + 5, 0);
    for (int i = 1; i <= q; i++) {
        int x, y; cin >> x >> y;
        for (int j = 0; j < y; j++) {
            int cur; cin >> cur;
            invalid[cur] = i;
        }

        if(x < SQRT) {
            bool found = false;
            for (auto a : root[x]) {
                if (invalid[a.second] == i) continue;
                found = true;
                cout << a.first << "\n";
                    break;
            }
            if (!found) {
                cout << -1 << "\n";
            }
        } else {
            for (int j = 1; j <= n; j++) {
                if (invalid[j] == i) dp[j] = -1;
                else dp[j] = 0;
                for (auto a : adj[j]) {
                    if (dp[a] >= 0) dp[j] = max(dp[j], dp[a] + 1);
                }
            }
            cout << dp[x] << "\n";
        }
    }
}

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