Submission #567122

#	Time	Username	Problem	Language	Result	Execution time	Memory
567122		MrDeboo	Bitaro’s Party (JOI18_bitaro)	C++17	14 / 100	2089 ms	14332 KiB

bitaro

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define int long long
#define endl '\n'
using namespace std;
using namespace __gnu_pbds;
using ordered_set = tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>;
signed main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int n,m,q;
    cin>>n>>m>>q;
    vector<int>vct[n+1];
    vector<int>vec[n+1];
    while(m--){
        int u,v;
        cin>>u>>v;
        vct[max(v,u)].push_back(min(u,v));
        vec[min(v,u)].push_back(max(u,v));
    }
    while(q--){
        int ans=-1;
        vector<bool>v(n+1,1);
        int a;
        cin>>a;
        deque<pair<int,int>>dq={{a,0}};
        int f=a;
        int k;
        cin>>k;
        while(k--){
            cin>>a;
            v[a]=0;
        }
        vector<bool>vis(n+1);
        while(dq.size()){
            a=dq.front().first;
            int b=dq.front().second;
            dq.pop_front();
            if(vis[a])continue;
            vis[a]=1;
            for(auto &i:vct[a])dq.push_back({i,b+1});
        }
        vector<int>topo(n+1);
        for(int i=1;i<=n;i++){
            for(auto &w:vec[i]){
                if(vis[w])topo[i]++;
            }
        }
        dq.push_back({f,0});
        while(dq.size()){
            a=dq.front().first;
            int b=dq.front().second;
            dq.pop_front();
            if(v[a])ans=max(ans,b);
            for(auto &i:vct[a]){
                if(topo[i]==1)dq.push_back({i,b+1});
                else topo[i]--;
            }
        }
        cout<<ans<<endl;
    }
}

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