Submission #1269263

#TimeUsernameProblemLanguageResultExecution timeMemory
1269263newsboyBitaro’s Party (JOI18_bitaro)C++20
7 / 100
1377 ms589824 KiB
#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);
    i64 N, M, Q;
    cin >> N >> M >> Q;
    i64 B = sqrt(N);
    vector<vector<i64>> adj(N);
    for (i64 i = 0; i < M; i++) {
        i64 u, v;
        cin >> u >> v;
        u--, v--;
        adj[v].push_back(u);
    }
    vector<vector<array<i64, 2>>> f(N);
    vector<i64> dp(N, -1);
    for (i64 i = 0; i < N; i++) {
        f[i].push_back({0, i});
        vector<i64> a;
        for (auto j : adj[i]) {
            for (auto e : f[j]) {
                i64 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());
        f[i].resize(B);
        for (auto j : a) {
            dp[j] = -1;
        }
    }
    vector<bool> b(N);
    while (Q--) {
        i64 T, Y;
        cin >> T >> Y;
        T--;
        vector<i64> C(Y);
        for (i64 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]) {
                i64 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 (i64 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;
        }
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...