Submission #521129

#	Time	Username	Problem	Language	Result	Execution time	Memory
521129		krit3379	Crocodile's Underground City (IOI11_crocodile)	C++17	100 / 100	493 ms	64604 KiB

crocodile

#include<bits/stdc++.h>
using namespace std;
#define N 100005
using pii = pair<int,int>;

int mi[2][N],deg[N];
bitset<N> vis;
vector<pair<int,int>> g[N];
priority_queue<pii,vector<pii>,greater<pii>> q;

int travel_plan(int n,int m,int r[N][2],int l[N],int k,int p[N]){
    int i,a;
    for(i=0;i<m;i++){
        g[r[i][0]].push_back({r[i][1],l[i]});
        g[r[i][1]].push_back({r[i][0],l[i]});
    }
    for(i=0;i<n;i++)mi[0][i]=mi[1][i]=1e9;
    for(i=0;i<k;i++){
        q.push({0,p[i]});
        mi[0][p[i]]=mi[1][p[i]]=0;
    }
    while(!q.empty()){
        a=q.top().second;
        q.pop();
        if(vis[a])continue;
        vis[a]=true;
        for(auto [x,w]:g[a]){
            w+=mi[1][a];
            if(w<mi[0][x])swap(mi[0][x],w);
            if(w<mi[1][x])swap(mi[1][x],w);
            if(++deg[x]>=2&&!vis[x])q.push({mi[1][x],x});
        }
        if(!a)return mi[1][0];
    }
    return mi[1][0];
}

• Subtask 1: 46 / 46
• Subtask 2: 43 / 43
• Subtask 3: 11 / 11