Submission #896702

#	Time	Username	Problem	Language	Result	Execution time	Memory
896702		ivaziva	Race (IOI11_race)	C++14	0 / 100	2 ms	10048 KiB

race

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

using namespace std;

#define MAXN 200010

long long n;
long long k;
vector<pair<long long,long long>> adj[MAXN];
long long siz[MAXN];
bool pos[MAXN];
long long dp[MAXN];
vector<long long> vec;
long long ans=-1;

long long dfs(long long node,long long pret)
{
    if (pos[node]==true) return 0;
    siz[node]=1;
    long long s=adj[node].size();
    for (long long i=0;i<s;i++)
    {
        long long sled=adj[node][i].first;
        if (sled!=pret) siz[node]+=dfs(sled,node);
    }
    return siz[node];
}

long long find_centroid(long long node,long long pret,long long val)
{
    long long s=adj[node].size();
    for (long long i=0;i<s;i++)
    {
        long long sled=adj[node][i].first;
        if (sled!=pret and pos[sled]==false and siz[sled]*2>val) return find_centroid(sled,node,val);
    }
    return node;
}

void calc(long long node,long long pret,long long dist,long long a,long long b)
{
    if (dist>k) return;
    if (b==1)
    {
        if (dp[dist]==-1) dp[dist]=a;
        else dp[dist]=min(dp[dist],a);
        vec.push_back(dist);
    }
    else
    {
        if (dp[k-dist]!=-1)
        {
            if (ans==-1) ans=dp[k-dist]+a;
            else ans=min(ans,dp[k-dist]+a);
        }
    }
    long long s=adj[node].size();
    for (long long i=0;i<s;i++)
    {
        long long sled=adj[node][i].first;
        long long w=adj[node][i].second;
        if (sled!=pret and pos[sled]==false) calc(sled,node,dist+w,a+1,b);
    }
}

void centroid_decomposition(long long node)
{
    dfs(node,-1);
    long long centroid=find_centroid(node,-1,siz[node]);
    pos[centroid]=true;
    long long s=adj[centroid].size();
    for (long long i=0;i<s;i++)
    {
        long long sled=adj[node][i].first;
        long long w=adj[node][i].second;
        if (pos[sled]==false)
        {
            calc(sled,centroid,w,1,0);
            calc(sled,centroid,w,1,1);
        }
    }
    s=vec.size();
    for (long long i=0;i<s;i++) dp[vec[i]]=-1;
    vec.clear();
    s=adj[centroid].size();
    for (long long i=0;i<s;i++)
    {
        long long sled=adj[centroid][i].first;
        if (pos[sled]==false) centroid_decomposition(sled);
    }
}

int best_path(int N, int K, int H[][2], int L[])
{
    n=(long long)N; k=(long long)K;
    for (long long i=0;i<n;i++)
    {
        long long x=(long long)H[i][0]+1;
        long long y=(long long)H[i][1]+1;
        long long z=(long long)L[i];
        adj[x].push_back({y,z});
        adj[y].push_back({x,z});
    }
    for (long long i=1;i<=n;i++) dp[i]=-1;
    dp[0]=0; centroid_decomposition(1);
    return ans;
}

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