oj.uz

Submission #385289

# Submission time Handle Problem Language Result Execution time Memory
385289 2021-04-04T03:11:47 Z ngpin04 Crocodile's Underground City (IOI11_crocodile) C++14
0 / 100
 2 ms 2668 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2668 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 43.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2668 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2668 KB Output isn't correct
2 Halted 0 ms 0 KB -