Submission #863827

#	Time	Username	Problem	Language	Result	Execution time	Memory
863827		biximo	Bitaro’s Party (JOI18_bitaro)	C++17	7 / 100	2033 ms	33884 KiB

bitaro

#include <bits/stdc++.h>
#define N 200005
#define BL 150
using namespace std;
typedef pair<int, int> pi;
int n, m, q;
vector<int> paths[N], NOT;
set<pi> dp[N], alr[N];
bool visited[N];
void dfs(int cur) {
    visited[cur] = 1;
    for(int i: paths[cur]) {
        for(auto&[v, ind]: dp[cur]) {
            auto alrin = alr[i].lower_bound(pi(ind, 0));
            if(alrin != alr[i].end() && (*alrin).first == ind) {
                dp[i].erase(pi((*alrin).second, -(*alrin).first));
                alr[i].erase(alrin);
            }
            if(dp[i].size() == BL) {
                if(v - 1 < (*prev(dp[i].end())).first) {
                    dp[i].erase(prev(dp[i].end()));
                } else {
                    break;
                }
            }
            dp[i].insert({v-1, ind});
            alr[i].insert({ind, -v + 1});
        }
    }
}
int ANS[N];
bool allowed[N];
void DP(int cur) {
    visited[cur] = 1;
    if(ANS[cur] == -1) return;
    for(int i: paths[cur]) {
        ANS[i] = max(ANS[i], ANS[cur] + 1);
    }
}
int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> m >> q;
    for(int i = 1; i <= n; i ++) {
        dp[i].insert({0, i});
    }
    while(m--) {
        int a, b;
        cin >> a >> b;
        paths[a].push_back(b);
    }
    for(int i = 1; i <= n; i ++) {
        if(!visited[i]) dfs(i);
        allowed[i] = 1;
    }
    while(q--) {
        int a, b;
        cin >> a >> b;
        NOT.resize(b);
        for(auto&i: NOT) {
            cin >> i;
            allowed[i] = 0;
        }
        if(b > BL) {
            for(auto&i: ANS) i = 0;
            for(auto i: NOT) ANS[i] = -1;
            for(auto&i: visited) i = 0;
            for(int i = 1; i <= n; i ++) {
                if(!visited[i]) DP(i);
            }
            cout << ANS[a] << "\n";
        } else {
            bool added = true;
            for(auto&[v, i]: dp[a]) {
                if(allowed[i]) {
                    added = false;
                    cout << (-v) << "\n";
                    break;
                }
            }
            if(added) cout << -1 << "\n";
        }
        for(auto&i: NOT) allowed[i] = 1;
    }
}

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