Submission #541516

#	Time	Username	Problem	Language	Result	Execution time	Memory
541516		adespawn	Mousetrap (CEOI17_mousetrap)	C++14	45 / 100	818 ms	60984 KiB

mousetrap

#include <bits/stdc++.h>
using namespace std;

vector<int> sc[1000006];
bool isS[1000006];
bool odw[1000006];

long long solve(int w, int f, int a = 1)
{

    priority_queue<int> k;
    for (auto i : sc[w])
    {
        if (i == f || isS[i])
            continue;
        k.push(solve(i, w));
    }
    while (k.size() < a + 1)
        k.push(0);
    for (int i = 0; i < a; i++)
        k.pop();
    return sc[w].size() - 1 + k.top();
}

int n, m, k;

stack<pair<int, int>> s;

long long nw;

int dfs(int w, int f = 0, int g = 1)
{
    if (w == m)
        return 1;
    for (auto i : sc[w])
    {
        if (i == f)
            continue;
        int x = dfs(i, w, g + 1);
        if (x == 0)
            continue;
        isS[i] = 1;
        nw = max(x + solve(w, f, g) - (f != 0), nw);
        return x + sc[w].size() - 2;
    }
    return 0;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin >> n >> m >> k;
    for (int i = 1; i < n; i++)
    {
        int a, b;
        cin >> a >> b;
        sc[a].push_back(b);
        sc[b].push_back(a);
    }
    dfs(k);
    cout << nw - 1 << '\n';
    // s.push({0, 0});
    // cout << solve(k, m);
}

Compilation message (stderr)

mousetrap.cpp: In function 'long long int solve(int, int, int)':
mousetrap.cpp:18:21: warning: comparison of integer expressions of different signedness: 'std::priority_queue<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   18 |     while (k.size() < a + 1)
      |            ~~~~~~~~~^~~~~~~

• Subtask 1: 20 / 20
• Subtask 2: 25 / 25
• Subtask 3: 0 / 20
• Subtask 4: 0 / 35