Submission #1293635

#	Time	Username	Problem	Language	Result	Execution time	Memory
1293635		stathiskons	Race (IOI11_race)	C++20	0 / 100	0 ms	332 KiB

race

// 

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using pi = pair<int, int>;

int k;
vector<vector<pi>> adj;
vector<int> sz;
vector<bool> erased;
// vector<map<int, int>> children;
map<int, int> children;

int ans = INT_MAX;

void get_sz(int i, int p) {
    sz[i] = 1;
    for(auto [u, c] : adj[i]) {
        if(u == p || erased[u]) continue;

        get_sz(u, i);
        sz[i] += sz[u];
    }
}

int centroid(int i, int p, int n) {
    for(auto [u, c] : adj[i]) {
        if(u == p || erased[u]) continue;

        if(sz[u] > n/2) return centroid(u, i, n);
    }
    return i;
}

void dfs(int i, int p, ll d, int steps, bool add) {
    if(d > k) return;
    if(add) {
        auto it = children.find(d);
        if(it == children.end()) children[d] = steps;
        else it->second = min(it->second, steps);
    } else {
        auto it = children.find(k - d);
        if(it != children.end()) ans = min(ans, steps + it->second);
    }

    for(auto [u, c] : adj[i]) {
        if(u == p || erased[u]) continue;

        dfs(u, i, d + c, steps + 1, add);
    }
}

void decompose(int i) {
    get_sz(i, i);
    i = centroid(i, i, sz[i]);

    children.clear();
    children[0] = 0;
    for(int add = 0 ; add < 2 ; add++) {
        for(auto [u, c] : adj[i]) {
            if(erased[u]) continue;
            
            dfs(u, i, c, 1, false);
        }
    }
        
    erased[i] = true;

    for(auto [u, c] : adj[i]) {
        if(!erased[u]) decompose(u);
    }
}

int best_path(int n, int K, int edges[][2], int l[]) {
    k = K;
    adj.resize(n + 1);
    for(int i = 0 ; i < n - 1 ; i++) {
        int a = edges[i][0];
        int b = edges[i][1];
        int c = l[i];

        adj[a].emplace_back(b, c);
        adj[b].emplace_back(a, c);
    }

    sz.resize(n + 1);
    erased.resize(n + 1);

    decompose(1);

    if(ans == INT_MAX) ans = -1;
    return ans;
}


// int main(void) {
//     ios_base::sync_with_stdio(false);
//     cin.tie(NULL);

//     int t; cin >> t; while(t--) solve();
    
//     return 0;
// }

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