Submission #1249108

#	Time	Username	Problem	Language	Result	Execution time	Memory
1249108		nguyendinhbach	Race (IOI11_race)	C++20	100 / 100	664 ms	57156 KiB

race

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define siz(x) (long long)(x.size())
#define all(x) x.begin(), x.end()
#define debug_arr(x,len) for(long long _=1; _<=len; _++) cout<<x[_]<<" "; cout<<'\n';
#define debug(x) cout<<'\n'<<#x<<": "<<x<<'\n';
const long long maxN = 1e6+5;

long long n, k, sz[maxN], mx_weight = 0, ans = 0, cur_min = 1e18;
long long cnt[maxN];
bool del[maxN];
vector<pair<long long,long long>>adj[maxN];

void dfs(long long u, long long v)
{
    sz[u] = 1;
    for(auto [i, val]: adj[u])
    {
        if(i == v || del[i]) continue;
        dfs(i, u);
        sz[u] += sz[i];
    }
}

long long find_centroid(long long u, long long v, long long total)
{
    for(auto [i, val]: adj[u])
    {
        if(i == v || del[i]) continue;
        if(sz[i] > total/2) return find_centroid(i, u, total);
    }
    return u;
}

void update(long long u, long long v, long long weight, bool type, long long layer)
{
    if(weight > k) return;
    mx_weight = max(mx_weight, weight);
    if(type == 1)
    {
        cnt[weight] = min(cnt[weight], layer);
    }
    else
    {
        long long xet = layer + cnt[k-weight];
        cur_min = min(cur_min, xet);
    }
    for(auto [i, val]: adj[u])
    {
        if(i == v || del[i]) continue;
        update(i, u, weight + val, type, layer+1);
    }
}

void cal(long long u)
{
    dfs(u, 0);
    long long root = find_centroid(u, 0, sz[u]);
    mx_weight = -1e18; cnt[0] = 0; del[root] = 1;
    for(auto [i, val]: adj[root])
    {
        if(del[i]) continue;
        update(i, root, val, 0, 1);
        update(i, root, val, 1, 1);
    }
    for(long long i=0; i<=mx_weight; i+=1) cnt[i] = 1e18;
    for(auto [i, val]: adj[root])
    {
        if(del[i]) continue;
        cal(i);
    }
}

// long long32_t main()
// {
//     ios_base::sync_with_stdio(0); cin.tie(0);
//     cin>>n>>k;
//     for(long long i=1; i<=k; i+=1) cnt[i] = 1e18;
//     for(long long i=1; i<n; i+=1)
//     {
//         long long x,y,w;
//         cin>>x>>y>>w; x++; y++;
//         adj[x].push_back({y,w});
//         adj[y].push_back({x,w});
//         // cout<<x<<" "<<y<<" "<<w<<'\n';
//     }
//     cal(1);
//     if(cur_min == 1e18) cout<<-1<<'\n';
//     else cout<<cur_min<<'\n';
// }

int best_path(int N, int K, int H[][2], int L[])
{
    n = N; k = K;
    for(long long i=1; i<=k; i+=1) cnt[i] = 1e18;
    for(long long i=0; i<n-1; i+=1)
    {
        long long x,y,w;
        x = H[i][0], y = H[i][1], w = L[i];
        x++; y++;
        adj[x].push_back({y,w});
        adj[y].push_back({x,w});
        // cout<<x<<" "<<y<<" "<<w<<'\n';
    }
    cal(1);
    if(cur_min == 1e18) return -1;
    else return cur_min;
}

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