Submission #1166130

#	Time	Username	Problem	Language	Result	Execution time	Memory
1166130		duccnamm	Race (IOI11_race)	C++20	100 / 100	885 ms	42564 KiB

race

#include<bits/stdc++.h>
#include "race.h"
using namespace std;
#define ll int
ll n,m,u,v,w,child[200005],ans,d;
vector<pair<ll,ll>>a[200005];
bool del[200005];
map<ll,ll>mp;
vector<pair<ll,ll>>vc;
void dfsmake(ll x,ll pa)
{
    child[x]=1;
    for(pair<ll,ll> it:a[x])
        if(del[it.first]==0&&it.first!=pa)
        {
            dfsmake(it.first,x);
            child[x]+=child[it.first];
        }
}
ll getcentroid(ll x,ll pa,ll n)
{
    for(pair<ll,ll> it:a[x])
        if(it.first!=pa&&del[it.first]==0&&child[it.first]>n/2)
            return getcentroid(it.first,x,n);
    return x;
}
void dfsgetans(ll x,ll pa,ll dist)
{
//    cout<<d<<" "<<m-d<<'\n';
    if(m-d<0)
        return;
    vc.push_back({d,dist});
//    cout<<m-d<<" "<<d<<" "<<mp[m-d]<<' '<<dist<<'\n';
    if(m-d==0)
        ans=min(ans,dist);
    else if(mp[m-d]!=0)
        ans=min(ans,dist+mp[m-d]);
    for(pair<ll,ll> it:a[x])
        if(it.first!=pa&&del[it.first]==0)
        {
            d+=it.second;
            dfsgetans(it.first,x,dist+1);
            d-=it.second;
        }
}
void dfscentroid(ll x,ll pa)
{
    dfsmake(x,0);
    ll u=getcentroid(x,0,child[x]);
    for(pair<ll,ll> it:a[u])
        if(del[it.first]==0)
        {
            d=it.second;
            dfsgetans(it.first,u,1);
            for(pair<ll,ll>it:vc)
            {
                if(mp[it.first]==0)
                    mp[it.first]=it.second;
                else
                    mp[it.first]=min(mp[it.first],it.second);
            }
            vc.clear();
        }
    mp.clear();
//    cout<<u<<" "<<ans<<'\n';
    del[u]=1;
    for(pair<ll,ll> it:a[u])
        if(del[it.first]==0)
            dfscentroid(it.first,u);
}
int best_path(int N,int M,int H[][2],int L[])
{
    m=M;
    n=N;
    for(int i=0;i<=n-2;i++)
    {
        u=H[i][0]+1;
        v=H[i][1]+1;
        w=L[i];
//        cout<<u<<" "<<v<<" "<<w<<'\n';
        a[u].push_back({v,w});
        a[v].push_back({u,w});
    }
    ans=1e9;
    dfscentroid(n,0);
    if(ans!=1e9)
        return ans;
    return -1;
}
//int main()
//{
//    int HH[10005][2];
//    HH[0][0]=0;
//    HH[0][1]=1;
//    HH[1][0]=1;
//    HH[1][1]=2;
//    HH[2][0]=1;
//    HH[2][1]=3;
//
//    int LH[10005];
//    LH[0]=1;
//    LH[1]=2;
//    LH[2]=4;
//    cout<<best_path(4,3,HH,LH);
//}
//

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