oj.uz

Submission #723990

# Submission time Handle Problem Language Result Execution time Memory
723990 2023-04-14T15:04:07 Z urosk Crocodile's Underground City (IOI11_crocodile) C++14
0 / 100
 7 ms 2772 KB 
#include "crocodile.h"
#include <bits/stdc++.h>
#define dbg(x) cerr<<#x<<": "<<x<<endl;
#define ll long long
#define endl '\n'
#define pll pair<ll,ll>
#define fi first
#define sc second
#define pb push_back
#define llinf 1000000000LL
using namespace std;
#define maxn 100005
 
ll n,m,k;
vector<pll> g[maxn];
ll d[maxn][2];
bool ok[maxn];
 
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
    n = N;
    m = M;
    k = K;
    for(ll i = 0;i<m;i++){
        ll x = R[i][0],y = R[i][1];
        x++; y++;
        ll w = L[i];
        g[x].pb({y,w});
        g[y].pb({x,w});
    }
    priority_queue<pll> pq;
    for(ll i = 1;i<=n;i++) d[i][0] = d[i][1] = llinf;
    for(ll i = 1;i<=k;i++){
        ll x = P[i-1] + 1;
        ok[x] = 1;
        d[x][0] = d[x][1] = 0;
        pq.push({0,x});
    }
    while(pq.size()){
        pll p = pq.top();
        pq.pop();
        ll u = p.sc;
        ll cur = -p.fi;
        if(cur>d[u][1]) continue;
        if(!ok[u]&&cur==d[u][0]) continue;
        for(pll p : g[u]){
            ll s = p.fi;
            ll w = p.sc;
            if(cur+w<d[s][0]){
                d[s][1] = d[s][0];
                d[s][0] = cur + w;
                pq.push({-d[s][0],s});
            }else if(cur+w<d[s][1]){
                d[s][1] = cur + w;
                pq.push({-d[s][1],s});
            }
        }
    }
    for(ll i = 1;i<=n;i++) cerr<<d[i][0]<< " "<<d[i][1]<<endl;
    return d[1][1];
}
/**
5 7 2
0 2 4
0 3 3
3 2 2
2 1 10
0 1 100
0 4 7
3 4 9
1 3
14
 
 
**/

Subtask #1
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 4 ms 2644 KB Output is correct
4 Incorrect 7 ms 2772 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 4 ms 2644 KB Output is correct
4 Incorrect 7 ms 2772 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 4 ms 2644 KB Output is correct
4 Incorrect 7 ms 2772 KB Output isn't correct
5 Halted 0 ms 0 KB -