Submission #1000809

#	Time	Username	Problem	Language	Result	Execution time	Memory
1000809		saayan007	Race (IOI11_race)	C++17	100 / 100	299 ms	32536 KiB

race

/*

This problem can be found at https://oj.uz/problem/view/IOI11_race.

SOLUTION

Consider the problem of finding a path of length K containing minimum edges THAT GOES A FIXED NODE x.
This can be done in O(Size of Tree) time. Once this is done, we can remove the node x and edges connected to it. Then we can solve the problem for the remaining connected components.

The best choice of x is the centroid of the tree.

*/ 

#include "race.h"
#include "bits/stdc++.h"
using namespace std;
 
const int mxN = 2e5L + 10;
const int mxK = 1e6L + 10;
int n, k;
vector<pair<int, int>> adj[mxN];
int ans = mxN;
int sz[mxN];
bool proc[mxN] = {};
int dp[mxK];
 
int get_sz(int x, int p) {
    sz[x] = 1;
    for(auto [y, w] : adj[x]) {
        if(proc[y] || y == p) continue;
        sz[x] += get_sz(y, x);
    }
    return sz[x];
}
 
int get_cen(int x, int p, int tot) {
    for(auto [y, w] : adj[x]) {
        if(proc[y] || y == p || sz[y] * 2 <= tot) continue;
        return get_cen(y, x, tot);
    }
    return x;
}
 
void dfs(int x, int p, int dep, int dis, int flag) {
    if(dis > k) return;
    if(flag == 0) {
        if(dp[k - dis] != mxN) ans = min(ans, dep + dp[k - dis]);
    }
    else if(flag == 1) {
        dp[dis] = min(dp[dis], dep);
    }
    else if(flag == 2) {
        dp[dis] = mxN;
    }
 
    for(auto [y, w] : adj[x]) {
        if(proc[y] || y == p) continue;
        dfs(y, x, dep + 1, dis + w, flag);
    }
}
 
void solve(int x = 1, int p = -1) {
    int c = get_cen(x, p, get_sz(x, p));
    dp[0] = 0;
    for(auto [d, w] : adj[c]) {
        if(proc[d]) continue;
        dfs(d, c, 1, w, 0);
        dfs(d, c, 1, w, 1);
    }
    for(auto [d, w] : adj[c]) {
        if(proc[d]) continue;
        dfs(d, c, 1, w, 2);
    }
    dp[0] = mxN;
    proc[c] = 1;
    for(auto [d, w] : adj[c]) {
        if(proc[d]) continue;
        solve(d, c);
    }
}
 
int best_path(int N, int K, int H[][2], int L[])
{
    for(int i = 0; i < mxK; ++i) dp[i] = mxN;
    n = N; k = K;
    for(int i = 0; i < n - 1; ++i) {
        adj[H[i][0] + 1].emplace_back(H[i][1] + 1, L[i]);
        adj[H[i][1] + 1].emplace_back(H[i][0] + 1, L[i]);
    }
 
    solve();
    return (ans > n - 1 ? -1 : ans);
}

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