Submission #341876

#	Time	Username	Problem	Language	Result	Execution time	Memory
341876		bigDuck	Crocodile's Underground City (IOI11_crocodile)	C++14	100 / 100	994 ms	59908 KiB

crocodile

#include "crocodile.h"
#include<bits/stdc++.h>
using namespace std;
#define INIT  ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define mp make_pair
#define pb push_back
#define ft first
#define sc second
#define ll long long
#define pii pair<int, int>
#define count_bits __builtin_popcount


int p[100010], k;
vector<pii> g[100010];

bool v[100010];
int d[100010][2];

void tricky_dijkstra(){
multiset<pii> ms;

for(int i=1; i<=k; i++){
    ms.insert({0, p[i]});
    v[p[i]]=true;
}

while(!ms.empty()){
    auto pr=(*ms.begin()); ms.erase(ms.begin());
    int node=pr.sc, d0=pr.ft;
    v[node]=true;
    if(node==0){
        break;
    }
    for(auto pr:g[node]){
        int u=pr.ft, c=pr.sc;
        if(!v[u]){
            auto it=ms.find({d[u][1], u});
            if(it==ms.end()){
                if(d[u][0]==0){
                    d[u][0]=d0+c;
                }
                else{
                    d[u][1]=d0+c;
                    if(d[u][1]<d[u][0]){
                        swap(d[u][1], d[u][0]);
                    }
                    ms.insert({d[u][1], u});
                }
            }
            else{
                if( (d0+c)<d[u][1]  ){
                    d[u][1]=(d0+c);
                    if(d[u][1]<d[u][0]){
                        swap(d[u][1], d[u][0]);
                    }
                    ms.erase(it);
                    ms.insert({d[u][1], u});
                }
            }
        }
    }
}






}



int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){

    k=K;
    for(int i=0; i<k; i++){
        p[i+1]=P[i];
    }

    for(int i=0; i<M; i++){
        int u=R[i][0], v=R[i][1], c=L[i];
        g[u].pb({v, c});
        g[v].pb({u, c});
    }
    tricky_dijkstra();
    return d[0][1];
}

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