Submission #93950

#	Time	Username	Problem	Language	Result	Execution time	Memory
93950		someone_aa	Crocodile's Underground City (IOI11_crocodile)	C++17	46 / 100	323 ms	263168 KiB

crocodile

#include "crocodile.h"
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
using namespace std;
const int maxn = 100100;
int dpf[maxn], dps[maxn];
vector<pair<int,int> > g[maxn];

void dfs(int node, int p) {
    if(g[node].size() == 1) {
        dps[node] = dpf[node] = 0LL;
        return;
    }

    vector<ll>dp;
    for(auto i:g[node]) {
        if(i.first != p) {
            dfs(i.first, node);
            dp.pb(dps[i.first] + i.second);
        }
    }

    sort(dp.begin(), dp.end());
    if(g[node].size() == 1) return;
    dpf[node] = dp[0];
    dps[node] = dp[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(mp(R[i][1], L[i]));
        g[R[i][1]].pb(mp(R[i][0], L[i]));
    }
    dfs(0, -1);
    return int(dps[0]);
}

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