Submission #892536

#	Time	Username	Problem	Language	Result	Execution time	Memory
892536		TahirAliyev	Crocodile's Underground City (IOI11_crocodile)	C++17	100 / 100	630 ms	88120 KiB

crocodile

#include "crocodile.h"
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define pii pair<ll, ll>
#define oo 1e18

const int MAX = 1e5 + 5;
int n, m;

vector<int> esc;

vector<pii> g[MAX];

ll dp[MAX][2];

void djikstra(){
    for(int i = 0; i < n; i++){
        dp[i][0] = oo;
        dp[i][1] = oo;
    }
    set<pii> s;
    for(int e : esc){
        dp[e][0] = 0;
        dp[e][1] = 0;
        s.insert({0, e});
    }
    while(s.size()){
        int a = s.begin()->second;
        s.erase(s.begin());
        for(pii to : g[a]){
            ll nw = dp[a][1] + to.second;
            if(dp[to.first][0] <= nw){
                if(dp[to.first][1] > nw){
                    s.erase({dp[to.first][1], to.first});
                    dp[to.first][1] = nw;
                    s.insert({dp[to.first][1], to.first});
                }
            }
            else{
                s.erase({dp[to.first][1], to.first});
                dp[to.first][1] = dp[to.first][0];
                s.insert({dp[to.first][1], to.first});
                dp[to.first][0] = nw;
            }
        }
    }
}

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){
    n = N, m = M;
    for(int 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(int i = 0; i < K; i++){
        esc.push_back(P[i]);
    }
    djikstra();
    return dp[0][1];
}

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