제출 #460793

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
460793		BT21tata	Crocodile's Underground City (IOI11_crocodile)	C++17	0 / 100	3 ms	3404 KiB

crocodile

#include<bits/stdc++.h>
#include "crocodile.h"
typedef long long ll;

using namespace std;

vector<pair<ll,ll> >g[100005];
priority_queue<pair<ll,ll> >q;
ll dis[100005], ans, par[100005];
bool used[100005], ext[100005];

ll check(int v)
{
    if(ext[v]) return -1;
    vector<int>w;
    for(pair<ll, ll> u : g[v])
    {
        if(u.first!=par[v]) w.push_back(dis[u.first]); 
    }
    sort(w.begin(), w.end());
    return w[1];
}

void dfs(int v, int p)
{
    for(pair<ll, ll> u : g[v])
    {
        if(u.first!=p)
        {
            par[u.first]=v;
            dis[u.first]=dis[v]+u.second;
            dfs(u.first, v);
        }
    }
}

int travel_plan(int n, int m, int R[][2], int L[], int k, int P[])
{
    memset(dis, 63, sizeof(dis));
    for(int i=0; i<m; i++)
    {
        g[R[i][0]].push_back({R[i][1], L[i]});
        g[R[i][1]].push_back({R[i][0], L[i]});
    }
    for(int i=0; i<k; i++)
        ext[P[i]]=1;
    dis[0]=0;
    dfs(0, 0);
    for(int i=0; i<n; i++)
    {
        ans=max(ans, check(i));
    }
    return ans;
}


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

*/

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