oj.uz

Submission #541596

# Submission time Handle Problem Language Result Execution time Memory
541596 2022-03-23T19:55:18 Z adespawn Mousetrap (CEOI17_mousetrap) C++14
100 / 100
 1382 ms 318412 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();
}

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+(long long)miip*(long long)1000000000000;
    if (mp[k] != 0)
        return mp[k];
    int lsp = -2137, 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

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)
      |            ~~~~~~~~~^~~~~~~
mousetrap.cpp: In function 'int solve2(int, int, int)':
mousetrap.cpp:82:9: warning: variable 'lsp' set but not used [-Wunused-but-set-variable]
   82 |     int lsp = -2137, csp = 0;
      |         ^~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 13 ms 23816 KB Output is correct
3 Correct 12 ms 23764 KB Output is correct
4 Correct 12 ms 23804 KB Output is correct
5 Correct 13 ms 23784 KB Output is correct
6 Correct 13 ms 23808 KB Output is correct
7 Correct 13 ms 23808 KB Output is correct
8 Correct 14 ms 23764 KB Output is correct
9 Correct 14 ms 23764 KB Output is correct
10 Correct 16 ms 23700 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 334 ms 55100 KB Output is correct
2 Correct 327 ms 51972 KB Output is correct
3 Correct 786 ms 56292 KB Output is correct
4 Correct 367 ms 39976 KB Output is correct
5 Correct 820 ms 56208 KB Output is correct
6 Correct 794 ms 56204 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 13 ms 23816 KB Output is correct
3 Correct 12 ms 23764 KB Output is correct
4 Correct 12 ms 23804 KB Output is correct
5 Correct 13 ms 23784 KB Output is correct
6 Correct 13 ms 23808 KB Output is correct
7 Correct 13 ms 23808 KB Output is correct
8 Correct 14 ms 23764 KB Output is correct
9 Correct 14 ms 23764 KB Output is correct
10 Correct 16 ms 23700 KB Output is correct
11 Correct 12 ms 23764 KB Output is correct
12 Correct 13 ms 23740 KB Output is correct
13 Correct 14 ms 23752 KB Output is correct
14 Correct 14 ms 24176 KB Output is correct
15 Correct 13 ms 24020 KB Output is correct
16 Correct 13 ms 23732 KB Output is correct
17 Correct 12 ms 23764 KB Output is correct
18 Correct 13 ms 23872 KB Output is correct
19 Correct 15 ms 23844 KB Output is correct
20 Correct 13 ms 23764 KB Output is correct
21 Correct 16 ms 23764 KB Output is correct
22 Correct 13 ms 23764 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 13 ms 23816 KB Output is correct
3 Correct 12 ms 23764 KB Output is correct
4 Correct 12 ms 23804 KB Output is correct
5 Correct 13 ms 23784 KB Output is correct
6 Correct 13 ms 23808 KB Output is correct
7 Correct 13 ms 23808 KB Output is correct
8 Correct 14 ms 23764 KB Output is correct
9 Correct 14 ms 23764 KB Output is correct
10 Correct 16 ms 23700 KB Output is correct
11 Correct 334 ms 55100 KB Output is correct
12 Correct 327 ms 51972 KB Output is correct
13 Correct 786 ms 56292 KB Output is correct
14 Correct 367 ms 39976 KB Output is correct
15 Correct 820 ms 56208 KB Output is correct
16 Correct 794 ms 56204 KB Output is correct
17 Correct 12 ms 23764 KB Output is correct
18 Correct 13 ms 23740 KB Output is correct
19 Correct 14 ms 23752 KB Output is correct
20 Correct 14 ms 24176 KB Output is correct
21 Correct 13 ms 24020 KB Output is correct
22 Correct 13 ms 23732 KB Output is correct
23 Correct 12 ms 23764 KB Output is correct
24 Correct 13 ms 23872 KB Output is correct
25 Correct 15 ms 23844 KB Output is correct
26 Correct 13 ms 23764 KB Output is correct
27 Correct 16 ms 23764 KB Output is correct
28 Correct 13 ms 23764 KB Output is correct
29 Correct 13 ms 23764 KB Output is correct
30 Correct 343 ms 55200 KB Output is correct
31 Correct 332 ms 55112 KB Output is correct
32 Correct 1027 ms 318412 KB Output is correct
33 Correct 399 ms 195960 KB Output is correct
34 Correct 791 ms 56200 KB Output is correct
35 Correct 798 ms 56264 KB Output is correct
36 Correct 894 ms 88692 KB Output is correct
37 Correct 859 ms 82412 KB Output is correct
38 Correct 731 ms 91284 KB Output is correct
39 Correct 1382 ms 199312 KB Output is correct
40 Correct 937 ms 142440 KB Output is correct