oj.uz

Submission #289023

# Submission time Handle Problem Language Result Execution time Memory
289023 2020-09-02T09:38:10 Z evpipis Mousetrap (CEOI17_mousetrap) C++11
45 / 100
 911 ms 79868 KB 
#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
typedef pair<int, int> ii;

const int len = 1e6+5, inf = 1e9;
vector<int> adj[len], cost[len], order;
int block[len], dp[2][len];

int fix_order(int u, int p, int en){
    if (u == en){
        block[u] = 1;
        return 1;
    }

    for (auto v: adj[u]){
        if (v == p) continue;

        if (fix_order(v, u, en)){
            order.pb(u);
            block[u] = 1;
            return 1;
        }
    }

    return 0;
}

int run_dfs(int u, int p){
    int mx1 = 0, mx2 = 0, kids = 0;
    for (auto v: adj[u]){
        if (v == p) continue;

        kids++;

        int cur = run_dfs(v, u);
        if (cur > mx1)
            mx2 = mx1, mx1 = cur;
        else if (cur > mx2)
            mx2 = cur;
    }

    return mx2+kids;
}

int main(){
    int n, en, st;
    scanf("%d %d %d", &n, &en, &st);
    for (int i = 0; i < n-1; i++){
        int a, b;
        scanf("%d %d", &a, &b);
        adj[a].pb(b);
        adj[b].pb(a);
    }


    fix_order(st, st, en);
    reverse(order.begin(), order.end());

    for (int i = (int)order.size()-1, cnt = 0; i >= 0; i--){
        int u = order[i];

        //printf("i = %d, u = %d\n", i, u);
        for (auto v: adj[u]){
            if (block[v]) continue;

            cost[i].pb(run_dfs(v, u)+1);

            //printf("%d -> %d, cost = %d\n", u, v, cost[i].back());
        }

        sort(cost[i].begin(), cost[i].end());
        reverse(cost[i].begin(), cost[i].end());

        for (int j = (int)cost[i].size()-1; j >= 0; j--)
            cost[i][j] += cnt++;
    }

    for (int i = (int)order.size()-1; i >= 0; i--){
        for (int rem = 1; rem <= i+1; rem++){
            dp[i&1][rem] = inf;
            if (rem >= cost[i].size())
                dp[i&1][rem] = cost[i].size() + dp[(i+1)&1][rem-cost[i].size()+1];

            int opt = -1;
            for (int j = 0; j < cost[i].size(); j++){
                if (j <= rem && cost[i][j] >= dp[(i+1)&1][rem-j+1])
                    opt = j;
                //if (j <= rem)
                  //  dp[i&1][rem] = min(dp[i&1][rem], j+max(cost[i][j], dp[(i+1)&1][rem-j+1]));
            }

            if (opt != -1)
                dp[i&1][rem] = min(dp[i&1][rem], opt + cost[i][opt]);
            else
                dp[i&1][rem] = min(dp[i&1][rem], dp[(i+1)&1][rem+1]);
        }
    }

    printf("%d\n", dp[0][1]);
    return 0;
}

Compilation message

mousetrap.cpp: In function 'int main()':
mousetrap.cpp:86:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |             if (rem >= cost[i].size())
      |                 ~~~~^~~~~~~~~~~~~~~~~
mousetrap.cpp:90:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |             for (int j = 0; j < cost[i].size(); j++){
      |                             ~~^~~~~~~~~~~~~~~~
mousetrap.cpp:52:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   52 |     scanf("%d %d %d", &n, &en, &st);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
mousetrap.cpp:55:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   55 |         scanf("%d %d", &a, &b);
      |         ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 47352 KB Output is correct
2 Correct 33 ms 47352 KB Output is correct
3 Correct 32 ms 47352 KB Output is correct
4 Correct 32 ms 47360 KB Output is correct
5 Correct 32 ms 47352 KB Output is correct
6 Correct 38 ms 47232 KB Output is correct
7 Correct 32 ms 47360 KB Output is correct
8 Correct 35 ms 47352 KB Output is correct
9 Correct 32 ms 47360 KB Output is correct
10 Correct 32 ms 47232 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 436 ms 78584 KB Output is correct
2 Correct 395 ms 75640 KB Output is correct
3 Correct 888 ms 79864 KB Output is correct
4 Correct 453 ms 63608 KB Output is correct
5 Correct 911 ms 79864 KB Output is correct
6 Correct 897 ms 79868 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 47352 KB Output is correct
2 Correct 33 ms 47352 KB Output is correct
3 Correct 32 ms 47352 KB Output is correct
4 Correct 32 ms 47360 KB Output is correct
5 Correct 32 ms 47352 KB Output is correct
6 Correct 38 ms 47232 KB Output is correct
7 Correct 32 ms 47360 KB Output is correct
8 Correct 35 ms 47352 KB Output is correct
9 Correct 32 ms 47360 KB Output is correct
10 Correct 32 ms 47232 KB Output is correct
11 Correct 32 ms 47352 KB Output is correct
12 Correct 33 ms 47360 KB Output is correct
13 Correct 33 ms 47352 KB Output is correct
14 Correct 35 ms 47360 KB Output is correct
15 Correct 34 ms 47360 KB Output is correct
16 Correct 32 ms 47284 KB Output is correct
17 Incorrect 32 ms 47360 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 47352 KB Output is correct
2 Correct 33 ms 47352 KB Output is correct
3 Correct 32 ms 47352 KB Output is correct
4 Correct 32 ms 47360 KB Output is correct
5 Correct 32 ms 47352 KB Output is correct
6 Correct 38 ms 47232 KB Output is correct
7 Correct 32 ms 47360 KB Output is correct
8 Correct 35 ms 47352 KB Output is correct
9 Correct 32 ms 47360 KB Output is correct
10 Correct 32 ms 47232 KB Output is correct
11 Correct 436 ms 78584 KB Output is correct
12 Correct 395 ms 75640 KB Output is correct
13 Correct 888 ms 79864 KB Output is correct
14 Correct 453 ms 63608 KB Output is correct
15 Correct 911 ms 79864 KB Output is correct
16 Correct 897 ms 79868 KB Output is correct
17 Correct 32 ms 47352 KB Output is correct
18 Correct 33 ms 47360 KB Output is correct
19 Correct 33 ms 47352 KB Output is correct
20 Correct 35 ms 47360 KB Output is correct
21 Correct 34 ms 47360 KB Output is correct
22 Correct 32 ms 47284 KB Output is correct
23 Incorrect 32 ms 47360 KB Output isn't correct
24 Halted 0 ms 0 KB -