Submission #115149

#	Time	Username	Problem	Language	Result	Execution time	Memory
115149		songc	Crocodile's Underground City (IOI11_crocodile)	C++14	89 / 100	2051 ms	80688 KiB

crocodile

#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, LL> pii;

int N, M;
vector<pii> G[101010];
LL F[101010], S[101010];
bool chk[101010];

int travel_plan(int n, int m, int r[][2], int l[], int k, int p[])
{
    N=n, M=m;
    for (int i=0; i<M; i++){
        G[r[i][0]].push_back(pii(r[i][1], l[i]));
        G[r[i][1]].push_back(pii(r[i][0], l[i]));
    }
    for (int i=0; i<k; i++) {
        chk[p[i]] = true;
        for (pii v : G[p[i]]){
            if (!F[v.first] || F[v.first] > v.second) S[v.first] = F[v.first], F[v.first] = v.second;
            else if (!S[v.first] || S[v.first] > v.second) S[v.first] = v.second;
        }
    }
    while(1){
        LL Min=1234567890123456;
        int u=-1;
        for (int j=0; j<N; j++) if (!chk[j] && S[j] && Min > S[j]) Min = S[j], u = j;
        if (u==-1) break;
        chk[u] = true;
        for (pii v : G[u]){
            if (!F[v.first] || F[v.first] > v.second+S[u]) S[v.first] = F[v.first], F[v.first] = v.second+S[u];
            else if (!S[v.first] || S[v.first] > v.second+S[u]) S[v.first] = v.second+S[u];
        }
    }
    return S[0];
}

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