Submission #1052972

#	Time	Username	Problem	Language	Result	Execution time	Memory
1052972		fryingduc	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	919 ms	517204 KiB

bitaro

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

#define int long long

const int maxn = 1e5 + 5;
const int B = 200;
int n, m, q;
vector<int> g[maxn];
vector<pair<int, int>> lp[maxn];
int del[maxn], d[maxn], mx[maxn][2];
void solve() {
    cin >> n >> m >> q;
    for(int i = 1; i <= m; ++i) {
        int u, v; cin >> v >> u;
        g[u].push_back(v);
    }
    memset(mx, 0, sizeof(mx));
    for(int i = 1; i <= n; ++i) {
        vector<int> cur;
        for(auto v:g[i]) {
            for(auto j:lp[v]) {
                int w = j.first, oe = j.second;
                if(mx[oe][1] != i) {
                    cur.push_back(oe);
                    mx[oe][1] = i;
                    mx[oe][0] = w + 1;
                }
                else {
                    mx[oe][0] = max(mx[oe][0], w + 1);
                }
            }
        }
        for(auto j:cur) {
            lp[i].push_back({mx[j][0], j});
        }
        lp[i].push_back({0, i});
        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) {
            for(int i = 0; i <= n; ++i) d[i] = -1;
            for(int i = 1; i <= x; ++i) {
                if(!del[i]) d[i] = 0;
                for(auto u:g[i]) {
                    if(d[u] != -1) d[i] = max(d[i], d[u] + 1);
                }
            }
            
            cout << d[x] << '\n';
        }
        else {
            int res = -1;
            for(int i = 0; i < (int)lp[x].size(); ++i) {
                if(!del[lp[x][i].second]) {
                    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: 86 / 86