Submission #729990

#	Time	Username	Problem	Language	Result	Execution time	Memory
729990		hoainiem	Crocodile's Underground City (IOI11_crocodile)	C++14	100 / 100	464 ms	81080 KiB

crocodile

#include "crocodile.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define nmax 100008
const long long inf = 1e18;
using namespace std;
typedef pair<long long, long long> pii;
pii operator+(pii x, long long y){
    return (y <= x.fi) ? make_pair(y, x.fi) : ((y < x.se) ? make_pair(x.fi, y) : x);
}
int n, m;
bool kt[nmax];
pii f[nmax];
vector<pii> l[nmax];
typedef pair<pii, int> ppiii;
struct cmp{
    bool operator()(ppiii x, ppiii y){
        return x.fi.se > y.fi.se;
    }
};
priority_queue<ppiii, vector<ppiii>, cmp> s;
bool check(pii x, pii y){
    return (x.se != y.se) ? (x.se > y.se) : (x.fi > y.fi);
}
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){
    n = N;
    m = M;
    fill(f, f + n + 1, make_pair(inf, inf));
    for (int i = 0; i < m; i++){
        int u = R[i][0], v = R[i][1], w = L[i];
        l[u].push_back({v, w});
        l[v].push_back({u, w});
    }
    for (int i = 0; i < K; i++){
        f[P[i]] = {0, 0};
        s.push({f[P[i]], P[i]});
    }
    while (!s.empty()){
        int u = s.top().se;
        pii val = s.top().fi;
        s.pop();
        if (f[u] != val)
            continue;
        if (!u)
            break;
        for (pii it : l[u]){
            ppiii v = {f[it.fi] + (val.se + it.se), it.fi};
            if (check(f[v.se], v.fi)){
                f[v.se] = v.fi;
                s.push(v);
            }
        }
    }
    return f[0].se;
}

• Subtask 1: 46 / 46
• Subtask 2: 43 / 43
• Subtask 3: 11 / 11