Submission #1256154

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256154		Irate	Bitaro’s Party (JOI18_bitaro)	C++20	100 / 100	1280 ms	83168 KiB

bitaro

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
const int B = 50; /// ?
vector<int> G[N];
vector<pair<int, int>> D[N];
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, m, q;
    cin >> n >> m >> q;
    for(int i = 0;i < m;++i){
        int u, v;
        cin >> u >> v;
        G[v].push_back(u);
    }
    vector<int>dist(n + 1, -1);
    for(int i = 1;i <= n;++i){
        D[i].push_back({0, i});
        vector<int>nodes;
        for(int j : G[i]){
            for(auto T : D[j]){
                int d = T.first + 1, nd = T.second;
                if(dist[nd] == -1){
                    nodes.push_back(nd);
                    dist[nd] = d;
                }
                else{
                    dist[nd] = max(dist[nd], d);
                }
            }
        }
        for(int j : nodes){
            D[i].push_back({dist[j], j});
        }
        sort(D[i].rbegin(), D[i].rend());
        while(D[i].size() > B + 1){
            D[i].pop_back();
        }
        for(int j : nodes){
            dist[j] = -1;
        }
    }
    for(int i = 0;i < q;++i){
        int t, k;
        cin >> t >> k;
        set<int>v;
        for(int i = 0;i < k;++i){
            int a;
            cin >> a;
            v.insert(a);
        }
        int res = -1;
        if(k > B){
            vector<int>dp(n + 1, -1e9);
            dp[t] = 0;
            for(int i = t;i >= 1;--i){
                for(int j : G[i]){
                    dp[j] = max(dp[j], dp[i] + 1);
                }
            }
            for(int i = 1;i <= t;++i){
                if(v.find(i) == v.end())res = max(res, dp[i]);
            }
        }
        else{
            for(int i = 0;i < (int)D[t].size();++i){
                int d = D[t][i].first, nd = D[t][i].second;
                if(v.find(nd) == v.end())res = max(res, d);
            }
        }
        cout << res << '\n';
    }
}

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