oj.uz

Submission #115525

# Submission time Handle Problem Language Result Execution time Memory
115525 2019-06-08T04:24:22 Z arnold518 Crocodile's Underground City (IOI11_crocodile) C++14
100 / 100
 794 ms 66312 KB 
#include <bits/stdc++.h>
#include "crocodile.h"
using namespace std;

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

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

vector<pii> adj[MAXN+10];
pll dist[MAXN+10];
bool vis[MAXN+10];

struct Queue
{
    int v;
    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;
    for(i=0; i<M; i++)
    {
        int u=R[i][0], v=R[i][1], w=L[i];
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }

    priority_queue<Queue> PQ;

    for(i=0; i<N; i++) dist[i]={INF, INF};
    for(i=0; i<K; i++) dist[P[i]]={0, 0}, PQ.push({P[i], 0});

    while(!PQ.empty())
    {
        Queue T=PQ.top();
        PQ.pop();
        int now=T.v;

        if(vis[now]) continue;
        vis[now]=true;

        for(pii nxt : adj[now])
        {
            if(dist[nxt.first].first>dist[now].second+nxt.second)
            {
                dist[nxt.first].second=dist[nxt.first].first;
                dist[nxt.first].first=dist[now].second+nxt.second;
                PQ.push({nxt.first, dist[nxt.first].second});
            }
            else if(dist[nxt.first].second>dist[now].second+nxt.second)
            {
                dist[nxt.first].second=dist[now].second+nxt.second;
                PQ.push({nxt.first, dist[nxt.first].second});
            }
        }
    }

    return dist[0].second;
}

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 5 ms 2688 KB Output is correct
2 Correct 4 ms 2688 KB Output is correct
3 Correct 4 ms 2688 KB Output is correct
4 Correct 5 ms 2816 KB Output is correct
5 Correct 5 ms 2728 KB Output is correct
6 Correct 4 ms 2816 KB Output is correct
7 Correct 5 ms 2816 KB Output is correct
8 Correct 6 ms 2816 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2688 KB Output is correct
2 Correct 4 ms 2688 KB Output is correct
3 Correct 4 ms 2688 KB Output is correct
4 Correct 5 ms 2816 KB Output is correct
5 Correct 5 ms 2728 KB Output is correct
6 Correct 4 ms 2816 KB Output is correct
7 Correct 5 ms 2816 KB Output is correct
8 Correct 6 ms 2816 KB Output is correct
9 Correct 7 ms 2944 KB Output is correct
10 Correct 4 ms 2688 KB Output is correct
11 Correct 5 ms 2816 KB Output is correct
12 Correct 9 ms 3200 KB Output is correct
13 Correct 9 ms 3200 KB Output is correct
14 Correct 4 ms 2688 KB Output is correct
15 Correct 5 ms 2788 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2688 KB Output is correct
2 Correct 4 ms 2688 KB Output is correct
3 Correct 4 ms 2688 KB Output is correct
4 Correct 5 ms 2816 KB Output is correct
5 Correct 5 ms 2728 KB Output is correct
6 Correct 4 ms 2816 KB Output is correct
7 Correct 5 ms 2816 KB Output is correct
8 Correct 6 ms 2816 KB Output is correct
9 Correct 7 ms 2944 KB Output is correct
10 Correct 4 ms 2688 KB Output is correct
11 Correct 5 ms 2816 KB Output is correct
12 Correct 9 ms 3200 KB Output is correct
13 Correct 9 ms 3200 KB Output is correct
14 Correct 4 ms 2688 KB Output is correct
15 Correct 5 ms 2788 KB Output is correct
16 Correct 606 ms 58116 KB Output is correct
17 Correct 99 ms 16880 KB Output is correct
18 Correct 130 ms 18288 KB Output is correct
19 Correct 794 ms 66312 KB Output is correct
20 Correct 321 ms 49784 KB Output is correct
21 Correct 48 ms 8568 KB Output is correct
22 Correct 343 ms 46872 KB Output is correct