Submission #928320

#	Time	Username	Problem	Language	Result	Execution time	Memory
928320		Aiperiii	Bitaro’s Party (JOI18_bitaro)	C++14	0 / 100	20 ms	11868 KiB

bitaro

#include <bits/stdc++.h>
#define int long long
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
#define pb push_back
using namespace std;
const int N=1e5+5,sq=400;
vector <pair <int,int> > cct[N];
vector <int> g[N];
signed main(){
    int n,m,q;
    cin>>n>>m>>q;
    for(int i=0;i<m;i++){
        int u,v;
        cin>>u>>v;
        g[v].pb(u);
    }
    vector <int> d(n+1),ld(n+1),can;
    for(int i=1;i<=n;i++){
        d[i]=0;
        can.pb(i);
        for(auto edg : g[i]){
            for(auto x : cct[edg]){
                if(ld[x.ss]==i){
                    d[x.ss]=max(d[x.ss],x.ff+1);
                }
                else{
                    d[x.ss]=x.ff+1;
                    ld[x.ss]=i;
                    can.pb(x.ss);
                }
            }
        }
        for(auto x : can){
            cct[i].pb({d[x],x});
        }
        sort(cct[i].rbegin(),cct[i].rend());
        while(cct[i].size()>sq)cct[i].pop_back();
        /*cout<<i<<"\n";
        for(auto x :cct[i])cout<<x.ff<<" "<<x.ss<<"\n";
        cout<<"\n";*/
        can.clear();
    }
    
    vector <int> no(n+1);
    while(q--){
        int t,s;
        cin>>t>>s;
        vector <int> a(s);
        for(int i=0;i<s;i++){
            cin>>a[i];
            no[a[i]]=1;
        }
        int ans=-1;
        for(auto x : cct[t]){
            if(!no[x.ss]){
                ans=x.ff;
                break;
            }
        }
        cout<<ans<<"\n";
        for(int i=0;i<s;i++){
            no[a[i]]=0;
        }
    }
}
/*

 */

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