Submission #237258

#	Time	Username	Problem	Language	Result	Execution time	Memory
237258		nicolaalexandra	Crocodile's Underground City (IOI11_crocodile)	C++14	100 / 100	659 ms	47744 KiB

crocodile

#include <bits/stdc++.h>
#include "crocodile.h"
#define DIMN 100010
#define DIMM 1000010
#define INF 2000000000
using namespace std;

priority_queue <pair<int,int>, vector<pair<int,int> >, greater<pair<int,int> > > H;
vector <pair<int,int> > L[DIMN],edg[DIMN];
int f[DIMN],dist[DIMN],viz[DIMN];
pair <int,int> fth[DIMN];
struct idk{
    int mini,mini2;
} dp[DIMN];
int travel_plan (int n, int m, int r[][2], int l[], int k, int p[]){
    int i;

    for (i=0;i<m;i++){
        int x = r[i][0]+1, y = r[i][1]+1;
        L[x].push_back(make_pair(y,l[i]));
        L[y].push_back(make_pair(x,l[i]));
    }

    for (i=1;i<=n;i++)
        dp[i].mini = dp[i].mini2 = INF;

    for (i=0;i<k;i++){
        int x = p[i] + 1;
        f[x] = 1;
        H.push(make_pair(0,x));
        dp[x].mini = dp[x].mini2 = 0;
    }

    while (!H.empty()){
        int nod = H.top().second;
        int cost = H.top().first;
        H.pop();
        if (cost != dp[nod].mini2)
            continue;
        for (auto it : L[nod]){
            int vecin = it.first, new_cost = it.second;
            int aux = dp[vecin].mini2;
            if (dp[nod].mini2 + new_cost < dp[vecin].mini){
                dp[vecin].mini2 = dp[vecin].mini;
                dp[vecin].mini = dp[nod].mini2 + new_cost;
            } else {
                if (dp[nod].mini2 + new_cost < dp[vecin].mini2)
                    dp[vecin].mini2 = dp[nod].mini2 + new_cost;
            }

            if (dp[vecin].mini2 != aux)
                H.push(make_pair(dp[vecin].mini2,vecin));

        }
    }

    return dp[1].mini2;

}

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