Submission #1354239

#TimeUsernameProblemLanguageResultExecution timeMemory
1354239anteknneBitaro’s Party (JOI18_bitaro)C++20
100 / 100
514 ms241640 KiB
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;

#define pb push_back
#define pii pair<int, int>
#define pll pair<ll, ll>
#define st first
#define nd second
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define debug false

const int K = 300;
const int MAXN = 100 * 1000 + 17 + K * 50;
pii dp[MAXN][K];
pii akt[K];
vector<int> graf[MAXN];
bool bylo[MAXN];
vector<int> vec;
int dp2[MAXN];

int main () {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

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

    int a, b;
    for (int i = 0; i < m; i ++) {
        cin >> a >> b;
        graf[b].pb(a);
    }

    for (int i = 1; i <= n; i ++) {
        for (int j = 0; j < K; j ++) {
            dp[i][j] = {-MAXN, n + j + 1};
        }
        dp[i][0] = {0, i};

        for (auto x : graf[i]) {
            int ind1 = 0, ind2 = 0;
            for (int j = 0; j < K; j ++) {
                while (bylo[dp[i][ind1].nd]) {
                    ind1 ++;
                }
                while (bylo[dp[x][ind2].nd]) {
                    ind2 ++;
                }
                if (dp[i][ind1].st >= dp[x][ind2].st + 1) {
                    akt[j] = {dp[i][ind1].st, dp[i][ind1].nd};
                    bylo[dp[i][ind1].nd] = true;
                    ind1 ++;
                } else {
                    akt[j] = {dp[x][ind2].st + 1, dp[x][ind2].nd};
                    bylo[dp[x][ind2].nd] = true;
                    ind2 ++;
                }
            }
            for (int j = 0; j < K; j ++) {
                bylo[dp[i][j].nd] = false;
                bylo[dp[x][j].nd] = false;
            }
            swap(akt, dp[i]);
        }
    }

    int t, k, x;
    while (q --) {
        cin >> t >> k;
        vec.clear();
        for (int i = 0; i < k; i ++) {
            cin >> x;
            vec.pb(x);
            bylo[x] = true;
        }

        if (k < K) {
            for (int i = 0; i < K; i ++) {
                if (!bylo[dp[t][i].nd]) {
                    if (dp[t][i].st < 0) {
                        cout << -1 << "\n";
                    } else {
                        cout << dp[t][i].st << "\n";
                    }
                    break;
                }
            }
        } else {
            for (int i = 1; i <= n; i ++) {
                if (!bylo[i]) {
                    dp2[i] = 0;
                } else {
                    dp2[i] = -MAXN;
                }
                for (auto x : graf[i]) {
                    dp2[i] = max(dp2[i], dp2[x] + 1);
                }
            }
            if (dp2[t] < 0) {
                cout << -1 << "\n";
            } else {
                cout << dp2[t] << "\n";
            }
        }

        for (auto x : vec) {
            bylo[x] = false;
        }
    }

    return 0;
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...