Submission #122237

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

crocodile

#include "crocodile.h"
#include <bits/stdc++.h>
#define MAXN 100005
#define MAXM 1000005

using namespace std;
typedef long long ll;

int N, M, K, R[MAXM][2], L[MAXM], P[MAXN];
vector < pair < int, ll > > Graph[MAXN];

ll dfs ( int node, int p = -1 )
{
    if ( Graph[node].size() == 1 )
        return 0;

    vector < ll > A;
    A.clear();
    for ( auto i : Graph[node] )
        if ( i.first != p )
            A.push_back ( dfs ( i.first, node ) + i.second );
    sort ( A.begin(), A.end() );
    return A[1];
}

int travel_plan ( int n, int m, int r[][2], int l[], int k, int p[] )
{
    N = n;
    M = m;
    for ( int i = 0; i < M; i++ )
        R[i][0] = r[i][0], R[i][1] = r[i][1], L[i] = l[i];
    K = k;
    for ( int i = 0; i < K; i++ )
        P[i] = p[i];

    for ( int i = 0; i < M; i++ )
    {
        Graph[R[i][0]].push_back ( {R[i][1], L[i]} );
        Graph[R[i][1]].push_back ( {R[i][0], L[i]} );
    }

    return dfs ( 0 );
}

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