Submission #1052925

#	Time	Username	Problem	Language	Result	Execution time	Memory
1052925		fryingduc	Bitaro’s Party (JOI18_bitaro)	C++17	14 / 100	1535 ms	415120 KiB

bitaro

#include "bits/stdc++.h"
using namespace std;

const int maxn = 1e5 + 5;
const int B = 350;
int n, m, q;
vector<int> g[maxn];
vector<pair<int, int>> lp[maxn];
int del[maxn], d[maxn], mx[maxn][2];

void dp(int src) {
    memset(d, 0, sizeof(d));
    for(int i = 1; i <= src; ++i) {
        for(auto u:g[i]) {
            d[i] = max(d[i], d[u] + 1);
        }
        
        if(d[i] == 0 and del[i]) {
            d[i] = -1;
        }
    }
}
void solve() {
    cin >> n >> m >> q;
    for(int i = 1; i <= m; ++i) {
        int u, v; cin >> v >> u;
        g[u].push_back(v);
    }
    for(int i = 1; i <= n; ++i) {
        vector<int> cur;
        lp[i].push_back({0, i});
        cur.push_back(i);
        mx[i][1] = i + 1;
        for(auto v:g[i]) {
            for(auto j:lp[v]) {
                if(mx[j.second][1] != i + 1) {
                    cur.push_back(j.second);
                    mx[j.second][1] = i + 1;
                    mx[j.second][0] = j.first + 1;
                }
                else {
                    mx[j.second][0] = max(mx[j.second][0], j.first + 1);
                }
            }
        }
        for(auto j:cur) {
            lp[i].push_back({mx[j][0], j});
        }
        sort(lp[i].begin(), lp[i].end(), greater<pair<int, int>>());
        while((int)lp[i].size() > B) {
            lp[i].pop_back();
        }
    }
    while(q--) {
        int sz, x; cin >> x >> sz;
        vector<int> cur;
        for(int i = 1; i <= sz; ++i) {
            int u; cin >> u;
            cur.push_back(u);
            del[u] = 1;
        }
        if(sz > B) {
            dp(x);
            cout << d[x] << '\n';
        }
        else {
            int res = -1;
            for(int i = 0; i < (int)lp[x].size(); ++i) {
//                cout << lp[x][i].second << " ";
                if(del[lp[x][i].second]) continue;
                res = lp[x][i].first;
                break;
            }
            
            cout << res << '\n';
        }
        for(auto &i:cur) del[i] = 0;
    }
}
signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    solve();
    return 0;
}

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