Submission #1122307

#	Time	Username	Problem	Language	Result	Execution time	Memory
1122307		hengliao	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	1693 ms	213580 KiB

bitaro

#include <bits/stdc++.h>
#include <chrono>
#include <random>
using namespace std;

#define F first
#define S second
#define pb push_back
#define vll vector<ll>
#define pll pair<ll, ll>
typedef long long ll;

const ll mxN=1e5+5;
const ll B=30;


ll n, m, q;
vll adj[mxN];
vll qry[mxN];
ll siz[mxN];
vll y[mxN];
ll dp[mxN];
ll e[mxN];
set<pll> st[mxN];
map<ll, ll> mp;

ll f(ll idx, ll t){
    memset(dp, -1, sizeof(dp));
    ll re=-1;
    dp[t]=0;
    while(siz[idx]>0 && y[idx].back()>t){
        siz[idx]--;
        y[idx].pop_back();
    }
    for(ll i=t;i>=0;i--){
        //cout<<i<<' '<<dp[i]<<'\n';
        if(siz[idx]>0 && y[idx].back()==i){
            siz[idx]--;
            y[idx].pop_back();
        }   
        else{
            re=max(re, dp[i]);
        }
        if(dp[i]!=-1){
            for(auto &it:adj[i]){
                dp[it]=max(dp[it], dp[i]+1);
            }
        }
        
    }
    return re;
}


void solve(){
    cin>>n>>m>>q;
    for(ll i=0;i<m;i++){
        ll u, v;
        cin>>u>>v;
        u--; v--;
        adj[v].pb(u);
    }
    for(ll i=0;i<q;i++){
        cin>>e[i];
        e[i]--;
        qry[e[i]].pb(i);
        cin>>siz[i];
        for(ll j=0;j<siz[i];j++){
            ll tep;
            cin>>tep;
            tep--;
            y[i].pb(tep);
        }
    }

    for(ll i=0;i<n;i++){
        mp.clear();
        mp[i]=0;
        for(auto &it:adj[i]){
            for(auto &[x, y]:st[it]){
                mp[y]=max(mp[y], x+1);
            }
        }
        //cout<<"considering mp:\n";
        for(auto &[x, y]:mp){
            //cout<<x<<' '<<y<<'\n';
            st[i].insert({y, x});
            if(st[i].size()>B){
                st[i].erase(st[i].begin());
            }
        }
        /*cout<<"st["<<i<<"]\n";
        for(auto &[x, y]:st[i]){
            cout<<x<<' '<<y<<'\n';
        }*/
    }

    auto check=[&](ll idx, ll tar){
        auto it=lower_bound(y[idx].begin(), y[idx].end(), tar);
        if(it==y[idx].end()) return false;
        return (*it)==tar;
    };
    //assert(q==1);
    for(ll i=0;i<q;i++){
        if(siz[i]<B){
            ll re=-1;
            for(auto &[x, y]:st[e[i]]){
                if(!check(i, y)){
                    re=max(re, x);
                }
            }
            cout<<re<<'\n';
        }
        else{
            cout<<f(i, e[i])<<'\n';
        }
    }
    
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

    solve();
    return 0;
}

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