Submission #689385

#	Time	Username	Problem	Language	Result	Execution time	Memory
689385		zeroesandones	Crocodile's Underground City (IOI11_crocodile)	C++17	46 / 100	129 ms	262144 KiB

crocodile

#include <bits/stdc++.h>
#include "crocodile.h"
using namespace std;

using ll = long long;
using vi = vector<ll>;
using pi = pair<ll, ll>;

#define fr first
#define sc second
#define pb emplace_back

const int mxN = 1005;
vector<pi> adj[mxN];
ll dp[mxN] = {};

void dfs(ll x, ll p) {
    dp[x] = 0;
    vi curr;
    for(auto [i, w] : adj[x]) {
        if(i == p) continue;
        dfs(i, x);
        curr.pb(dp[i] + w);
    }

    if(curr.empty()) return;
    sort(curr.begin(), curr.end());
    dp[x] = curr[1];
}

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
    for(int i = 0; i < M; ++i) {
        adj[R[i][0]].pb(R[i][1], L[i]);
        adj[R[i][1]].pb(R[i][0], L[i]);
    }

    dfs(0, -1);
    return dp[0];
}

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