Submission #1315845

#	Time	Username	Problem	Language	Result	Execution time	Memory
1315845		wangzhiyi33	Bitaro’s Party (JOI18_bitaro)	C++20	100 / 100	1678 ms	513524 KiB

bitaro

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ii pair<int,int>
#define fir first
#define sec second
#define pb push_back

const int maxn=1e5;
const int mx=200;

int n,m,qu;
vector<int>adj[maxn+2];
ii dist[maxn+2];
vector<ii>path[maxn+2];

void precom(){
    for(int q=1;q<=n;q++){
        vector<int>node;
        node.pb(q);
        dist[q]={0,q};

        for(auto x : adj[q]){
            for(auto [brp,idx]  : path[x]){
                if(dist[idx].sec!=q){
                    dist[idx]={brp+1,q};
                    node.pb(idx);
                }
                else{
                    dist[idx].fir=max(dist[idx].fir,brp+1);
                }
            }
        }

        for(auto x : node){
            path[q].pb({dist[x].fir,x});

            //if(q==4)cout<<dist[x].fir<<"K"<<x<<endl;
        }
        sort(path[q].rbegin(),path[q].rend());
        while(path[q].size()>mx){
            path[q].pop_back();
        }
    } 
}

bool skip[maxn+2];
int val[maxn+2];

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

    while(qu--){
        int city,brp;
        cin>>city>>brp;
        vector<int>apa;

        for(int q=1;q<=brp;q++){
            int x;cin>>x;
            apa.pb(x); skip[x]=true;
        }

        if(brp<mx){
            int ans=-1;
            for(auto [jrk,idx] : path[city]){
                if(skip[idx])continue;
                ans=jrk; break;
            }
            cout<<ans<<endl;
        }
        else{
            for(int q=1;q<=n;q++){
                val[q]=0;
            }
           
            for(int q=1;q<=city;q++){
                for(auto x : adj[q]){
                    val[q]=max(val[x]+1,val[q]);
                }
                if(val[q]==0 && skip[q]){
                    val[q]=-1;
                }
            }

            cout<<val[city]<<endl;
        }

        for(auto x : apa){
            skip[x]=false;
        }

    }
}

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