oj.uz

Submission #18423

# Submission time Handle Problem Language Result Execution time Memory
18423 2016-02-01T07:14:05 Z tlwpdus Crocodile's Underground City (IOI11_crocodile) C++
100 / 100
 697 ms 187744 KB 
#include "crocodile.h"
#include<vector>
#include<queue>
#include<stdio.h>

using namespace std;

typedef long long ll;

struct edge {
    int j;
    ll w;
    edge(int j, ll w):j(j),w(w){}
    edge(){}
};

struct dijk {
    int loc;
    ll w;
    dijk(int l, ll w):loc(l),w(w){}
    dijk(){}
    inline bool operator < (const dijk &A) const {return w>A.w;}
};

vector<edge> lis[100100];
priority_queue<dijk> pq;
ll dist[100100][2];
bool visit[100100];

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
    int i;
    for (i=0;i<N;i++) dist[i][0] = dist[i][1] = 1LL<<60;
    for (i=0;i<M;i++) {
        lis[R[i][0]].push_back(edge(R[i][1],L[i]));
        lis[R[i][1]].push_back(edge(R[i][0],L[i]));
    }
    for (i=0;i<K;i++) {
        pq.push(dijk(P[i],0));
        dist[P[i]][0] = dist[P[i]][1] = 0;
    }
    while(!pq.empty()) {
        dijk tmp = pq.top();
        pq.pop();
        int here = tmp.loc;
        if (visit[here]) continue;
        if (dist[here][1]!=tmp.w) continue;
        visit[here] = true;
        for (i=0;i<lis[here].size();i++) {
            int there = lis[here][i].j;
            int w = lis[here][i].w;
            if (visit[there]) continue;
            if (dist[there][0]>w+tmp.w) {
                dist[there][1] = dist[there][0];
                dist[there][0] = w+tmp.w;
                pq.push(dijk(there,dist[there][1]));
            }
            else if (dist[there][1]>w+tmp.w) {
                dist[there][1] = w+tmp.w;
                pq.push(dijk(there,dist[there][1]));
            }
        }
    }
    return dist[0][1];
}

Subtask #1
46.0 / 46.0

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

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 123236 KB Output is correct
2 Correct 0 ms 122972 KB Output is correct
3 Correct 0 ms 123112 KB Output is correct
4 Correct 0 ms 123368 KB Output is correct
5 Correct 7 ms 123500 KB Output is correct
6 Correct 0 ms 122972 KB Output is correct
7 Correct 2 ms 122972 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 570 ms 178248 KB Output is correct
2 Correct 125 ms 133860 KB Output is correct
3 Correct 163 ms 136032 KB Output is correct
4 Correct 697 ms 187744 KB Output is correct
5 Correct 352 ms 168756 KB Output is correct
6 Correct 47 ms 127920 KB Output is correct
7 Correct 363 ms 159836 KB Output is correct