Submission #942407

#	Time	Username	Problem	Language	Result	Execution time	Memory
942407		Blagoj	Bitaro’s Party (JOI18_bitaro)	C++17	0 / 100	3 ms	6492 KiB

bitaro

#include <bits/stdc++.h>

using namespace std;

#define endl '\n'
#define ll long long
#define all(x) (x).begin(), (x).end()

const int mxn = 1e5 + 10, K = 320;

int n, m, q;
vector<int> g[mxn];
vector<pair<int, int>> mx[mxn];
pair<int, int> mxDist[mxn];

void init() {
    for (int i = 1; i <= n; i++) {
        mx[i].push_back({0, i});
        mxDist[i] = {0, i};
        vector<int> v;
        for (auto x : g[i]) {
            for (auto [dist, from] : mx[x]) {
                if (mxDist[from].second != i) {
                    mxDist[from] = {dist + 1, i};
                    v.push_back(from);
                }
                else mxDist[from].first = max(mxDist[from].first, dist + 1);
            }
        }
        for (auto x : v) mx[i].push_back({mxDist[x].first, x});
        sort(all(mx[i]));
        reverse(all(mx[i]));
        int sz = mx[i].size();
        while (sz > K) {
            sz--;
            mx[i].pop_back();
        }
    }
}

int dp[mxn], blocked[mxn];

int solve(int Time, int node) {
    memset(dp, 0, sizeof(dp));
    for (int i = 1; i <= node; i++) {
        for (auto x : g[i]) {
            dp[i] = max(dp[i], dp[x] + 1);
        }
        if (dp[i] == 0 && blocked[i] == Time) dp[i] = -1;
    }
    return dp[node];
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> m >> q;
    for (int i = 0; i < m; i++) {
        int f, t;
        cin >> f >> t;
        g[t].push_back(f);
    }
    init();
    int cnt = 0;
    while (q--) {
        cnt++;
        int node, sz;
        cin >> node >> sz;
        for (int i = 0; i < sz; i++) {
            int x;
            cin >> x;
            blocked[x] = cnt;
        }
        if (sz < K) {
            for (auto x : mx[node]) {
                if (blocked[x.second] != cnt) {
                    cout << x.first << endl;
                    break;
                }
            }
        }
        else solve(cnt, node);
    }
}

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