oj.uz

Submission #391691

# Submission time Handle Problem Language Result Execution time Memory
391691 2021-04-19T14:47:06 Z cpp219 Crocodile's Underground City (IOI11_crocodile) C++14
0 / 100
 2 ms 2716 KB 
#include<bits/stdc++.h>
#define ll int
#define ld long double
#define fs first
#define sc second
using namespace std;
typedef pair<long long,long long> LL;
const ll N = 1e5 + 9;
const long long inf = 1e16 + 7;
#include "crocodile.h"
vector<ll> vec;
vector<LL> g[N];
LL d[N];
ll ans;
struct Node{
    long long cur,w1,w2;
};

bool operator < (Node a,Node b){
    return a.w2 > b.w2;
}
priority_queue<Node> pq;

void update(LL &x,long long y){
    if (x.fs >= y) x.sc = x.fs,x.fs = y;
    else if (x.sc > y) x.sc = y;
}

void Dij(ll n){
    for (ll i = 0;i < n;i++) d[i] = {inf,inf};
    for (auto i : vec) d[i] = {0,0},pq.push({i,0,0});
    while(!pq.empty()){
        Node t = pq.top(); pq.pop();
        ll u = t.cur,cost = t.w2;
        for (auto i : g[u]){
            ll v = i.fs,L = i.sc;
            if (d[v].sc > cost + L){
                update(d[v],cost + L); pq.push({v,d[v].fs,d[v].sc});
            }
        }
    }
    ans = d[0].sc;
}

ll travel_plan(ll n,ll m,ll R[][2],ll lens[],ll k,ll a[]){
    for (ll i = 0;i < k;i++) vec.push_back(a[i]);
    for (ll i = 0;i < m;i++){
        ll u = R[i][0],v = R[i][1],L = lens[i];
        g[u].push_back({v,L}); g[v].push_back({u,L});
    }
    Dij(n); return ans;
}

Subtask #1
0 / 46.0

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

Subtask #2
0 / 43.0

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

Subtask #3
0 / 11.0

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