제출 #1131329

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1131329		tuongll	Bitaro’s Party (JOI18_bitaro)	C++20	14 / 100	1366 ms	410988 KiB

bitaro

// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <utility>
#include <cmath>
#include <ctime>
#include <cassert>
#include <set>
#include <stack>
#include <map>
#include <queue>
#include <random>
#include <chrono>
#include <bitset>
#include <array>
using ll = long long;
#define debug(x) cout << #x << " = " << x << '\n'
#define separator "===============================================\n"
#define all(a) a.begin(), a.end()
#define SZ(a) (int)(a).size()
using namespace std;
const int mxn = 1e5 + 3;
const ll  mod = 1e9 + 7;
const int inf32 = 2e9;
const ll  inf64 = 3e18;
int n, m, q;
vector<int> gt[mxn];
const int B = 320;
vector<pair<int, int>> best[mxn];
void solve(){
    cin >> n >> m >> q;
    for (int i = 1, u, v; i <= m; ++i){
        cin >> u >> v;
        gt[v].push_back(u);
    }
    best[1].emplace_back(0, 1);
    vector<int> dist(n + 1, -1), cand;
    for (int u = 2; u <= n; ++u){
        for (int i : gt[u]){
            for (auto node : best[i]){
                int d, v; tie(d, v) = node;
                if (dist[v] == -1) cand.push_back(v);
                dist[v] = max(dist[v], d + 1);
            }
        }
        for (int v : cand) best[u].emplace_back(dist[v], v);
        best[u].emplace_back(0, u);
        sort(all(best[u]), greater<>());
        while(SZ(best[u]) > B) best[u].pop_back();

        for (int v : cand) dist[v] = -1;
        cand.clear();
    }
    vector<bool> ban(n + 1, false);
    vector<int> lst;
    while(q--){
        int S, k;
        cin >> S >> k;
        for (int i = 0, u; i < k; ++i){
            cin >> u;
            ban[u] = true, lst.push_back(u);
        }
        int res = -1;
        if (k > B){
            vector<int> dp(S + 1, -1);
            dp[S] = 0;
            for (int u = S; u >= 1; --u){
                if (dp[u] == -1) continue;
                for (int v : gt[u])
                    dp[v] = max(dp[v], dp[u] + 1);
            }
            for (int u = 1; u <= S; ++u)
                if (!ban[u]) res = max(res, dp[u]);
        } else {
            for (auto node : best[S]){
                int d, u; tie(d, u) = node;
                if (!ban[u]) res = max(res, d);
            }
        }
        cout << res << '\n';
        for (int u : lst) ban[u] = false;
        lst.clear();
    }
}
int main(){
	auto start = chrono::steady_clock::now();
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t = 1;
    // cin >> t;
    while(t--) solve();
    chrono::duration<double> elapsed {chrono::steady_clock::now() - start};
    cerr << "\n>> Runtime: " << elapsed.count() << "s\n";
}

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