Submission #526924

#	Time	Username	Problem	Language	Result	Execution time	Memory
526924		pedroslrey	Race (IOI11_race)	C++17	0 / 100	3076 ms	97692 KiB

race

#include <bits/stdc++.h>
#include "race.h"

using namespace std;
using lli = long long;

const int MAXN = 1e5 + 10;
const int MAXK = 1e6 + 10;

vector<pair<int, int>> graph[MAXN];
vector<int> subs[MAXN];
int sub[MAXN], dist[MAXK], aprof[MAXN];
bool marc[MAXN];
lli prof[MAXN];

void dfs_sub(int u, int p) {
    sub[u] = 1;
    for (auto [v, c]: graph[u]) {
        if (v == p) continue;
        dfs_sub(v, u);
        sub[u] += sub[v];
    }
}

void dfs_prof(int u, int p, int cor) {
    subs[cor].push_back(u);
    for (auto [v, c]: graph[u]) {
        if (marc[v] || v == p) continue;
        prof[v] = prof[u] + c;
        aprof[v] = aprof[u] + 1;
        dfs_prof(v, u, cor);
    }
}

int dfs_cent(int u, int p, int n) {
    for (auto [v, c]: graph[u]) {
        if (v == p) continue;
        if (sub[v] >= n/2) return dfs_cent(v, u, n);
    }
    return u;
}

int dfs(int u, int p, int n, int k) {
    dfs_sub(u, p);
    int c = dfs_cent(u, p, n);
    marc[c] = true;

    for (int i = 0; i < graph[c].size(); ++i) {
        auto [v, cost] = graph[c][i];
        if (!marc[v]) {
            prof[v] = cost;
            aprof[v] = 1;
            dfs_prof(v, c, i);
        }
    }

    int ans = 1e9;
    dist[0] = 0;
    for (int i = 0; i < graph[c].size(); ++i) {
        for (int v: subs[i])
            if (prof[v] <= k)
                ans = min(ans, dist[k - prof[v]] + aprof[v]);
         for (int v: subs[i])
            if (prof[v] < MAXK) dist[prof[v]] = min(dist[prof[v]], aprof[v]);
    }

    for (int i = 0; i < graph[c].size(); ++i) {
        for (int v: subs[i])
            dist[v] = 1e9;
        subs[i].clear();
    }

    for (auto [v, cost]: graph[u])
        if (!marc[v]) ans = min(ans, dfs(v, c, n, k));

    return ans;
}


int best_path(int n, int k, int edges[][2], int costs[]) {
    for (int i = 0; i < n-1; ++i) {
        graph[edges[i][0]].emplace_back(edges[i][1], costs[i]);
        graph[edges[i][1]].emplace_back(edges[i][0], costs[i]);
    }

    for (int i = 0; i < MAXK; ++i)
        dist[i] = 1e9;

    int ans = dfs(1, 1, n, k);
    if (ans == 1e9) return -1;
    return ans;
}

Compilation message (stderr)

race.cpp: In function 'int dfs(int, int, int, int)':
race.cpp:48:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |     for (int i = 0; i < graph[c].size(); ++i) {
      |                     ~~^~~~~~~~~~~~~~~~~
race.cpp:59:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |     for (int i = 0; i < graph[c].size(); ++i) {
      |                     ~~^~~~~~~~~~~~~~~~~
race.cpp:67:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |     for (int i = 0; i < graph[c].size(); ++i) {
      |                     ~~^~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 9
• Subtask 2: 0 / 12
• Subtask 3: 0 / 22
• Subtask 4: 0 / 57