Submission #1361670

#	Time	Username	Problem	Language	Result	Execution time	Memory
1361670		mayac	Currents (EGOI25_currents)	C++20	27 / 100	214 ms	27232 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,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});
            }
        }
    }
    for(int u:g2[n-1]){
        dn[u]=d0[u];
        q.push({dn[u],u});
    }
    dn[n-1]=0;
    while(!q.empty()){
        a=q.top().second;q.pop();
        for(int u:g2[a]){
            if(dn[u]>dn[a]+1&&dn[a]+1>d0[u]){
                dn[u]=dn[a]+1;
                q.push({dn[u],u});
            }
        }
    }
    for(int i=0;i<n-1;i++){
        cout<<max(dn[i],1)<<" ";
    }
}

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