Submission #1262544

#	Time	Username	Problem	Language	Result	Execution time	Memory
1262544		nathlol2	Bitaro’s Party (JOI18_bitaro)	C++20	100 / 100	946 ms	416600 KiB

bitaro

#include <bits/stdc++.h>
#define fi first
#define sc second
using namespace std;
const int N = 100005;
const int SQ = 330;
vector<vector<int>> g(N), rv(N);
vector<pair<int, int>> dp[N];
bool s[N];
int ans = -1;
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m, q;
    cin >> n >> m >> q;
    for(int i = 0;i<m;i++){
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        rv[v].push_back(u);
    }
    dp[1].push_back({0, 1});
    for(int i = 2;i<=n;i++){
        vector<int> ptr(rv[i].size(), 0);
        vector<int> dmg;
        for(int c = 0;c<SQ;c++){
            pair<int, int> a = {-1, -1};
            int idx = -1;
            for(int j = 0;j<rv[i].size();j++){
                if(ptr[j] < dp[rv[i][j]].size()){
                    while(ptr[j] < dp[rv[i][j]].size() && s[dp[rv[i][j]][ptr[j]].sc]){
                        ++ptr[j];
                    }
                    if(ptr[j] < dp[rv[i][j]].size() && dp[rv[i][j]][ptr[j]].fi > a.fi){
                        a.fi = dp[rv[i][j]][ptr[j]].fi;
                        a.sc = dp[rv[i][j]][ptr[j]].sc;
                        idx = j;
                    }
                }
            }
            if(idx == -1){
                break;
            }
            ++ptr[idx];
            dp[i].push_back({a.fi + 1, a.sc});
            s[a.sc] = 1;
            dmg.push_back(a.sc);
        }
        for(auto x : dmg){
            s[x] = 0;
        }
        dp[i].push_back({0, i});
    }
    bool come[N];
    for(int i = 1;i<N;i++){
        come[i] = 1;
    }
    while(q--){
        int x, h;
        cin >> x >> h;
        int a[h];
        for(int i = 0;i<h;i++){
            cin >> a[i];
            come[a[i]] = 0;
        }
        if(h < SQ){
            for(auto p : dp[x]){
                if(come[p.sc]){
                    ans = p.fi;
                    break;
                }
            }
        }else{
            vector<int> dp(N, -10000000);
            dp[x] = 0;
            for(int i = x;i>=1;i--){
                for(auto v : g[i]){
                    dp[i] = max(dp[i], dp[v] + 1);
                }
            }
            for(int i = x;i>=1;i--){
                if(come[i]){
                    ans = max(ans, dp[i]);
                }
            }
        }
        for(int i = 0;i<h;i++){
            come[a[i]] = 1;
        }
        cout << ans << '\n';
        ans = -1;
    }
}

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