Submission #1176424

#	Time	Username	Problem	Language	Result	Execution time	Memory
1176424		nguyenkhangninh99	Bitaro’s Party (JOI18_bitaro)	C++20	100 / 100	1347 ms	212352 KiB

bitaro

#include<bits/stdc++.h>
using namespace std;

#define int long long

const int maxn = 1e5 + 5;

vector<int> g[maxn];
vector<pair<int, int>> f[maxn];
bool checked[maxn], ban[maxn];
int d[maxn], dp[maxn];

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

    //độ phức tạp tối đa M * b
    for(int u = 1; u <= n; u++){
        vector<pair<int, int>> res;
        res.push_back({0, u});
        for(int v: g[u]){
            for(auto [x, y]: f[v]) res.push_back({x + 1, y});
        }

        sort(res.begin(), res.end(), greater<>());

        for(auto [x, y]: res){
            if(!checked[y] && f[u].size() < 100){
                f[u].push_back({x, y});
                checked[y] = 1;
            }
        }
        for(auto [x, y]: res) checked[y] = 0;
    }

    while(q--){
        int a, b; cin >> a >> b;
        for(int i = 1; i <= b; i++){
            cin >> d[i];
            ban[d[i]] = 1;
        }

        if(b < 100){
            //dpt O(b)
            int ans = -1;
            for(auto [x, y]: f[a]){
                if(!ban[y]) ans = max(ans, x);
            }
            cout << ans << '\n';
        }
        else{
            //dpt tối đa. O(n + m);
            //số lần gọi tối đa (q / b);
            int ans = -1;
            for(int u = a; u >= 1; u--) dp[u] = -1;

            dp[a] = 0;

            for(int u = a; u >= 1; u--){
                if(dp[u] != -1){
                    if(!ban[u]) ans = max(ans, dp[u]);
                    for(int v: g[u]) dp[v] = max(dp[v], dp[u] + 1);
                }
            }
            cout << ans << '\n';
        }

        for(int i = 1; i <= b; i++) ban[d[i]] = 0;
    }
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    solve();
}

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