Submission #1190941

#	Time	Username	Problem	Language	Result	Execution time	Memory
1190941		zh_h	Crocodile's Underground City (IOI11_crocodile)	C++20	46 / 100	175 ms	327680 KiB

crocodile

#include <bits/stdc++.h>
#define pb push_back
#define lint long long int
using namespace std;

int _n, _m, _k;
vector<bool> is_exit;
vector<int> dp;
vector<vector<pair<int, int>>> edge;

void dfs(int v, int p) {
    if (is_exit[v]) {dp[v] = 0; return;}
    int min1=1e9, min2=1e9;
    for (auto [child, w] : edge[v]) {
        if (child == p) continue;
        dfs(child, v);
        if (dp[child]+w <= min1) {
            min2 = min1;
            min1 = dp[child]+w;
        }
        else if (dp[child]+w <= min2) {
            min2 = dp[child]+w;
        }
    }
    dp[v] = min2;
}

int travel_plan (int n, int m, int r[][2], int l[], int k, int p[]) {
    _n = n; _m = m; _k = k;
    edge.resize(n);
    for (int i = 0; i < m; i ++) {
        edge[r[i][0]].pb({r[i][1], l[i]});
        edge[r[i][1]].pb({r[i][0], l[i]});
    }

    is_exit.resize(n, false);
    for (int i = 0; i < k; i ++) {
        is_exit[p[i]] = true;
    }

    dp.resize(n, 1e9);
    dfs(0, -1);

    return dp[0];
}

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