Submission #799885

#	Time	Username	Problem	Language	Result	Execution time	Memory
799885		phoenix	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	1537 ms	489020 KiB

bitaro

#include<bits/stdc++.h>

using namespace std;

using ll = long long;

const int N = 1e5 + 10;
const int INF = 1e9;
const int B = 300;

int n, m, q;
vector<int> g0[N], g1[N];

int solve(int t, vector<int> st) {
    vector<int> dp(n + 1, -2 * INF);
    dp[t] = 0;
    for(int i = n; i >= 1; i--) {
        for(int to : g0[i]) 
            dp[i] = max(dp[i], dp[to] + 1);
    }
    bool us[n + 1] = {};
    for(int c : st) 
        us[c] = 1;
    
    int res = -INF;
    for(int i = 1; i <= n; i++) {
        if(us[i]) continue;
        res = max(res, dp[i]);
    } 
    if(res == -INF) res = -1;
    return res;
}
vector<pair<int, int>> v[N];
bool us[N];

void merge(int i, int j) {
    vector<pair<int, int>> res;
    int lb = 0, rb = 0;
    // for(auto [d, c] : v[i]) cout << c << ' ';
    // cout << '\n';
    // for(auto [d, c] : v[j]) cout << c << ' ';
    // cout << '\n';
    // for(auto [d, c] : res) cout << c << ' ';
    // cout << '\n';
    while((int)res.size() < B && (lb < (int)v[i].size() || rb < (int)v[j].size())) {
        while(lb < (int)v[i].size() && us[v[i][lb].second]) lb++;
        while(rb < (int)v[j].size() && us[v[j][rb].second]) rb++;
        if(lb == (int)v[i].size() && rb == (int)v[j].size()) break;
        int w1 = (lb < (int)v[i].size() ? v[i][lb].first : -INF);
        int w2 = (rb < (int)v[j].size() ? v[j][rb].first : -INF);
        if(w1 > w2) res.push_back({v[i][lb].first, v[i][lb].second}), lb++;
        else res.push_back({v[j][rb].first, v[j][rb].second}), rb++;
        us[res.back().second] = 1;
    }
    v[i] = res;
    for(auto [d, c] : v[i]) us[c] = 0;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin >> n >> m >> q;
    for(int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        g0[u].push_back(v);
        g1[v].push_back(u);
    }
    for(int i = 1; i <= n; i++) {
        for(int from : g1[i]) {
            merge(i, from);
        }
        for(auto &x : v[i]) x.first++;
        v[i].push_back({0, i});
    }
    while(q--) {
        int t, k;
        cin >> t >> k;
        vector<int> y(k);
        for(int i = 0; i < k; i++) {
            cin >> y[i];
            us[y[i]] = 1;
        }
        int ans = 0;
        if(k >= B) ans = solve(t, y);
        else {
            int lb = 0;
            while(lb < (int)v[t].size() && us[v[t][lb].second])
                lb++;
            if(lb == (int)v[t].size()) ans = -1;
            else ans = v[t][lb].first;
        }
        cout << ans << '\n';
        for(int c : y) us[c] = 0;
    }
}   

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