Submission #1221321

#	Time	Username	Problem	Language	Result	Execution time	Memory
1221321		enzy	Crocodile's Underground City (IOI11_crocodile)	C++20	0 / 100	1 ms	2624 KiB

crocodile

#include "crocodile.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
const int inf=1e9+7;
int dist[maxn][2], n;
vector<pair<int,int>>v[maxn];
void dijkstra(vector<int> ini){
    for(int i=1;i<=n;i++) dist[i][0]=dist[i][1]=inf;
    for(int a : ini) dist[a][0]=dist[a][1]=0;
    set<pair<int,int>> s;
    for(int i=1;i<=n;i++) s.insert({dist[i][1],i});
    while(!s.empty()){
        auto f=s.begin();
        int u=f->second;
        s.erase(f);
        for(pair<int,int> p : v[u]){
            int viz=p.first, w=p.second;
            if(dist[u][1]+w<dist[viz][0]){
                s.erase({dist[viz][1],viz});
                dist[viz][1]=dist[viz][0];
                dist[viz][0]=dist[u][1]+w;
                s.insert({dist[viz][1],viz});
            }else if(dist[u][1]+w<dist[viz][1]){
                s.erase({dist[viz][1],viz});
                dist[viz][1]=dist[u][1]+w;
                s.insert({dist[viz][1],viz});
            }
        }
    }
}
int travel_plan(int N, int m, int R[][2], int L[], int k, int P[]){
    n=N;
    for(int i=0;i<m;i++){
        v[R[i][0]+1].push_back({R[i][1]+1,L[i]});
        v[R[i][1]+1].push_back({R[i][0]+1,L[i]});
    }
    vector<int> aux;
    for(int i=0;i<k;i++) aux.push_back(P[i]);
    dijkstra(aux);
    assert(dist[1][1]<=1000000000);
    return dist[1][1];
}

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