Submission #1231630

#	Time	Username	Problem	Language	Result	Execution time	Memory
1231630		AMel0n	Race (IOI11_race)	C++20	0 / 100	1 ms	320 KiB

race

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
#define FOR(i,N) for(ll i = 0; i < N; i++)
#define all(x) (x).begin(), (x).end()
#define F first
#define S second


#include "race.h"
// centroid decomp & dp => O(N * log^2 N)

int N, K, res = INT_MAX;
vector<vector<pair<int,int>>> adj;
vector<int> sz;
vector<bool> del;

int dfsSZ(int n, int p) {
    sz[n] = 1;
    for(auto [c, l]: adj[n]) {
        if (c == p) continue;
        sz[n] += dfsSZ(c, n);
    }
    return sz[n];
}

int dfsCEN(int n, int p, int treeSZ) {
    for(auto [c, l]: adj[n]) {
        if (c == p || del[c] || sz[c] * 2 <= treeSZ) continue;
        return dfsCEN(c, n, treeSZ);
    }
    return n;
}

void solve(int n, int p, int dist, int dep, unordered_map<int,int> &d) {
    if (dist > K) return ;
    if (d.find(dist) == d.end() || d[dist] > dep) d[dist] = dep;
    if (dist == K) {res = min(res, dep); return ;}
    for(auto [c, l]: adj[n]) {
        if (c == p || del[c]) continue;
        solve(c, n, dist+l, dep+1, d);
    }
}

void build(int n) {
    int cen = dfsCEN(n, n, dfsSZ(n, n));

    // for every centroid, there will be at most N' values (where N' = the number of nodes in the centroid)
    unordered_map<int,int> dp;
    for(auto [c, l]: adj[n]) {
        if (del[c]) continue;
        unordered_map<int,int> d;
        solve(c, cen, l, 1, d);
        for(auto [dist, dep]: d) {
            if (dp.find(K-dist) != dp.end()) res = min(res, dp[K-dist] + dep);
        }
        for(auto [dist, dep]: d) {
            if (dp.find(dist) == dp.end() || dp[dist] > dep) dp[dist] = dep;
        }
    }

    del[cen] = true;
    for(auto [c, l]: adj[n]) {
        if (del[c]) continue;
        build(c); 
    }
}

int best_path(int N, int K, int H[][2], int L[]) {
    ::N = N, ::K = K;
    adj.resize(N), sz.resize(N), del.resize(N);
    FOR(i, N-1) {
        adj[H[i][0]].push_back({H[i][1], L[i]});
        adj[H[i][1]].push_back({H[i][0], L[i]});
    }
    build(0);
    return (res == INT_MAX ? -1 : res);
}

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