Submission #1052988

#	Time	Username	Problem	Language	Result	Execution time	Memory
1052988		BF001	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	1448 ms	259924 KiB

bitaro

#include<bits/stdc++.h>
using namespace std;
 
#define blsiz 200
#define N 100005
#define fi first
#define se second
#define oo 1e9

typedef pair<int, int> ii;

int n, m, q, dep[N], bl[N], val[N], dp[N];
vector<int> adj[N];
vector<ii> pth[N]; 
vector<int> tmp;

bool cmp(ii& a, ii& b){
    return a.fi > b.fi;
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    
    cin >> n >> m >> q;
    for (int i = 1; i <= m; i++){
        int u, v;
        cin >> u >> v;
        adj[v].push_back(u);
    }

    for (int i = 1; i <= n; i++) dep[i] = -1;

    for (int i = 1; i <= n; i++){
        pth[i].push_back({0, i});
        tmp.push_back(i);
        dep[i] = 0;
        for (auto x : adj[i]){
            for (auto v : pth[x]){
                if (dep[v.se] == -1){
                    dep[v.se] = v.fi + 1;
                    tmp.push_back(v.se);
                }
                else{
                    dep[v.se] = max(dep[v.se], v.fi + 1);
                }
            }
        }
        for (auto x : tmp) { pth[i].push_back({dep[x], x}); dep[x] = -1;}
        tmp.clear();
        sort(pth[i].begin(), pth[i].end(), cmp);
        while ((int) pth[i].size() > blsiz) pth[i].pop_back();
    }

    for (int i = 1; i <= n; i++) dp[i] = -oo;
 
    while (q--){
        int u, sl;
        cin >> u >> sl;
        for (int i = 1; i <= sl; i++){
            cin >> val[i];
            bl[val[i]] = 1;
        }
        if (sl < blsiz){
            int res = -1;
            for (auto x : pth[u]){
                if (!bl[x.se]) res = max(res, x.fi);
            }
            cout << res << "\n";
            for (int i = 1; i <= sl; i++) bl[val[i]] = 0;
            continue;
        }
        int res = -1;
        dp[u] = 0;
        for (int i = u; i >= 1; i--){
            for (auto x : adj[i]){
                dp[x] = max(dp[x], dp[i] + 1);
            }
            if (!bl[i]) res = max(res, dp[i]);
        }
        cout << res << "\n";
        for (int i = 1; i <= sl; i++) bl[val[i]] = 0;
        for (int i = 1; i <= u; i++) dp[i] = -oo;
    }   

    return 0;
}

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