oj.uz

Submission #289226

# Submission time Handle Problem Language Result Execution time Memory
289226 2020-09-02T13:21:42 Z evpipis Mousetrap (CEOI17_mousetrap) C++11
65 / 100
 5000 ms 189048 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(){
    //freopen("trap.01.01.in", "r", stdin);

    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++;
        cost[i].pb(0);

        /*printf("i = %d\n", i);
        for (int j = 0; j < cost[i].size(); j++)
            printf("%d ", cost[i][j]);
        printf("\n");*/
    }

    for (int i = (int)order.size()-1; i >= 0; i--){
        for (int rem = 1, j = 0; rem <= i+1; rem++){
            //printf("computing dp: i = %d, rem = %d\n", i, rem);

            dp[i&1][rem] = inf;

            //int opt = -1;
            while (j < cost[i].size() && j <= rem && cost[i][j] >= dp[(i+1)&1][rem-j+1]){
                j++;
            }

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

                //dp[i&1][rem] = min(dp[i&1][rem], j+max(cost[i][j], dp[(i+1)&1][rem-j+1]));
            }*/

            //printf("opt = %d\n", opt);

            if (j-1 != -1)
                dp[i&1][rem] = min(dp[i&1][rem], j-1 + cost[i][j-1]);
            if (j < cost[i].size() && j <= rem)
                dp[i&1][rem] = min(dp[i&1][rem], j + dp[(i+1)&1][rem+1-j]);

            /*if (opt != -1)
                dp[i&1][rem] = min(dp[i&1][rem], opt + cost[i][opt]);
            if (opt+1 < cost[i].size() && opt+1 <= rem)
                dp[i&1][rem] = min(dp[i&1][rem], opt+1 + dp[(i+1)&1][rem-opt]);*/
        }

        //printf("i = %d\n", i);
        //for (int rem = 1; rem <= i+1; rem++)
          //  printf("rem = %d, dp = %d\n", rem, dp[i&1][rem]);
    }

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

Compilation message

mousetrap.cpp: In function 'int main()':
mousetrap.cpp:98:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |             while (j < cost[i].size() && j <= rem && cost[i][j] >= dp[(i+1)&1][rem-j+1]){
      |                    ~~^~~~~~~~~~~~~~~~
mousetrap.cpp:114:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |             if (j < cost[i].size() && j <= rem)
      |                 ~~^~~~~~~~~~~~~~~~
mousetrap.cpp:54:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   54 |     scanf("%d %d %d", &n, &en, &st);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
mousetrap.cpp:57:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   57 |         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 47360 KB Output is correct
3 Correct 32 ms 47352 KB Output is correct
4 Correct 34 ms 47352 KB Output is correct
5 Correct 33 ms 47352 KB Output is correct
6 Correct 33 ms 47488 KB Output is correct
7 Correct 33 ms 47360 KB Output is correct
8 Correct 32 ms 47352 KB Output is correct
9 Correct 32 ms 47352 KB Output is correct
10 Correct 34 ms 47480 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 428 ms 79480 KB Output is correct
2 Correct 400 ms 76280 KB Output is correct
3 Correct 897 ms 80428 KB Output is correct
4 Correct 441 ms 64376 KB Output is correct
5 Correct 904 ms 80568 KB Output is correct
6 Correct 899 ms 80632 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 47352 KB Output is correct
2 Correct 33 ms 47360 KB Output is correct
3 Correct 32 ms 47352 KB Output is correct
4 Correct 34 ms 47352 KB Output is correct
5 Correct 33 ms 47352 KB Output is correct
6 Correct 33 ms 47488 KB Output is correct
7 Correct 33 ms 47360 KB Output is correct
8 Correct 32 ms 47352 KB Output is correct
9 Correct 32 ms 47352 KB Output is correct
10 Correct 34 ms 47480 KB Output is correct
11 Correct 32 ms 47360 KB Output is correct
12 Correct 33 ms 47352 KB Output is correct
13 Correct 33 ms 47360 KB Output is correct
14 Correct 36 ms 47616 KB Output is correct
15 Correct 34 ms 47616 KB Output is correct
16 Correct 33 ms 47360 KB Output is correct
17 Correct 33 ms 47488 KB Output is correct
18 Correct 33 ms 47360 KB Output is correct
19 Correct 33 ms 47352 KB Output is correct
20 Correct 33 ms 47360 KB Output is correct
21 Correct 32 ms 47480 KB Output is correct
22 Correct 32 ms 47352 KB Output is correct

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 47352 KB Output is correct
2 Correct 33 ms 47360 KB Output is correct
3 Correct 32 ms 47352 KB Output is correct
4 Correct 34 ms 47352 KB Output is correct
5 Correct 33 ms 47352 KB Output is correct
6 Correct 33 ms 47488 KB Output is correct
7 Correct 33 ms 47360 KB Output is correct
8 Correct 32 ms 47352 KB Output is correct
9 Correct 32 ms 47352 KB Output is correct
10 Correct 34 ms 47480 KB Output is correct
11 Correct 428 ms 79480 KB Output is correct
12 Correct 400 ms 76280 KB Output is correct
13 Correct 897 ms 80428 KB Output is correct
14 Correct 441 ms 64376 KB Output is correct
15 Correct 904 ms 80568 KB Output is correct
16 Correct 899 ms 80632 KB Output is correct
17 Correct 32 ms 47360 KB Output is correct
18 Correct 33 ms 47352 KB Output is correct
19 Correct 33 ms 47360 KB Output is correct
20 Correct 36 ms 47616 KB Output is correct
21 Correct 34 ms 47616 KB Output is correct
22 Correct 33 ms 47360 KB Output is correct
23 Correct 33 ms 47488 KB Output is correct
24 Correct 33 ms 47360 KB Output is correct
25 Correct 33 ms 47352 KB Output is correct
26 Correct 33 ms 47360 KB Output is correct
27 Correct 32 ms 47480 KB Output is correct
28 Correct 32 ms 47352 KB Output is correct
29 Correct 32 ms 47360 KB Output is correct
30 Correct 445 ms 79560 KB Output is correct
31 Correct 423 ms 79480 KB Output is correct
32 Execution timed out 5107 ms 189048 KB Time limit exceeded
33 Halted 0 ms 0 KB -