Submission #1256136

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256136		Irate	Bitaro’s Party (JOI18_bitaro)	C++20	14 / 100	1016 ms	121452 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);
    }
    for(int i = 1;i <= n;++i){
        multiset<array<int, 4>>ms;
        for(int j : G[i]){
            ms.insert({D[j][0].first + 1, D[j][0].second, j, 0});
        }
        while(!ms.empty()){
            int d = (*(--ms.end()))[0], node = (*(--ms.end()))[1], nd = (*(--ms.end()))[2], p = (*(--ms.end()))[3];
            D[i].push_back({d, node});
            ms.erase(--ms.end());
            if((int)D[nd].size() != p + 1){
                ms.insert({D[nd][p + 1].first + 1, D[nd][p + 1].second, nd, p + 1});
            }
        }
        D[i].push_back({0, i});
        while(D[i].size() > B + 1){
            D[i].pop_back();
        }
    }
    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: 0 / 86