Submission #1361839

#	Time	Username	Problem	Language	Result	Execution time	Memory
1361839		mayac	Currents (EGOI25_currents)	C++20	100 / 100	275 ms	29820 KiB

Main

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

int main(){
    int n,m,a,b;
    cin>>n>>m;
    vector<vector<int>> g(n),g2(n);
    for(int i=0;i<m;i++){
        cin>>a>>b;
        g[a].push_back(b);
        g2[b].push_back(a);
    }
    vector<int> d0(n,n),dn(n,n),ans(n,2*n);
    d0[0]=0;
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q;
    q.push({0,0});
    while(!q.empty()){
        a=q.top().second;q.pop();
        for(int u:g[a]){
            if(d0[u]>d0[a]+1){
                d0[u]=d0[a]+1;
                q.push({d0[u],u});
            }
        }
    }
    q.push({0,n-1});
    while(!q.empty()){
        a=q.top().second;q.pop();
        for(int u:g2[a]){
            if(dn[u]>dn[a]+1){
                dn[u]=dn[a]+1;
                q.push({dn[u],u});
            }
        }
    }
    vector<bool> vis(n,0);
    for(int u:g2[n-1]){
        ans[u]=max(1,d0[u]);
        q.push({ans[u],u});
    }
    //cout<<"!\n";
    while(!q.empty()){
        a=q.top().second;q.pop();
        if(!vis[a]){
            vis[a]=1;
            ans[a]=max(ans[a],d0[a]);
            //cout<<a<<" "<<ans[a]<<"\n";
            for(int u:g2[a]){
                if(!vis[u]){
                ans[u]=min(ans[a]+1,ans[u]);
                q.push({ans[u],u});
                }
            }
        }
    }
    for(int i=0;i<n-1;i++){
        cout<<max(d0[i],ans[i])<<" ";
    }
}

• Subtask 1: 0 / 0
• Subtask 2: 12 / 12
• Subtask 3: 15 / 15
• Subtask 4: 20 / 20
• Subtask 5: 29 / 29
• Subtask 6: 24 / 24