Submission #1301773

#	Time	Username	Problem	Language	Result	Execution time	Memory
1301773		kiteyu	Bitaro’s Party (JOI18_bitaro)	C++20	0 / 100	8 ms	6980 KiB

bitaro

#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
using ll = long long;
const int N = 1e5;
int n,m,q;
vector<int> adj[N+5];
int d[N+5],qe[N+5],busy[N+5];
bool f[N+5],fbusy[N+5];
int head = 0, tail = 0;

set<pair<int,int>> largest[N+5];

int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n >> m >> q;
    for(int i = 1,x,y; i <= m ; ++i){
        cin >> x >> y;
        adj[y].push_back(x);
    }
    for(int i = 1 ; i <= n ; ++i){
        for(int j : adj[i]){
            d[i] = max(d[i],d[j] + 1);
            for(pair<int,int> j1 : largest[j])
                largest[i].insert(j1);
        }
        largest[i].insert({d[i],i});
//        sort(largest[i].begin(),largest[i].end(),[&](pair<int,int> x, pair<int,int>y){
//            return x.se < y.se;
//        });
        while(largest[i].size() > 100) largest[i].erase((*largest[i].rbegin()));
    }
//    for(int i = 1 ; i <= n ; ++i){
//        cout << i << ":\n";
//        for(auto j : largest[i]) cout << j.fi << ',' << j.se << '\n';
//
//    }

    for(int i = 1 ; i <= q ; ++i){ int t,k;
        cin >> t >> k;
        for(int j = 1 ; j <= k ; ++j) cin >> busy[j], fbusy[busy[j]] = 1;
        bool ok = false;
        for(pair<int,int> j : largest[t]) if(!fbusy[j.se]){
//            cout << j.fi << ',' << j.se << '\n';
            cout << d[t] - j.fi << '\n';
            ok = true;
            break;
        }
        if(!ok){
            head = tail = 0;
            qe[++tail] = t;
            f[t] = 1;
            int ans = -1;
            while(head < tail){
                int u = qe[++head];
//                cout << u << "!" << fbusy[u] << '\n';
                if(!fbusy[u]) {
//                    cout << u << "!\n";
                    ans = max(ans,d[t] - d[u]);
                }
                for(int j : adj[u]) if(!f[j]){
                    f[j] = 1;
                    qe[++tail] = j;
                }
            }
            for(int j = 1 ; j <= tail ; ++j) f[qe[j]] = 0;
            cout << ans << '\n';
        }
        for(int j = 1 ; j <= k ; ++j) fbusy[busy[j]] = 0;
    }
    return 0;
}

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