oj.uz

Submission #764631

# Submission time Handle Problem Language Result Execution time Memory
764631 2023-06-23T17:03:46 Z borisAngelov Crocodile's Underground City (IOI11_crocodile) C++17
46 / 100
 139 ms 262144 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 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.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2676 KB Output is correct
6 Correct 2 ms 2772 KB Output is correct
7 Correct 2 ms 2772 KB Output is correct
8 Correct 2 ms 2772 KB Output is correct

Subtask #2
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2676 KB Output is correct
6 Correct 2 ms 2772 KB Output is correct
7 Correct 2 ms 2772 KB Output is correct
8 Correct 2 ms 2772 KB Output is correct
9 Runtime error 139 ms 262144 KB Execution killed with signal 9
10 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2676 KB Output is correct
6 Correct 2 ms 2772 KB Output is correct
7 Correct 2 ms 2772 KB Output is correct
8 Correct 2 ms 2772 KB Output is correct
9 Runtime error 139 ms 262144 KB Execution killed with signal 9
10 Halted 0 ms 0 KB -