# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
257816 | 2020-08-04T20:50:15 Z | monus1042 | Crocodile's Underground City (IOI11_crocodile) | C++17 | 0 ms | 0 KB |
#include "crocodile.h" #include <bits/stdc++.h> using namespace std; typedef vector<int> vi; typedef long long ll; typedef pair<int,int> ii; typedef vector<ii> vii; #define pb push_back #define mkp make_pair #define all(X) X.begin(), X.end() const int MAXS = 100002; vector< pair<int, ll> > g[MAXS]; //vi lev[MAXS]; bool vis[MAXS]; //int p[MAXS]; ll acc[MAXS]; //map <int, vi> slev; // level, nodes here void dfs(int u){ vis[u] = 1; if (g[u].size() == 1) { acc[u] = 0; return; } vector<ll> adj;//w for (int i=0; i<(int)g[u].size(); i++){ int v=g[u][i].first; if (!vis[v]){ //p[v]=u; dfs(v); adj.pb(acc[v] + g[u][i].second); } } sort(all(adj)); acc[u] = adj[1]; } 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] ].pb(ii( R[i][1] , L[i])); g[ R[i][1] ].pb(ii( R[i][0] , L[i])); } dfs(0); //memset(p, -1, sizeof p); int ans=acc[u]; return ans; }