Submission #391715

#	Time	Username	Problem	Language	Result	Execution time	Memory
391715		cpp219	Crocodile's Underground City (IOI11_crocodile)	C++14	100 / 100	1281 ms	84980 KiB

crocodile

#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 = 1e9;
//#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||(a.w2 == b.w2 && a.w1 < b.w1)||(a.w2 == b.w2 && a.w1 == b.w1 && a.cur < b.cur);
}
set<Node> s;

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},s.insert({i,0,0});
    while(!s.empty()){
        Node t = *s.begin(); s.erase(s.begin());
        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){
                s.erase({v,d[v].fs,d[v].sc});
                update(d[v],cost + L); s.insert({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: 46 / 46
• Subtask 2: 43 / 43
• Subtask 3: 11 / 11