Submission #1320296

#	Time	Username	Problem	Language	Result	Execution time	Memory
1320296		husseinjuanda	Bitaro’s Party (JOI18_bitaro)	C++20	100 / 100	1088 ms	283632 KiB

bitaro

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

int B = 100;

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, m, q; cin >> n >> m >> q;
    vector<vector<int>> g(n+1);
    vector<vector<int>> rg(n+1);
    for(int i = 0; i < m; i++){
        int a, b; cin >> a >> b;
        // if(a < b){
        //     swap(a, b);
        // }
        g[a].push_back(b);
        rg[b].push_back(a);
    }
    vector<vector<pair<int, int>>> path(n+1); //path 
    vector<int> mx(n+1, -1);
    for(int i = 1; i <= n; i++){
        path[i].push_back({0, i});
        mx[i] = 0;
        for(int y = 0; y < rg[i].size(); y++){
            for(auto k : path[rg[i][y]]){
                if(mx[k.second] == -1){
                    path[i].push_back({k.first+1, k.second});
                    mx[k.second] = k.first+1;
                }else{
                    mx[k.second] = max(mx[k.second], k.first+1);
                }
            }
        }
        for(int y = 0; y < path[i].size(); y++){
            path[i][y].first = mx[path[i][y].second];
            mx[path[i][y].second] = -1;
        }
        sort(path[i].rbegin(), path[i].rend());
        while(path[i].size() > B){
            path[i].pop_back();
        }
    }
    for(int i = 1; i <= n; i++){
        for(int y = 0; y < path[i].size(); y++){
            swap(path[i][y].first, path[i][y].second);
        }
        sort(path[i].begin(), path[i].end());
    }
    while(q--){
        int k; cin >> k;
        int sz; cin >> sz;
        vector<int> j(sz);
        for(int i = 0; i < sz; i++){
            cin >> j[i];
        }
        sort(j.begin(), j.end());
        if(sz >= B){
            vector<int> dp(n+1, 0);
            for(int i = 0; i < sz; i++){
                dp[j[i]] = -1e18;
            }
            for(int i = 1; i < k; i++){
                for(int y = 0; y < g[i].size(); y++){
                    dp[g[i][y]] = max(dp[g[i][y]], dp[i]+1);
                }
            }
            if(dp[k] < 0){
                dp[k] = -1;
            }
            cout << dp[k] << "\n";
        }else{
            int it = 0;
            int mx = -1;
            for(int y = 0; y < j.size(); y++){
                while(it < path[k].size()){
                    if(path[k][it].first == j[y]){
                        it++;
                    }else if(path[k][it].first < j[y]){
                        mx = max(mx, path[k][it].second);
                        it++;
                    }else{
                        break;
                    }
                }
            }
            for(int y = it; y < path[k].size(); y++){
                mx = max(mx, path[k][y].second);
            }
            cout << mx << "\n";
        }
    }
    return 0;
}

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