Submission #769925

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

crocodile

#include "crocodile.h"
//#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using arr = array<int, 2>;
using arrr = array<int, 3>;

constexpr int maxn = 1e3;

basic_string <arr> adj[maxn];


bool exit_node[maxn] = { 0 };
int val[maxn] = { 0 };

int dfs(int p, int par)
{
    if (exit_node[p]) return 0;

    multiset <int, greater<int>> s; // Value

    for (arr i : adj[p])
    {
        if (i[0] == par) continue;

        s.insert(dfs(i[0], p) + i[1]);

        if (s.size() > 2) s.erase(s.begin());
    }

    val[p] = *s.begin();
    return val[p];
}


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]].push_back({R[i][1], L[i]});
        adj[R[i][1]].push_back({R[i][0], L[i]});
    }  

    for (int i = 0; i < k; i++) exit_node[P[i]] = true;


    return dfs(0, -1);
}

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