Submission #820025

#	Time	Username	Problem	Language	Result	Execution time	Memory
820025		Farbod	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	1140 ms	114232 KiB

bitaro

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

const int N = 1e5 + 20, sq = 69;

int n, m;
vector <int> adj[N];
vector <pair <int, int>> vec[N];

bool vis[N], seen[N];
int dp[N];

signed main()
{
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    int q;
    cin >> n >> m >> q;

    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v, u--, v--;

        adj[v].push_back(u);
    }

    for (int i = 0; i < n; i++) {        
        vector <pair <int, int>> tmp;
        for (auto u: adj[i])
            for (auto [j, idx]: vec[u])
                tmp.push_back({j + 1, idx});

        sort(tmp.begin(), tmp.end(), greater <>());

        for (auto [j, idx]: tmp) {
            if (vec[i].size() == sq)
                break;
            if (seen[idx])
                continue;
            vec[i].push_back({j, idx}), seen[idx] = 1;
        }
        for (auto [j, idx]: vec[i])
            seen[idx] = 0;

        if (vec[i].size() < sq)
            vec[i].push_back({0, i});
    }

    while (q--) {
        int v, k;
        cin >> v >> k, v--;

        vector <int> tmp;
        while (k--) {
            int x;
            cin >> x, x--, tmp.push_back(x), vis[x] = 1;
        }

        if (vec[v].size() < sq || tmp.size() < sq) {
            bool fnd = 0;
            for (auto [j, idx]: vec[v])
                if (!vis[idx]) {
                    cout << j << '\n', fnd = 1;
                    break;
                }

            if (!fnd)
                cout << "-1\n";
        }
        else {
            for (int i = 0; i <= v; i++) {
                dp[i] = (vis[i] ? -1 : 0);
                for (auto u: adj[i])
                    if (dp[u] != -1)
                        dp[i] = max(dp[i], dp[u] + 1);
            }

            cout << dp[v] << '\n';
        }

        for (auto x: tmp)
            vis[x] = 0;
    }

    return 0;
}

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