Submission #435719

#	Time	Username	Problem	Language	Result	Execution time	Memory
435719		illyakr	Crocodile's Underground City (IOI11_crocodile)	C++14	46 / 100	4 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 dfs(int v, int sum) {
    if (cn[v]) {
        ans[v] = 0;
        return 0;
    }
    if (used[v])return 1010101010;
    used[v] = true;

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

    return Mn2;
}
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));
    return dfs(1, 0);
}


/**
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 'int dfs(int, int)':
crocodile.cpp:19:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   19 |     for (auto [to, c] : g[v]) {
      |               ^

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