Submission #1139450

#	Time	Username	Problem	Language	Result	Execution time	Memory
1139450		turska	Race (IOI11_race)	C++20	100 / 100	613 ms	36432 KiB

race

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

using namespace std;
using ll = long long;
const int maxN = 2e5+1;

using pii = pair<int, int>;
vector<pii> adj[maxN];
int sz[maxN], dead[maxN];
int n, k;
int ans = 1e9;
map<int, int> mn;

int calc_sz(int v, int p=0) {
    sz[v] = 1;
    for (auto [u, _]: adj[v]) if (!dead[u] && u!=p) sz[v] += calc_sz(u, v);
    return sz[v];
}
int find_cd(int v, int tree_sz, int p=0) {
    for (auto [u, _]: adj[v]) if (!dead[u] && u!=p) {
        if (sz[u]*2>tree_sz) return find_cd(u, tree_sz, v);
    } 
    return v;
}
void calc_dist(int v, int p, int dist, int dep, bool insert) {
    if(dist>k) return;
    if (insert) {
        if (mn.count(dist)) mn[dist] = min(mn[dist], dep);
        else mn[dist] = dep;
    } else {
        if (mn.count(k-dist)) ans = min(ans, mn[k-dist]+dep);
    }
    for (auto [u, w]: adj[v]) if (!dead[u] && u!=p)  calc_dist(u, v, dist+w, dep+1, insert);
}

void decomp(int v) {
    int cd = find_cd(v, calc_sz(v));
    mn[0] = 0;
    for (auto [u, w]: adj[cd]) if (!dead[u]) {
        calc_dist(u, cd, w, 1, false);
        calc_dist(u, cd, w, 1, true);
    }
    mn.clear();
    dead[cd] = true;
    for (auto [u, _]: adj[cd]) if (!dead[u]) decomp(u);
}


int best_path(int N, int K, int H[][2], int L[])
{
    n = N;
    k = K;
    for (int i=0; i<N-1; i++) {
        int u = H[i][0]+1;
        int v = H[i][1]+1;
        int w = L[i];
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }
    decomp(1);
    if (ans==1e9) return -1; 
    return ans;
}

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