Submission #1100281

#	Time	Username	Problem	Language	Result	Execution time	Memory
1100281		kokoue	Race (IOI11_race)	C++14	100 / 100	631 ms	36960 KiB

race

#include<bits/stdc++.h>
#include "race.h"
#define maxn 200010
#define maxk 1000010
#define f first
#define s second
#define ll long long
using namespace std;
int n,k;
int subsz[maxn],cnt[maxk];
bool is_cen[maxn];
int mx_sz=0;
int ans=INT_MAX;
vector<pair<int,int>> edges[maxn];
int get_size(int start,int parent=-1)
{
    int sz=1;
    for(auto e:edges[start])
    {
        if(e.f==parent || is_cen[e.f]) continue;
        sz+=get_size(e.f,start);
    }
    return subsz[start]=sz;
}
int find_centroid(int start,int tree_sz,int parent=-1)
{
    for(auto e:edges[start])
    {
        if(e.f==parent || is_cen[e.f]) continue;
        if(2*subsz[e.f]>tree_sz) return find_centroid(e.f,tree_sz,start);
    }
    return start;
}
void get_cnt(int start,bool filling,int parent,int dist,int depth=1)
{
    if(dist>k) return;
    mx_sz=max(mx_sz,dist);

    if(filling)
    {
        //cnt[depth]++;
        //if(cnt[dist]==INT_MAX) cnt[dist]
        cnt[dist]=min(cnt[dist],depth);
    }
    else if(cnt[k-dist]!=INT_MAX) ans=min(ans,cnt[k-dist]+depth);

    for(auto e:edges[start])
    {
        if(is_cen[e.f] || e.f==parent) continue;
        get_cnt(e.f,filling,start,dist+e.s,depth+1);
    }
}
void decomp(int start=1)
{
    int centroid=find_centroid(start,get_size(start));
    is_cen[centroid]=1;
    mx_sz=0;
    for(auto e:edges[centroid])
    {
        if(is_cen[e.f]) continue;
        get_cnt(e.f,false,centroid,e.s);
        get_cnt(e.f,true,centroid,e.s);
    }
    for(int i=1;i<=mx_sz;i++) cnt[i]=INT_MAX;
    for(auto e:edges[centroid])
    {
        if(is_cen[e.f]) continue;
        decomp(e.f);
    }
}
int best_path(int N,int K,int H[][2],int L[])
{
    /*ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>k;*/
    n=N;
    k=K;
    for(int i=1;i<=k;i++) cnt[i]=INT_MAX;
    for(int i=0;i<n-1;i++)
    {
        int a=H[i][0],b=H[i][1],w=L[i];
        //cin>>a>>b>>w;
        a++;
        b++;
        edges[a].push_back({b,w});
        edges[b].push_back({a,w});
    }
    decomp();
    if(ans!=INT_MAX) return ans;
    else return -1;
}
/*
3 3
0 1 1
1 2 1
*/
/*
11 12
0 1 3
0 2 4
2 3 5
3 4 4
4 5 6
0 6 3
6 7 2
6 8 5
8 9 6
8 10 7
*/

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