Submission #385289

#	Time	Username	Problem	Language	Result	Execution time	Memory
385289		ngpin04	Crocodile's Underground City (IOI11_crocodile)	C++14	0 / 100	2 ms	2668 KiB

crocodile

#include <bits/stdc++.h>
#include "crocodile.h"
#define fi first
#define se second
#define mp make_pair
using namespace std;
const int N = 1e5 + 5;
const int oo = 1e9 + 1;

vector <pair <int, int>> adj[N];

int dis[N][3];
int n;

int travel_plan(int n, int m, int r[][2], int l[], int k, int p[])
{
    for (int i = 0; i < m; i++) {
        int u = r[i][0];
        int v = r[i][1];
        int w = l[i];
        adj[u].push_back(mp(v, w));
        adj[v].push_back(mp(u, w));
    }
    for (int i = 0; i < n; i++)
    for (int j = 0; j < 3; j++)
        dis[i][j] = oo;

    priority_queue <pair <int, int>> heap;

    for (int i = 0; i < k; i++)
    for (int j = 0; j < 2; j++) {
        dis[p[i]][j] = 0;
        heap.push(mp(0, p[i]));
    }
    while (heap.size()) {
        int u = heap.top().se;
        int cur = -heap.top().fi;
        heap.pop();
        if (dis[u][1] != cur)
            continue;
        for (pair <int, int> e : adj[u]) {
            int v = e.fi;
            int w = e.se;
            bool ok = false;
            dis[v][2] = cur + w;
            for (int i = 2; i >= 1; i--)
                if (dis[v][i] < dis[v][i - 1])
                    swap(dis[v][i], dis[v][i - 1]), ok = true;
            if (ok)
                heap.push(mp(-dis[v][1], v));
        }
    }
    return dis[0][1];
}

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