제출 #1245827

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1245827		bbldrizzy	Bitaro’s Party (JOI18_bitaro)	C++20	100 / 100	847 ms	150240 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 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) {
            vector<int> dp(a+1, -1);
            dp[a] = 0;
            int ans = -1;
			for (int i = a; i >= 0; i--) {
				if (dp[i] == -1) { continue; }
				if (!aggin[i]) { ans = max(ans, dp[i]); }
				for (int x: radj[i]) { dp[x] = max(dp[x], dp[i] + 1); }
			}
            cout << ans << "\n";
        } else {
            bool nig = false;
            for (pair<int, int> x: best[a]) {
                if (x.s == -1) continue;
                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: 7 / 7
• Subtask 2: 7 / 7
• Subtask 3: 86 / 86