Submission #541594

#	Time	Username	Problem	Language	Result	Execution time	Memory
541594		adespawn	Mousetrap (CEOI17_mousetrap)	C++14	45 / 100	780 ms	56248 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();
}

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());
        int z = sp.back() + tv.size() - 1;
        sp.push_back(z);
        v.push_back(tv);
        // cout << w << ' ' << sp.back() << '\n';
        // for (auto j : tv)
        //     cout << j << ' ';
        // cout << '\n';
        return 1;
    }
    return 0;
}

int illR;
map<long long, int> mp;
int solve2(int w, int a, int miip = 0)
{
    if (w == 0 || a == 0)
        return 0;
    // if (w + a - 1 >= sp[w])
    //     return sp[w];
    int mnw = 100000000;
    long long k = (long long)w + (long long)a * (long long)1000000;
    if (mp[k] != 0)
        return mp[k];
    int lsp = 0, csp = 0;
    for (int i = min(a + 1, (int)v[w].size()) - 1; i >= 0; i--)
    {
        csp = v[w][i] + sp[w - 1] + max((int)(v[w].size() - i - 2), 0) + i;
        if (csp == lsp)
            continue;
        lsp = csp;
        int cll = solve2(w - 1, a - i + 1, max(miip - i, csp - i));
        mnw = min(max(csp - i, cll) + i, mnw);
        if (mnw < miip)
            break;
    }
    if (mnw == 100000000)
        mnw = 0;
    // cout << w << ' ' << a << ' ' << miip << ' ' << mnw << '\n';
    mp[k] = mnw;
    // illR++;
    // cout << illR << ' ' << flush;
    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);
    for (int i = 1; i <= n; i++)
        sc[i].clear();
    // 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: 20 / 20
• Subtask 2: 25 / 25
• Subtask 3: 0 / 20
• Subtask 4: 0 / 35