Submission #204859

#	Time	Username	Problem	Language	Result	Execution time	Memory
204859		mdn2002	Race (IOI11_race)	C++14	43 / 100	433 ms	78480 KiB

race

#include <bits/stdc++.h>
#include "race.h"
using namespace std;



long long n,k,dp[200500],siz[200500],dis[200500],mn=1e9;
vector<pair<long long,long long> >gr[200500];
multiset<pair<long long,long long> >v[200500];
multiset<pair<long long,long long> >::iterator it;
void cal(int x,int p)
{
    dp[x]=dp[p]+1;
    siz[x]++;
    for(int i=0; i<gr[x].size(); i++)
    {
        long long u=gr[x][i].first,w=gr[x][i].second;
        if(u==p)continue;
        dis[u]=dis[x]+w;
        cal(u,x);
        siz[x]+=siz[u];
    }
}
void dfs(int x,int p)
{
    long long big=0,mx=-1;
    for(int i=0; i<gr[x].size(); i++)
    {
        long long u=gr[x][i].first;
        if(u==p)continue;
        if(mx<siz[u])
        {
            mx=siz[u];
            big=u;
        }
    }
    if(mx!=-1)dfs(big,x);
    swap(v[big],v[x]);
    v[x].insert({dis[x],dp[x]});
    pair<long long,long long>zz=*v[x].lower_bound(make_pair(k+dis[x],0ll));
    if(zz.first==k+dis[x]&&v[x].lower_bound(make_pair(k+dis[x],0ll))!=v[x].end())
    {
        long long add=zz.second-dp[x];
        mn=min(mn,add);
    }
    for(int i=0; i<gr[x].size(); i++)
    {
        long long u=gr[x][i].first;
        if(u==p||u==big)continue;
        dfs(u,x);
    }
    for(int i=0; i<gr[x].size(); i++)
    {
        long long u=gr[x][i].first;
        if(u==p||u==big)continue;
        for(it=v[u].begin(); it!=v[u].end(); it++)
        {
            pair<long long,long long>z=*it;
            long long dd=k-z.first+(2*dis[x]),add=z.second-dp[x];
            pair<long long,long long>zz=*v[x].lower_bound(make_pair(dd,0));
            if(zz.first==dd&&v[x].lower_bound(make_pair(dd,0ll))!=v[x].end())
            {
                long long add1=zz.second-dp[x];
                mn=min(mn,add1+add);
            }
            v[x].insert(z);
        }
    }
}
int best_path(int N, int K, int H[][2], int L[])
{
    n=N,k=K;
    for(int i=0; i<n-1; i++)
    {
        int x=H[i][0]+1,y=H[i][1]+1;
        gr[x].push_back({y,L[i]});
        gr[y].push_back({x,L[i]});
    }
    cal(1,0);
    dfs(1,0);
    if(mn!=1e9)return mn;
    else return -1;
}

Compilation message (stderr)

race.cpp: In function 'void cal(int, int)':
race.cpp:15:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<gr[x].size(); i++)
                  ~^~~~~~~~~~~~~
race.cpp: In function 'void dfs(int, int)':
race.cpp:27:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<gr[x].size(); i++)
                  ~^~~~~~~~~~~~~
race.cpp:46:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<gr[x].size(); i++)
                  ~^~~~~~~~~~~~~
race.cpp:52:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<gr[x].size(); i++)
                  ~^~~~~~~~~~~~~

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