oj.uz

Submission #16284

# Submission time Handle Problem Language Result Execution time Memory
16284 2015-08-20T01:13:39 Z khsoo01 Crocodile's Underground City (IOI11_crocodile) C++
100 / 100
 784 ms 185352 KB 
#include<bits/stdc++.h>
#define ll long long
#include "crocodile.h"
#define INF 987654321987654321ll
using namespace std;
priority_queue<pair<ll,ll> >pq;
vector<ll>cg[100005],cv[100005];
ll n,m,k,p[100005],cval,cidx;
ll mn[100005][2];
bool vis[100005];

bool update(ll idx,ll val) {
    if(mn[idx][0]>val) {
        mn[idx][1]=mn[idx][0];
        mn[idx][0]=val;
        return true;
    }
    if(mn[idx][1]>val) {
        mn[idx][1]=val;
        return true;
    }
    return false;
}

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
    ll i; n=N; m=M; k=K;
    for(i=0;i<n;i++) {
        mn[i][0]=INF;
        mn[i][1]=INF;
    }
    for(i=0;i<k;i++) {
        p[i]=P[i];
        mn[p[i]][0]=mn[p[i]][1]=0;
        pq.push({0,p[i]});
    }
    for(i=0;i<m;i++) {
        cg[R[i][0]].push_back(R[i][1]);
        cv[R[i][0]].push_back(L[i]);
        cg[R[i][1]].push_back(R[i][0]);
        cv[R[i][1]].push_back(L[i]);
    }
    while(!pq.empty()) {
        cval=-pq.top().first;
        cidx=pq.top().second;
        pq.pop();
        if(vis[cidx])continue;
        vis[cidx]=true;
        for(i=0;i<cg[cidx].size();i++) {
            if(!vis[cg[cidx][i]] && update(cg[cidx][i],cv[cidx][i]+cval) && mn[cg[cidx][i]][1]!=INF) {
                pq.push({-mn[cg[cidx][i]][1],cg[cidx][i]});
            }
        }
    }
    return mn[0][1];
}

Subtask #1
46.0 / 46.0

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

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 126500 KB Output is correct
2 Correct 0 ms 126236 KB Output is correct
3 Correct 0 ms 126236 KB Output is correct
4 Correct 0 ms 126632 KB Output is correct
5 Correct 3 ms 126764 KB Output is correct
6 Correct 0 ms 126236 KB Output is correct
7 Correct 0 ms 126236 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 662 ms 177660 KB Output is correct
2 Correct 115 ms 135608 KB Output is correct
3 Correct 162 ms 137060 KB Output is correct
4 Correct 784 ms 185352 KB Output is correct
5 Correct 483 ms 171900 KB Output is correct
6 Correct 72 ms 130724 KB Output is correct
7 Correct 393 ms 162948 KB Output is correct