oj.uz

Submission #155375

# Submission time Handle Problem Language Result Execution time Memory
155375 2019-09-27T17:02:48 Z arnold518 Crocodile's Underground City (IOI11_crocodile) C++14
100 / 100
 1247 ms 76188 KB 
#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1e5;
const ll INF = 1e15;

int N, M, K;
vector<pii> adj[MAXN+10];
ll dist[MAXN+10];
int vis[MAXN+10];

struct Queue
{
    int u; ll w;
    bool operator < (const Queue &p) const { return w>p.w; }
};

int travel_plan(int _N, int _M, int R[][2], int L[], int _K, int P[])
{
    int i, j;
    N=_N; M=_M; K=_K;

    for(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]});
    }

    priority_queue<Queue> PQ;
    for(i=0; i<K; i++) PQ.push({P[i], 0}), vis[P[i]]=1;

    while(!PQ.empty())
    {
        Queue T=PQ.top(); PQ.pop();
        if(vis[T.u]==2) continue;
        vis[T.u]++;
        if(vis[T.u]<2) continue;
        dist[T.u]=T.w;

        for(auto nxt : adj[T.u]) PQ.push({nxt.first, T.w+nxt.second});
    }
    return dist[0];
}

Compilation message

crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:25:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2680 KB Output is correct
3 Correct 4 ms 2808 KB Output is correct
4 Correct 5 ms 2808 KB Output is correct
5 Correct 5 ms 2808 KB Output is correct
6 Correct 5 ms 2808 KB Output is correct
7 Correct 5 ms 2812 KB Output is correct
8 Correct 5 ms 2812 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2680 KB Output is correct
3 Correct 4 ms 2808 KB Output is correct
4 Correct 5 ms 2808 KB Output is correct
5 Correct 5 ms 2808 KB Output is correct
6 Correct 5 ms 2808 KB Output is correct
7 Correct 5 ms 2812 KB Output is correct
8 Correct 5 ms 2812 KB Output is correct
9 Correct 7 ms 3320 KB Output is correct
10 Correct 4 ms 2680 KB Output is correct
11 Correct 5 ms 2808 KB Output is correct
12 Correct 11 ms 3704 KB Output is correct
13 Correct 10 ms 3716 KB Output is correct
14 Correct 4 ms 2680 KB Output is correct
15 Correct 5 ms 2808 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2680 KB Output is correct
3 Correct 4 ms 2808 KB Output is correct
4 Correct 5 ms 2808 KB Output is correct
5 Correct 5 ms 2808 KB Output is correct
6 Correct 5 ms 2808 KB Output is correct
7 Correct 5 ms 2812 KB Output is correct
8 Correct 5 ms 2812 KB Output is correct
9 Correct 7 ms 3320 KB Output is correct
10 Correct 4 ms 2680 KB Output is correct
11 Correct 5 ms 2808 KB Output is correct
12 Correct 11 ms 3704 KB Output is correct
13 Correct 10 ms 3716 KB Output is correct
14 Correct 4 ms 2680 KB Output is correct
15 Correct 5 ms 2808 KB Output is correct
16 Correct 1191 ms 73108 KB Output is correct
17 Correct 109 ms 10844 KB Output is correct
18 Correct 154 ms 12508 KB Output is correct
19 Correct 1247 ms 76188 KB Output is correct
20 Correct 727 ms 69784 KB Output is correct
21 Correct 58 ms 6520 KB Output is correct
22 Correct 651 ms 32920 KB Output is correct