Submission #434841

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

crocodile

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

vector<pair<int, int> > g[101010];
bool used[101010];
pair<int, int> ans[101010];
bool cn[101010];
int sv = -1;
void dfs(int v, int sum) {
    if (used[v])return;
    if (cn[v]) {
        ans[v] = {0, sum};
        sv = sum;
        return;
    }
    if (ans[v].first != -1) {
//        ans[v] = max(ans[v], 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].first + c < Mn1) {
            Mn2 = Mn1;
            Mn1 = ans[to].first + c;
        } else if (ans[to].first + c < Mn2) {
            Mn2 = ans[to].first + c;
        }
    }

    ans[v] = {Mn2, sum};
    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].first;
}


/**
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:26:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   26 |     for (auto [to, c] : g[v]) {
      |               ^
crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:47:32: warning: 'void* memset(void*, int, size_t)' writing to an object of type 'struct std::pair<int, int>' with no trivial copy-assignment [-Wclass-memaccess]
   47 |     memset(ans, -1, sizeof(ans));
      |                                ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:64,
                 from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from crocodile.cpp:1:
/usr/include/c++/10/bits/stl_pair.h:211:12: note: 'struct std::pair<int, int>' declared here
  211 |     struct pair
      |            ^~~~

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