oj.uz

Submission #764630

# Submission time Handle Problem Language Result Execution time Memory
764630 2023-06-23T16:58:54 Z borisAngelov Crocodile's Underground City (IOI11_crocodile) C++17
0 / 100
 2 ms 2644 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2644 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 43.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2644 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2644 KB Output isn't correct
2 Halted 0 ms 0 KB -