Submission #210664

#	Time	Username	Problem	Language	Result	Execution time	Memory
210664		robinrst	Race (IOI11_race)	C++14	100 / 100	2632 ms	103672 KiB

race

#include<bits/stdc++.h>
using namespace std;
 
int n,k;
vector<int>to [200005];
vector<int>len[200005];
long long deep[200005];
int Dep[200005];
int size[200005];
int son [200005];
int nid [200005];
int id  [200005];
int cnt;
 
map< long long,int >dep;
int ans = 1e9;
 
void dfs1(int now,int last)
{
    size[now] = 1;
    id  [now] = ++ cnt;
    nid [cnt] = now;
    int mx = 0;
    for(int i = 0;i < to[now].size();i ++)
    {
        int next = to[now][i];
        if( next == last )continue;
 
        deep[next] = deep[now] + len[now][i];
        Dep[next] = Dep[now] + 1;
        dfs1( next,now );
 
        size[now] += size[next];
        if( size[next] > mx )
        {
            mx = size[next];
            son[now] = next;
        }
    }
}
 
void updata(int x,int k)
{
    int dx = deep[x];
    if( k == -1 )
    {
        dep[ dx ] = 0;
    }
    else
    {
        int tmp = dep[dx];
        if( tmp == 0 )tmp = 1e9;
        dep[dx] = min( tmp,Dep[x] );
    }
}
 
void dfs2(int now,int last,bool keep)
{
    for(auto next : to[now])
    {
        if( next == son[now] or next == last )continue;
        dfs2( next,now,0 );
    }
 
    if( son[now] )dfs2( son[now],now,1 );
 
    for(auto next : to[now])
    {
        if( next == son[now] or next == last )continue;
 
        for( int i = 0;i < size[next];i ++ )
        {
            int nxt = nid[ id[next] + i ];
            int req = k +  deep[now] - deep[nxt] + deep[now];
            if( dep[ req ] )
            {
                ans = min( ans,dep[ req ] + Dep[nxt] - 2 * Dep[now] );
            }
        }
        for( int i = 0;i < size[next];i ++)
        {
            updata( nid[ id[next] + i ],1 );
        }
    }
    updata( now,1 );
 
    if( dep[ deep[now] + k ] ) ans = min( ans,dep[ deep[now] + k ] - Dep[now] );
 
    if( keep == 0 )
    {
        for( int i = 0;i < size[now];i ++ ){
            updata( nid[ id[now] + i ],-1 );
        }
    }
}
 
int best_path(int N, int K, int H[][2], int L[]){
    n = N, k = K;
    for(int i = 0;i < n-1;i ++)
    {
        to[H[i][0]].push_back( H[i][1] );
        to[H[i][1]].push_back( H[i][0] );
      	len[H[i][0]].push_back(L[i]);
      	len[H[i][1]].push_back(L[i]);
    }
    dfs1(0,0);dfs2(0,0,0);
    if( ans == 1e9 )ans = -1;
    return ans;
}

Compilation message (stderr)

race.cpp: In function 'void dfs1(int, int)':
race.cpp:24:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0;i < to[now].size();i ++)
                   ~~^~~~~~~~~~~~~~~~

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