Submission #291024

#	Time	Username	Problem	Language	Result	Execution time	Memory
291024		Kastanda	Crocodile's Underground City (IOI11_crocodile)	C++11	100 / 100	769 ms	52332 KiB

crocodile

// M
#include<bits/stdc++.h>
#include "crocodile.h"
using namespace std;
typedef long long ll;
const int N = 100005;
int n, m, k, M[N];
ll D[N][2];
vector < pair < int , int > > Adj[N];

int travel_plan(int _n, int _m, int R[][2], int L[], int _k, int P[])
{
        n = _n; m = _m; k = _k;
        for (int i = 0; i < m; i ++)
        {
                Adj[R[i][0]].push_back({R[i][1], L[i]});
                Adj[R[i][1]].push_back({R[i][0], L[i]});
        }

        memset(D, 63, sizeof(D));
        priority_queue < pair < ll , int > > Pq;
        for (int i = 0; i < k; i ++)
                D[P[i]][0] = D[P[i]][1] = 0, Pq.push({0, P[i]});
        while (Pq.size())
        {
                int v = Pq.top().second;
                Pq.pop();
                if (M[v])
                        continue;
                M[v] = 1;
                for (auto e : Adj[v])
                {
                        int u = e.first;
                        int w = e.second;
                        if (D[u][0] > D[v][1] + w)
                        {
                                D[u][1] = D[u][0];
                                D[u][0] = D[v][1] + w;
                                Pq.push({-D[u][1], u});
                        }
                        else if (D[u][1] > D[v][1] + w)
                        {
                                D[u][1] = D[v][1] + w;
                                Pq.push({-D[u][1], u});
                        }
                }
        }
        return D[0][1];
}

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