Submission #321174

#	Time	Username	Problem	Language	Result	Execution time	Memory
321174		Kesatria_Komodo	Race (IOI11_race)	C++17	43 / 100	559 ms	41572 KiB

race

#include <iostream>
#include <vector>
#include <utility>
using namespace std;
vector<pair<int , int>> adjlist[200001];
bool used[200001];
int subtree[200001];
int ans = 1e9 , target;
int cnt_subtree(int node , int bef){
    subtree[node] = 1;
    for (const pair<int , int> &it : adjlist[node])
        if (it.first != bef && !used[it.first])subtree[node] += cnt_subtree(it.first , node);
    return subtree[node];
}
int cari_centroid(int node , int bef , const int &max_bound){
    for (const pair<int , int> &it : adjlist[node])
        if (!used[it.first] && it.first != bef && subtree[it.first] > max_bound)
            return cari_centroid(it.first , node , max_bound);
    return node;
}
void dfs(int node , int bef , int depth , int val , int min_len[]){
    if (min_len[target - val])
        ans = min(ans , depth + min_len[target - val] - 2);
    for (const pair<int , int> &it : adjlist[node])
        if (it.first != bef && !used[it.first] && val + it.second <= target)
            dfs(it.first , node , depth + 1 , val + it.second , min_len);
    if (!min_len[val])
        min_len[val] = depth;
    else min_len[val] = min(min_len[val] , depth);
}
void cari(int now){
    int centroid = cari_centroid(now , -1 , cnt_subtree(now , -1) >> 1);
    int min_len[target + 1] = {};
    min_len[0] = used[centroid] = 1;
    for (const pair<int , int> &it : adjlist[centroid])
        if (!used[it.first] && it.second <= target)
            dfs(it.first , centroid , 2 , it.second , min_len);
    for (const pair<int , int> &it : adjlist[centroid])
        if (!used[it.first])
            cari(it.first);
}
int best_path(int N, int K, int H[][2], int L[]) //K : adalah nilai yang dibutuhkan
{
    target = K;
    for (int i = 0 ; i < N - 1 ; ++i)
        adjlist[H[i][0]].push_back({H[i][1] , L[i]}),
        adjlist[H[i][1]].push_back({H[i][0] , L[i]});
    cari(0);
    return ans > 1e8 ? -1 : ans;
}
/*int main(){
    int N , K;
    cin >> N >> K;
    int arr[N - 1][2] , L[N - 1];
    for (int i = 0 ; i < N - 1 ; ++i)
        cin >> arr[i][0] >> arr[i][1];
    for (int i = 0 ; i < N - 1 ; ++i)
        cin >> L[i];
    cout << best_path(N , K , arr , L) << endl;

}*/

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