Submission #499898

#	Time	Username	Problem	Language	Result	Execution time	Memory
499898		aryan12	Race (IOI11_race)	C++17	100 / 100	509 ms	41640 KiB

race

#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 (stderr)

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 / 9
• Subtask 2: 12 / 12
• Subtask 3: 22 / 22
• Subtask 4: 57 / 57