Submission #434840

#	Time	Username	Problem	Language	Result	Execution time	Memory
434840		illyakr	Crocodile's Underground City (IOI11_crocodile)	C++14	46 / 100	2060 ms	3276 KiB

crocodile

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

vector<pair<int, int> > g[101010];
bool used[101010];
int ans[101010];
bool cn[101010];
int sv = -1;
void dfs(int v, int sum) {
    if (used[v])return;
//    if (ans[v] != -1){ans[v] = max(ans[v], sum);return;}
    if (cn[v]) {
        ans[v] = 0;
        sv = sum;
        return;
    }
    used[v] = true;

    int Mn1 = 1010101010;
    int Mn2 = 1010101010;
    for (auto [to, c] : g[v]) {
        if (used[to])continue;
        dfs(to, sum + c);
        if (ans[to] + c < Mn1) {
            Mn2 = Mn1;
            Mn1 = ans[to] + c;
        } else if (ans[to] + c < Mn2) {
            Mn2 = ans[to] + c;
        }
    }

    ans[v] = Mn2;
    used[v] = false;
}
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
    for (int i = 0; i < M; i++) {
        g[R[i][0] + 1].push_back({R[i][1] + 1, L[i]});
        g[R[i][1] + 1].push_back({R[i][0] + 1, L[i]});
    }
    for (int i = 0; i < K; i++)
        cn[P[i] + 1] = true;
    memset(ans, -1, sizeof(ans));
    dfs(1, 0);
    return ans[1];
}


/**
5 4 3
0 1 2
0 2 3
3 2 1
2 4 4
1 3 4
7

5 7 2
0 2 4
0 3 3
3 2 2
2 1 10
0 1 100
0 4 7
3 4 9
1 3
14
*/

Compilation message (stderr)

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

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