oj.uz

Submission #499898

# Submission time Handle Problem Language Result Execution time Memory
499898 2021-12-29T22:56:44 Z aryan12 Race (IOI11_race) C++17
100 / 100
 509 ms 41640 KB 
#include "race.h"
#include <bits/stdc++.h>
using namespace std;

const long long MAXN = 2e5 + 5, MAXK = 1e6 + 5;
long long knapsack[MAXK];
vector<pair<long long, long long> > g[MAXN];
bool vis[MAXN];
long long subtree[MAXN], ans, k;
vector<long long> changes;

long long Dfs(long long node, long long par = -1) {
    subtree[node] = 1;
    for(long long i = 0; i < g[node].size(); i++) {
        if(!vis[g[node][i].first] && g[node][i].first != par) {
            subtree[node] += Dfs(g[node][i].first, node);
        }
    }
    return subtree[node];
}

long long FindCentroid(long long node, long long subtreeSize, long long par = -1) {
    for(long long i = 0; i < g[node].size(); i++) {
        if(!vis[g[node][i].first] && g[node][i].first != par) {
            if(subtree[g[node][i].first] > subtreeSize / 2) {
                return FindCentroid(g[node][i].first, subtreeSize, node);
            }
        }
    }
    return node;
}

void DfsSubtree(long long node, long long par, long long cur_len, long long cur_roads, bool taking) {
    if(cur_len > k) {
        return;
    }
    if(taking) {
        //cout << "node = " << node << ", par = " << par << ", cur_len = " << cur_len << ", cur_roads = " << cur_roads << ", values = " << knapsack[k - cur_len] + cur_roads << "\n";
        //cout << "Node = " << node << ", ans = " << ans << "\n";
        ans = min(ans, knapsack[k - cur_len] + cur_roads);
        //cout << "Node = " << node << ", ans = " << ans << "\n";
    }
    else {
        if(knapsack[cur_len] > cur_roads) {
            knapsack[cur_len] = cur_roads;
            changes.push_back(cur_len);
        }
    }
    for(long long i = 0; i < g[node].size(); i++) {
        if(vis[g[node][i].first] || g[node][i].first == par) {
            continue;
        }
        DfsSubtree(g[node][i].first, node, cur_len + g[node][i].second, cur_roads + 1, taking);
    }
    //cout << "node = " << node << ", ans = " << ans << "\n";
}

void DecomposeTree(long long node) {
    long long subtreeSize = Dfs(node);
    long long cur_centroid = FindCentroid(node, subtreeSize); 
    //cout << "cur_centroid = " << cur_centroid << "\n"; //is perfect
    vis[cur_centroid] = true;
    for(int i = 0; i < g[cur_centroid].size(); i++) {
        if(!vis[g[cur_centroid][i].first]) {
            DfsSubtree(g[cur_centroid][i].first, cur_centroid, g[cur_centroid][i].second, 1LL, true); //first take all, then fill, to ensure nothing from same subtree is taken
            DfsSubtree(g[cur_centroid][i].first, cur_centroid, g[cur_centroid][i].second, 1LL, false);
        }
    }
    for(long long i = 0; i < changes.size(); i++) {
        knapsack[changes[i]] = 1e15;
    }
    changes.clear();
    for(long long i = 0; i < g[cur_centroid].size(); i++) {
        if(!vis[g[cur_centroid][i].first]) {
            DecomposeTree(g[cur_centroid][i].first);
        }
    }
}

int best_path(int N, int K, int H[][2], int L[]) {
    ans = 1e15;
    k = K;
    for(long long i = 0; i < N - 1; i++) {
        g[H[i][0]].push_back(make_pair(H[i][1], L[i]));
        g[H[i][1]].push_back(make_pair(H[i][0], L[i]));
    }
    for(long long i = 1; i <= k; i++) {
        knapsack[i] = 1e15;
    }
    DecomposeTree(0);
    if(ans == 1e15) return -1;
    return ans;
}

Compilation message

race.cpp: In function 'long long int Dfs(long long int, long long int)':
race.cpp:14:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |     for(long long i = 0; i < g[node].size(); i++) {
      |                          ~~^~~~~~~~~~~~~~~~
race.cpp: In function 'long long int FindCentroid(long long int, long long int, long long int)':
race.cpp:23:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |     for(long long i = 0; i < g[node].size(); i++) {
      |                          ~~^~~~~~~~~~~~~~~~
race.cpp: In function 'void DfsSubtree(long long int, long long int, long long int, long long int, bool)':
race.cpp:49:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |     for(long long i = 0; i < g[node].size(); i++) {
      |                          ~~^~~~~~~~~~~~~~~~
race.cpp: In function 'void DecomposeTree(long long int)':
race.cpp:63:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |     for(int i = 0; i < g[cur_centroid].size(); i++) {
      |                    ~~^~~~~~~~~~~~~~~~~~~~~~~~
race.cpp:69:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |     for(long long i = 0; i < changes.size(); i++) {
      |                          ~~^~~~~~~~~~~~~~~~
race.cpp:73:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |     for(long long i = 0; i < g[cur_centroid].size(); i++) {
      |                          ~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 5012 KB Output is correct
3 Correct 3 ms 5008 KB Output is correct
4 Correct 3 ms 5008 KB Output is correct
5 Correct 3 ms 5008 KB Output is correct
6 Correct 2 ms 4940 KB Output is correct
7 Correct 3 ms 4940 KB Output is correct
8 Correct 3 ms 4940 KB Output is correct
9 Correct 3 ms 5016 KB Output is correct
10 Correct 3 ms 4940 KB Output is correct
11 Correct 4 ms 4940 KB Output is correct
12 Correct 3 ms 4940 KB Output is correct
13 Correct 2 ms 4940 KB Output is correct
14 Correct 3 ms 4940 KB Output is correct
15 Correct 3 ms 4940 KB Output is correct
16 Correct 3 ms 4940 KB Output is correct
17 Correct 3 ms 4940 KB Output is correct
18 Correct 2 ms 4940 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 5012 KB Output is correct
3 Correct 3 ms 5008 KB Output is correct
4 Correct 3 ms 5008 KB Output is correct
5 Correct 3 ms 5008 KB Output is correct
6 Correct 2 ms 4940 KB Output is correct
7 Correct 3 ms 4940 KB Output is correct
8 Correct 3 ms 4940 KB Output is correct
9 Correct 3 ms 5016 KB Output is correct
10 Correct 3 ms 4940 KB Output is correct
11 Correct 4 ms 4940 KB Output is correct
12 Correct 3 ms 4940 KB Output is correct
13 Correct 2 ms 4940 KB Output is correct
14 Correct 3 ms 4940 KB Output is correct
15 Correct 3 ms 4940 KB Output is correct
16 Correct 3 ms 4940 KB Output is correct
17 Correct 3 ms 4940 KB Output is correct
18 Correct 2 ms 4940 KB Output is correct
19 Correct 2 ms 4940 KB Output is correct
20 Correct 3 ms 4940 KB Output is correct
21 Correct 3 ms 5068 KB Output is correct
22 Correct 7 ms 12236 KB Output is correct
23 Correct 6 ms 10956 KB Output is correct
24 Correct 6 ms 11852 KB Output is correct
25 Correct 9 ms 11724 KB Output is correct
26 Correct 5 ms 7716 KB Output is correct
27 Correct 7 ms 11296 KB Output is correct
28 Correct 4 ms 6604 KB Output is correct
29 Correct 4 ms 7620 KB Output is correct
30 Correct 4 ms 7956 KB Output is correct
31 Correct 5 ms 10188 KB Output is correct
32 Correct 6 ms 10572 KB Output is correct
33 Correct 6 ms 11212 KB Output is correct
34 Correct 5 ms 9676 KB Output is correct
35 Correct 7 ms 11424 KB Output is correct
36 Correct 7 ms 12292 KB Output is correct
37 Correct 8 ms 11340 KB Output is correct
38 Correct 5 ms 8992 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 5012 KB Output is correct
3 Correct 3 ms 5008 KB Output is correct
4 Correct 3 ms 5008 KB Output is correct
5 Correct 3 ms 5008 KB Output is correct
6 Correct 2 ms 4940 KB Output is correct
7 Correct 3 ms 4940 KB Output is correct
8 Correct 3 ms 4940 KB Output is correct
9 Correct 3 ms 5016 KB Output is correct
10 Correct 3 ms 4940 KB Output is correct
11 Correct 4 ms 4940 KB Output is correct
12 Correct 3 ms 4940 KB Output is correct
13 Correct 2 ms 4940 KB Output is correct
14 Correct 3 ms 4940 KB Output is correct
15 Correct 3 ms 4940 KB Output is correct
16 Correct 3 ms 4940 KB Output is correct
17 Correct 3 ms 4940 KB Output is correct
18 Correct 2 ms 4940 KB Output is correct
19 Correct 146 ms 13520 KB Output is correct
20 Correct 126 ms 13508 KB Output is correct
21 Correct 126 ms 13472 KB Output is correct
22 Correct 128 ms 13648 KB Output is correct
23 Correct 82 ms 13848 KB Output is correct
24 Correct 56 ms 13124 KB Output is correct
25 Correct 107 ms 16324 KB Output is correct
26 Correct 86 ms 19268 KB Output is correct
27 Correct 173 ms 21272 KB Output is correct
28 Correct 236 ms 32268 KB Output is correct
29 Correct 235 ms 31496 KB Output is correct
30 Correct 159 ms 21188 KB Output is correct
31 Correct 158 ms 21256 KB Output is correct
32 Correct 214 ms 21316 KB Output is correct
33 Correct 203 ms 20132 KB Output is correct
34 Correct 174 ms 19980 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 5012 KB Output is correct
3 Correct 3 ms 5008 KB Output is correct
4 Correct 3 ms 5008 KB Output is correct
5 Correct 3 ms 5008 KB Output is correct
6 Correct 2 ms 4940 KB Output is correct
7 Correct 3 ms 4940 KB Output is correct
8 Correct 3 ms 4940 KB Output is correct
9 Correct 3 ms 5016 KB Output is correct
10 Correct 3 ms 4940 KB Output is correct
11 Correct 4 ms 4940 KB Output is correct
12 Correct 3 ms 4940 KB Output is correct
13 Correct 2 ms 4940 KB Output is correct
14 Correct 3 ms 4940 KB Output is correct
15 Correct 3 ms 4940 KB Output is correct
16 Correct 3 ms 4940 KB Output is correct
17 Correct 3 ms 4940 KB Output is correct
18 Correct 2 ms 4940 KB Output is correct
19 Correct 2 ms 4940 KB Output is correct
20 Correct 3 ms 4940 KB Output is correct
21 Correct 3 ms 5068 KB Output is correct
22 Correct 7 ms 12236 KB Output is correct
23 Correct 6 ms 10956 KB Output is correct
24 Correct 6 ms 11852 KB Output is correct
25 Correct 9 ms 11724 KB Output is correct
26 Correct 5 ms 7716 KB Output is correct
27 Correct 7 ms 11296 KB Output is correct
28 Correct 4 ms 6604 KB Output is correct
29 Correct 4 ms 7620 KB Output is correct
30 Correct 4 ms 7956 KB Output is correct
31 Correct 5 ms 10188 KB Output is correct
32 Correct 6 ms 10572 KB Output is correct
33 Correct 6 ms 11212 KB Output is correct
34 Correct 5 ms 9676 KB Output is correct
35 Correct 7 ms 11424 KB Output is correct
36 Correct 7 ms 12292 KB Output is correct
37 Correct 8 ms 11340 KB Output is correct
38 Correct 5 ms 8992 KB Output is correct
39 Correct 146 ms 13520 KB Output is correct
40 Correct 126 ms 13508 KB Output is correct
41 Correct 126 ms 13472 KB Output is correct
42 Correct 128 ms 13648 KB Output is correct
43 Correct 82 ms 13848 KB Output is correct
44 Correct 56 ms 13124 KB Output is correct
45 Correct 107 ms 16324 KB Output is correct
46 Correct 86 ms 19268 KB Output is correct
47 Correct 173 ms 21272 KB Output is correct
48 Correct 236 ms 32268 KB Output is correct
49 Correct 235 ms 31496 KB Output is correct
50 Correct 159 ms 21188 KB Output is correct
51 Correct 158 ms 21256 KB Output is correct
52 Correct 214 ms 21316 KB Output is correct
53 Correct 203 ms 20132 KB Output is correct
54 Correct 174 ms 19980 KB Output is correct
55 Correct 12 ms 5904 KB Output is correct
56 Correct 11 ms 5828 KB Output is correct
57 Correct 87 ms 13832 KB Output is correct
58 Correct 34 ms 12776 KB Output is correct
59 Correct 104 ms 21844 KB Output is correct
60 Correct 431 ms 41640 KB Output is correct
61 Correct 166 ms 21448 KB Output is correct
62 Correct 181 ms 29368 KB Output is correct
63 Correct 262 ms 29244 KB Output is correct
64 Correct 509 ms 26776 KB Output is correct
65 Correct 224 ms 20788 KB Output is correct
66 Correct 381 ms 37312 KB Output is correct
67 Correct 109 ms 27816 KB Output is correct
68 Correct 228 ms 29656 KB Output is correct
69 Correct 238 ms 29332 KB Output is correct
70 Correct 245 ms 28840 KB Output is correct