Submission #419446

#	Time	Username	Problem	Language	Result	Execution time	Memory
419446		snasibov05	Crocodile's Underground City (IOI11_crocodile)	C++14	46 / 100	4 ms	560 KiB

crocodile

#include "crocodile.h"
#include <vector>
#include <algorithm>

using namespace std;

#define pb push_back
#define pii pair<int, int>
#define f first;
#define s second;
#define oo 1000000000

vector<vector<pii>> ed;
vector<bool> ext;
vector<bool> visited;
vector<int> res;

int dfs(int v, int pr, int d){
    visited[v] = true;
    vector<int> cur;
    for (auto [x, l] : ed[v]){
        if (x == pr) continue;
        if (ext[x]) cur.pb(d + l);
        else if (visited[x]) cur.pb(res[x]);
        else cur.pb(dfs(x, v, d + l));
    }

    sort(cur.begin(), cur.end());
    if (cur.size() <= 1) return res[v] = oo;
    return res[v] = cur[1];
}

int travel_plan(int n, int m, int r[][2], int l[], int k, int p[]){

    ed.resize(n);
    ext.resize(n);
    visited.resize(n);
    res.resize(n);

    for (int i = 0; i < m; ++i) {
        ed[r[i][0]].pb({r[i][1], l[i]});
        ed[r[i][1]].pb({r[i][0], l[i]});
    }

    for (int i = 0; i < k; ++i) {
        ext[p[i]] = true;
    }

    int ans = dfs(0, -1, 0);

    return ans;

}

Compilation message (stderr)

crocodile.cpp: In function 'int dfs(int, int, int)':
crocodile.cpp:21:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   21 |     for (auto [x, l] : ed[v]){
      |               ^

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