Submission #568193

#	Time	Username	Problem	Language	Result	Execution time	Memory
568193		n0sk1ll	Crocodile's Underground City (IOI11_crocodile)	C++17	46 / 100	146 ms	262144 KiB

crocodile

#include "crocodile.h"

#include <bits/stdc++.h>

#define xx first
#define yy second

using namespace std;
long long int typedef li;

vector<vector<pair<int,int>>> g(100003);
li dp[100003];

void dfs(int p, int q)
{
    if (g[p].size()==1) return;

    vector<li> vals;
    for (auto it : g[p]) if (it.yy!=q)
    {
        dfs(it.yy,p);
        vals.push_back(dp[it.yy]+it.xx);
    }

    sort(vals.begin(),vals.end());
    dp[p]=vals[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]].push_back({L[i],R[i][1]});
        g[R[i][1]].push_back({L[i],R[i][0]});
    }

    dfs(0,-1);
    return dp[0];
}

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