Submission #385297

#	Time	Username	Problem	Language	Result	Execution time	Memory
385297		ngpin04	Crocodile's Underground City (IOI11_crocodile)	C++14	89 / 100	588 ms	47332 KiB

crocodile

#include <bits/stdc++.h>
#include "crocodile.h"
//#include "crocodile.cpp"
//#include "grader.cpp"
#define fi first
#define se second
#define mp make_pair
using namespace std;
const int NN = 1e5 + 5;
const int oo = 1e9 + 1;
 
vector <pair <int, int>> adj[NN];
 
int dis[NN][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;
        if (j == 1)
            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));
            if (v == 0){
                //cerr << u << " " << v << " " << w << endl;
                //for (int i = 0; i < 3; i++)
                //    cerr << dis[0][i] << " ";
                //cerr << endl;
            }
        }
    }
    assert(dis[0][1] < oo);
    return dis[0][1];
}

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