oj.uz

Submission #724003

# Submission time Handle Problem Language Result Execution time Memory
724003 2023-04-14T15:20:58 Z urosk Crocodile's Underground City (IOI11_crocodile) C++14
0 / 100
 2 ms 2644 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<tuple<ll,ll,ll> > 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;
        d[x][0] = d[x][1] = 0;
        pq.push({0,0,x});
    }
    while(pq.size()){
        auto p = pq.top();
        pq.pop();
        ll u,cur1,cur2;
        tie(cur1,cur2,u) = p;
        cur1 = -cur1;
        cur2 = -cur2;
        if(cur2!=d[u][1]||cur1!=d[u][0]) continue;
        for(pll p : g[u]){
            ll s = p.fi;
            ll w = p.sc;
            ll tmp = cur2 + w;
            if(tmp<d[s][0]){
                d[s][1] = d[s][0];
                d[s][0] = tmp;
                pq.push({-tmp,-d[s][1],s});
            }else if(tmp<d[s][1]){
                d[s][1] = tmp;
                pq.push({-d[s][0],-tmp,s});
            }
        }
    }
    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

5 4 3
0 1 2
0 2 3
3 2 1
2 4 4
1 3 4
7
**/

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 Incorrect 2 ms 2644 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 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Incorrect 2 ms 2644 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 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Incorrect 2 ms 2644 KB Output isn't correct
4 Halted 0 ms 0 KB -