oj.uz

Submission #541575

# Submission time Handle Problem Language Result Execution time Memory
541575 2022-03-23T18:58:15 Z adespawn Mousetrap (CEOI17_mousetrap) C++14
25 / 100
 858 ms 57488 KB 
#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

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.0

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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 377 ms 56244 KB Output is correct
2 Correct 320 ms 53252 KB Output is correct
3 Correct 858 ms 57360 KB Output is correct
4 Correct 401 ms 41276 KB Output is correct
5 Correct 817 ms 57488 KB Output is correct
6 Correct 804 ms 57424 KB Output is correct

Subtask #3
0 / 20.0

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

Subtask #4
0 / 35.0

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