Submission #1316580

#	Time	Username	Problem	Language	Result	Execution time	Memory
1316580		aaaaaaaa	Bitaro’s Party (JOI18_bitaro)	C++20	7 / 100	2094 ms	136420 KiB

bitaro

#include <bits/stdc++.h>
using namespace std;
const int inf = -1e9;
const int mxN = 2e5 + 100;
const int mxB = 343;
vector<vector<int>> Query[mxN];
vector<int> adj[mxN], radj[mxN];
int dist[mxB][mxN];
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(nullptr); cout.tie(nullptr);
    int n, m, q;
    cin >> n >> m >> q;
    vector<int> ans(q + 1, -1);

    int block_size = sqrt(n + 1) + 1;

    for(int i = 0, u, v; i < m; ++i){
        cin >> u >> v; --u, --v;
        adj[u].push_back(v);
        radj[v].push_back(u);
    }


    int xx = 0;
                vector<int> dp(n + 1, inf);

    auto dfs = [&](auto &self, int u, int x) -> int {
        if(++xx == 1){
            priority_queue<pair<int, int>> pq;
            pq.push({0, x}); dp[x] = 0;
            while(pq.size()){
            auto [d, u] = pq.top();
            pq.pop();
            for(auto v : radj[u]){
                if(dp[v] < d + 1){
                    dp[v] = d + 1;
                    pq.push({d + 1, v});
                }
            }
        }
        }
        return dp[u];
    };


    auto get = [&](int l, int r, int x) -> int {
        int cans = -1;
        for(int i = l; i <= r;){
            if(i % block_size == 0 && i + block_size - 1 <= r){
                cans = max(cans, dist[i / block_size][x]);
                i += block_size;
            }else{
                cans = max(cans, dfs(dfs, i, x));
                i += 1;
            }
        }
        return cans;
    };

    auto process = [&](int x) -> void {
        if((int) Query[x].size()){
          dp = vector<int>(n + 1, inf);
        }
        for(auto cur : Query[x]){
            int cur_ans = -1;
            for(int j = 0; j < (int) cur.size() - 2; ++j){
                int l = cur[j] + 1, r = cur[j + 1] - 1;
                if(l <= r){
                    cur_ans = max(cur_ans, get(l, r, x));
                }
            }
            ans[cur.back()] = cur_ans;
        }
    };

    for(int i = 0, block = 0; i < n; i += block_size, block += 1){
        int j = i + block_size - 1;
        priority_queue<pair<int, int>> pq;
        for(int k = 1; k <= n; ++k){
            dist[block][k] = -1;
        }
        for(int k = i; k <= j; ++k){
            pq.push({0, k});
            dist[block][k] = 0;
        }
        while(pq.size()){
            auto [d, u] = pq.top();
            pq.pop();
            for(auto v : adj[u]){
                if(dist[block][v] < d + 1){
                    dist[block][v] = d + 1;
                    pq.push({d + 1, v});
                }
            }
        }
    }
    for(int i = 1, x, y; i <= q; ++i){
        cin >> x >> y; --x;
        vector<int> banned = {-1};
        int mx = 0;
        for(int j = 0, vrtx; j < y; ++j){
            cin >> vrtx; --vrtx;
            if(vrtx <= x){
                banned.push_back(vrtx);
            }
            mx = max(mx, vrtx);
        }
        if(mx > x){
            banned.push_back(mx);
        }else{
            banned.push_back(n);
        }
        sort(banned.begin(), banned.end());
        banned.push_back(i);
        Query[x].push_back(banned);
    }
    for(int i = 0; i < n; ++i){
        process(i);
    }
    for(int i = 1; i <= q; ++i) cout << ans[i] << "\n";
    return 0;
}

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