oj.uz

Submission #385288

# Submission time Handle Problem Language Result Execution time Memory
385288 2021-04-04T03:09:45 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;

bool mini(int &a, int b)
{
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

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 + 2;
            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];
}

Compilation message

crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:52:17: warning: unused variable 'w' [-Wunused-variable]
   52 |             int w = e.se;
      |                 ^

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 -