Submission #843029

#	Time	Username	Problem	Language	Result	Execution time	Memory
843029		12345678	Crocodile's Underground City (IOI11_crocodile)	C++17	0 / 100	2 ms	6756 KiB

crocodile

#include "crocodile.h"
#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int nx=1e5+5;
ll dp[nx];
vector<vector<pair<ll, ll>>> d(nx);

void dfs(int u, int p)
{
    ll mn1(LLONG_MAX), mn2(LLONG_MAX);
    for (auto [v, w]:d[u]) 
    {
        if (v==p) continue;
        dfs(v, u);
        if (dp[v]+w<mn1) swap(mn1, mn2), mn1=dp[v]+w;
        else if (dp[v]+1<mn2) mn2=dp[v]+w;
    }
    dp[u]=(d[u].size()==1)?0:mn2;
}

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
    for (int i=0; i<M; i++) d[R[i][0]].push_back({R[i][1], L[i]}), d[R[i][1]].push_back({R[i][0], L[i]});
    dfs(0, 0);
    return dp[0];
}

/*
7 6 4
0 1 1
0 2 2
1 3 3
1 4 4
2 5 5
2 6 6
3 4 5 6
0
*/

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