Submission #1245812

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245812		bbldrizzy	Bitaro’s Party (JOI18_bitaro)	C++20	0 / 100	3 ms	1352 KiB

bitaro

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
vector<vector<int>> adj;
vector<vector<int>> radj;
vector<vector<pair<int, int>>> best; // <val, node>
vector<int> bp;

int dfs(int nd, vector<bool> &aggin) {
    if (aggin[nd]) return -1;
    int anz = 0;
    for (int x: radj[nd]) {
        if (aggin[x]) continue;
        anz = max(anz, 1+dfs(x, aggin));
    }
    return anz;
}

int main() {
    int n, m, q; cin >> n >> m >> q;
    adj.resize(n);
    radj.resize(n);
    best.resize(n, vector<pair<int, int>>());
    bp.resize(n, -1);
    for (int i = 0; i < m; i++) {
        int a, b; cin >> a >> b; --a; --b;
        adj[a].push_back(b);
        radj[b].push_back(a);
    }
    for (int i = 0; i < n; i++) {
        best[i].push_back({0, i});
        vector<int> in;
        for (int x: radj[i]) {
            for (pair<int, int> u: best[x]) {
                if (u.f == -1) break;
                if (bp[u.s] == -1) {
                    bp[u.s] = u.f+1;
                    in.push_back(u.s);
                } else {
                    bp[u.s] = max(bp[u.s], u.f+1);
                }
            }
        }
        for (int x: in) {
            best[i].push_back({bp[x], x});
        }
        sort(best[i].rbegin(), best[i].rend());
        best[i].resize(100, {-1, -1});
        for (int x: in) {
            bp[x] = -1;
        }
    }
    // for (int i = 0; i < n; i++) {
    //     for (auto j: best[i]) {
    //         cout << j.f << ", " << j.s << "  ";
    //     }
    //     cout << "\n";
    //     cout << "\n";
    // }
    vector<bool> aggin(n);
    for (int i = 0; i < q; i++) {
        int a, t; cin >> a >> t; --a;
        vector<int> clapped;
        for (int i = 0; i < t; i++) {
            int u; cin >> u; --u;
            clapped.push_back(u);
            aggin[u] = true;
        }
        if (t > 100) {
            int sigma = dfs(a, aggin);
            cout << sigma << "\n";
        } else {
            bool nig = false;
            for (pair<int, int> x: best[a]) {
                if (!aggin[x.s]) {
                    cout << x.f << "\n"; nig = true; break;
                }
            }
            if (!nig) cout << -1 << "\n";
        }
        for (int u: clapped) {
            aggin[u] = false;
        }
    }
}

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