Submission #1269265

#	Time	Username	Problem	Language	Result	Execution time	Memory
1269265		newsboy	Bitaro’s Party (JOI18_bitaro)	C++20	7 / 100	2117 ms	410596 KiB

bitaro

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <numeric>
#include <iomanip>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <queue>
#include <deque>
#include <stack>
#include <cmath>
#include <tuple>
#include <cassert>
#include <array>
#include <list>
#include <random>
#include <initializer_list>
#include <utility>
using namespace std;
using i64 = long long;
using u64 = unsigned long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, M, Q;
    cin >> N >> M >> Q;
    constexpr int B = 400;
    vector<vector<int>> adj(N);
    for (int i = 0; i < M; i++) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        adj[v].push_back(u);
    }
    vector<vector<array<int, 2>>> f(N);
    vector<int> dp(N, -1);
    for (int i = 0; i < N; i++) {
        f[i].push_back({0, i});
        vector<int> a;
        for (auto j : adj[i]) {
            for (auto e : f[j]) {
                int dis = e[0], idx = e[1];
                if (dp[idx] == -1) {
                    a.push_back(idx);
                    dp[idx] = dis + 1;
                }
                else {
                    dp[idx] = max(dp[idx], dis + 1);
                }
            }
        }
        for (auto j : a) {
            f[i].push_back({dp[j], j});
        }
        sort(f[i].rbegin(), f[i].rend());
        while (f[i].size() > B) {
            f[i].pop_back();
        }
        for (auto j : a) {
            dp[j] = -1;
        }
    }
    vector<bool> b(N);
    while (Q--) {
        int T, Y;
        cin >> T >> Y;
        T--;
        vector<int> C(Y);
        for (int i = 0; i < Y; i++) {
            cin >> C[i];
            C[i]--;
            b[C[i]] = 1;
        }
        if (Y < B) {
            bool ok = 0;
            for (auto e : f[T]) {
                int dis = e[0], idx = e[1];
                if (!b[idx]) {
                    cout << dis << '\n';
                    ok = 1;
                    break;
                }
            }
            if (!ok) {
                cout << -1 << '\n';
            }
        }
        else {
            fill(dp.begin(), dp.begin() + T + 1, -1);
            for (int i = 0; i <= T; i++) {
                if (!b[i]) {
                    dp[i] = 0;
                }
                for (auto j : adj[i]) {
                    if (dp[j] != -1) {
                        dp[i] = max(dp[i], dp[j] + 1);
                    }
                }
            }
            cout << dp[T] << '\n';
        }
        for (auto i: C) {
            b[i] = 0;
        }
    }
}

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