Submission #1141270

#	Time	Username	Problem	Language	Result	Execution time	Memory
1141270		HasanV11010238	Race (IOI11_race)	C++20	21 / 100	3096 ms	44436 KiB

race

#include "race.h"
#include <bits/stdc++.h>
#define ll int
using namespace std;
int n, k, a, b;
vector<vector<vector<int>>> v;
vector<int> sts, isrem, rang;
int getsts(int x, int p){
    sts[x] = 1;
    for (auto ch : v[x]){
        if (isrem[ch[0]] == 0 && ch[0] != p){
            sts[x] += getsts(ch[0], x);
        }
    }
    return sts[x];
}
int getcentr(int x, int p){
    for (auto ch : v[x]){
        if (isrem[ch[0]] == 0 && ch[0] != p && sts[ch[0]] * 2 > sts[x]){
            return getcentr(ch[0], x);
        }
    }
    return x;
}
vector<ll> cnt;
vector<vector<ll>> di;
void dist(int x, int p, int de, ll le){
    if (le > k) return;
    di.push_back({le, de});
    for (auto ch : v[x]){
        if (isrem[ch[0]] == 0 && ch[0] != p){
            dist(ch[0], x, de + 1, le + ch[1]);
        }
    }
}
ll ans;
void decomposition(int x, int p){
    getsts(x, p);
    int centr = getcentr(x, p);
    isrem[centr] = 1;
    vector<vector<ll>> al;
    cnt[0] = 0;
    for (auto ch : v[centr]){
        if (isrem[ch[0]] == 1){
            continue;
        }
        di.clear();
        dist(ch[0], centr, 1, ch[1]);
        for (auto el : di){
            ans = min(ans, el[1] + cnt[k - el[0]]);
        }
        for (auto el : di){
            al.push_back(el);
            cnt[el[0]] = min(cnt[el[0]], el[1]);
        }
    }
    for (auto el : al){
        cnt[el[0]] = n + 1;
    }
    for (auto ch : v[centr]){
        if (isrem[ch[0]] == 0){
            decomposition(ch[0], x);
        }
    }
}
int best_path(int N, int K, int H[][2], int L[])
{
    n = N, k = K;
    ans = n + 1;
    v.assign(n + 1, vector<vector<ll>>());
    sts.assign(n + 1, 0), isrem.assign(n + 1, 0), cnt.assign(k + 1, n + 1);
    for (int i = 0; i < n - 1; i++){
        v[H[i][0]].push_back({H[i][1], L[i]});
        v[H[i][1]].push_back({H[i][0], L[i]});
    }
    decomposition(0, 0);
    if (ans >= n + 1) return -1;
    return ans;
}

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