Submission #541575

#	Time	Username	Problem	Language	Result	Execution time	Memory
541575		adespawn	Mousetrap (CEOI17_mousetrap)	C++14	25 / 100	858 ms	57488 KiB

mousetrap

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

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

int n, m, k;

int solve(int w, int f, int a = 1)
{
    priority_queue<int> k;
    if (w == m)
        return 0;
    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) && (k.size() > 1); i++)
        k.pop();
    return sc[w].size() - 1 + k.top();
}

stack<pair<int, int>> s;

int nw;

vector<vector<int>> v;
vector<int> sp;

int dfs(int w, int f = 0, int g = 1, int z = 0)
{
    if (w == m)
    {
        v.push_back(sp);
        sp.push_back(0);
        return 1;
    }
    for (auto i : sc[w])
    {
        if (i == f)
            continue;
        int x = dfs(i, w, g + 1, z + sc[w].size() - 2 + (f == 0));
        if (x == 0)
            continue;
        isS[i] = 1;
        vector<int> tv;
        for (auto j : sc[w])
        {
            if (j == f || i == j)
                continue;
            tv.push_back(solve(j, w) + 1);
        }
        tv.push_back(0);
        sort(tv.begin(), tv.end());
        reverse(tv.begin(), tv.end());
        sp.push_back(sp.back() + tv.size());
        v.push_back(tv);
        // cout << w << '\n';
        // for (auto j : tv)
        //     cout << j << ' ';
        // cout << '\n';
        return 1;
    }
    return 0;
}

map<pair<int, int>, int> mp;
int solve2(int w, int a)
{
    if (w == 0 || a == 0)
        return 0;
    int mnw = 100000000;
    if (mp[{w, a}] != 0)
        return mp[{w, a}];
    // cout << w << '\n';
    for (int i = 0; i < min(a + 1, (int)v[w].size()); i++)
    {
        mnw = min(max(v[w][i] + sp[w - 1] + max((int)(v[w].size() - i - 2), 0), solve2(w - 1, a - i + 1)) + i, mnw);
    }
    mp[{w, a}] = mnw;
    // cout << w << ' ' << a << ' ' << mnw << '\n';
    return mnw;
}

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 << solve2(sp.size() - 1, 1);
}

Compilation message (stderr)

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

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