oj.uz

Submission #541592

# Submission time Handle Problem Language Result Execution time Memory
541592 2022-03-23T19:43:05 Z adespawn Mousetrap (CEOI17_mousetrap) C++14
25 / 100
 839 ms 59960 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());
        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;
}

map<pair<int, pair<int, int>>, 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;
    if (mp[{w, {a, miip}}] != 0)
        return mp[{w, {a, miip}}];
    int lsp = 0, csp = 0;
    for (int i = 0; i < min(a + 1, (int)v[w].size()); 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;
    }
    // cout << w << ' ' << a << ' ' << miip << ' ' << mnw << '\n';
    mp[{w, {a, miip}}] = mnw;
    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 Correct 14 ms 23764 KB Output is correct
2 Correct 15 ms 23716 KB Output is correct
3 Incorrect 14 ms 23816 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 342 ms 58632 KB Output is correct
2 Correct 317 ms 55592 KB Output is correct
3 Correct 829 ms 59840 KB Output is correct
4 Correct 405 ms 42736 KB Output is correct
5 Correct 827 ms 59960 KB Output is correct
6 Correct 839 ms 59832 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23764 KB Output is correct
2 Correct 15 ms 23716 KB Output is correct
3 Incorrect 14 ms 23816 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23764 KB Output is correct
2 Correct 15 ms 23716 KB Output is correct
3 Incorrect 14 ms 23816 KB Output isn't correct
4 Halted 0 ms 0 KB -