제출 #1111640

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1111640		diobrando97	Bitaro’s Party (JOI18_bitaro)	C++17	14 / 100	1155 ms	192584 KiB

bitaro

#include <bits/stdc++.h>
// #pragma GCC optimize(3)
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#define F first
#define S second
#define endl '\n'
#define bpc(x) __builtin_popcount(x)
#define bpcll(x) __builtin_popcountll(x)

using namespace std;
using ll = long long;
using i128 = __int128;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

const ll Inf = 1e18;
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const int N = 2e5 + 5;

void solve(){
    int n, m, q; cin >> n >> m >> q;
    vector<vector<int>> g(n+1);
    for(int i=1; i<=m; i++){
        int x, y; cin >> x >> y;
        g[x].push_back(y);
    }

    const int B = 80;
    vector<vector<pii>> path(n+1);
    auto rs = [&](auto &q) -> void {
        sort(q.rbegin(), q.rend());
        while(q.size() > B) q.pop_back();
        return;
    };
    for(int i=1; i<=n; i++){
        path[i].push_back({0, i});
        rs(path[i]);
        for(auto j : g[i]){
            for(auto [x, y] : path[i]){
                path[j].push_back({x + 1, y});
            }
        }
    }

    

    vector<bool> ban(n+1);
    for(int i=1; i<=q; i++){
        int pos; cin >> pos;
        int k; cin >> k;
        vector<int> t(k);
        for(int j=0; j<k; j++) cin >> t[j];
        for(auto x : t) ban[x] = 1;
        if(k < B){
            int res = -1;
            for(auto [x, y] : path[pos]){
                if(ban[y]) continue;
                res = max(res, x);
            }
            cout << res << endl;
        }
        else{
            vector<int> dp(n+1, -1);
            dp[pos] = 0;
            for(int i=pos; i>=1; i--){
                int ma = -1;
                for(auto j : g[i]){
                    if(dp[j] == -1) continue;
                    ma = max(ma, dp[j]);
                }
                if(ma >= 0){
                    dp[i] = ma + 1;
                }
            }
            int res = -1;
            for(int i=1; i<=pos; i++){
                if(ban[i]) continue;
                res = max(res, dp[i]);
            }
            cout << res << endl;
        }

        for(auto x : t) ban[x] = 0;
    }

}


int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    //freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    
    int t = 1;
    //cin >> t;
    while(t--)
    solve();
    return 0;
}

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