Submission #1122276

#	Time	Username	Problem	Language	Result	Execution time	Memory
1122276		hengliao	Bitaro’s Party (JOI18_bitaro)	C++14	14 / 100	2031 ms	21104 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;

ll n, m, q;
vll adj[mxN];
vll qry[mxN];
ll siz[mxN];
vll y[mxN];
ll dp[mxN];
ll e[mxN];

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);
        }
    }
    //assert(q==1);
    for(ll i=0;i<q;i++){
        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: 0 / 86