Submission #724005

#	Time	Username	Problem	Language	Result	Execution time	Memory
724005		urosk	Crocodile's Underground City (IOI11_crocodile)	C++14	100 / 100	516 ms	97444 KiB

crocodile

#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(cur2,cur1,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({-d[s][1],-tmp,s});
            }else if(tmp<d[s][1]){
                d[s][1] = tmp;
                pq.push({-tmp,-d[s][0],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: 46 / 46
• Subtask 2: 43 / 43
• Subtask 3: 11 / 11