Submission #764631

#	Time	Username	Problem	Language	Result	Execution time	Memory
764631		borisAngelov	악어의 지하 도시 (IOI11_crocodile)	C++17	46 / 100	139 ms	262144 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 ans1 = 1e9 + 5;
    int ans2 = 1e9 + 5;

    for (auto [v, w] : g[node])
    {
        if (v != par)
        {
            int result = 0;

            if (subtree[v] > 1)
            {
                result = w + dfs2(v, node);
            }
            else if (is_leaf[v] == true)
            {
                result = w;
            }

            if (ans1 > result)
            {
                ans2 = ans1;
                ans1 = result;
            }
            else if (ans1 <= result)
            {
                ans2 = min(ans2, result);
            }
        }
    }

    return ans2;
}

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: 46 / 46
• Subtask 2: 0 / 43
• Subtask 3: 0 / 11