Submission #1221323

#	Time	Username	Problem	Language	Result	Execution time	Memory
1221323		enzy	Crocodile's Underground City (IOI11_crocodile)	C++20	100 / 100	505 ms	70104 KiB

crocodile

//#include "crocodile.h"
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1e5+10;
const int inf=1e9+7;
ll dist[maxn][2], n;
vector<pair<int,ll>>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<ll,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,ll> 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]+1);
    dijkstra(aux);
    //assert(dist[1][1]<=1000000000);
    int resp=dist[1][1];
    return resp;
}

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