# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
257815 | monus1042 | Crocodile's Underground City (IOI11_crocodile) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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<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);
return (int)acc[u];
}