제출 #764630

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

crocodile

#include "crocodile.h"
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

const int maxn = 100005;

int n, m, k;

vector<pair<int, int>> g[maxn];

bool is_leaf[maxn];
bool is_escape[maxn];

int subtree[maxn];

void dfs1(int node, int par)
{
    subtree[node] = is_escape[node];

    for (auto [v, w] : g[node])
    {
        if (v != par)
        {
            dfs1(v, node);
            subtree[node] += subtree[v];
        }
    }
}

int dfs2(int node, int par)
{
    if (is_escape[node] == true)
    {
        return 0;
    }

    int ans = 0;

    for (auto [v, w] : g[node])
    {
        if (v != par)
        {
            if (subtree[v] > 1)
            {
                ans = max(ans, w + dfs2(v, node));
            }
            else if (is_leaf[v] == true)
            {
                ans = max(ans, w);
            }
        }
    }

    return ans;
}

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
    n = N;
    m = M;
    k = K;

    for (int i = 0; i < m; ++i)
    {
        int x = R[i][0];
        int y = R[i][1];
        int w = L[i];

        g[x].push_back(make_pair(y, w));
        g[y].push_back(make_pair(x, w));
    }

    for (int i = 0; i < n; ++i)
    {
        if (g[i].size() == 1)
        {
            is_leaf[i] = true;
        }
    }

    for (int i = 0; i < k; ++i)
    {
        is_escape[P[i]] = true;
    }

    if (is_escape[0] == true)
    {
        return 0;
    }

    dfs1(0, -1);

    return dfs2(0, -1);
}

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