Submission #175896

#	Time	Username	Problem	Language	Result	Execution time	Memory
175896		muhammad_hokimiyon	Race (IOI11_race)	C++14	100 / 100	591 ms	35560 KiB

race

#include <bits/stdc++.h>
#include "race.h"
 
#define fi first
#define se second
#define ll long long
 
using namespace std;
 
const int N = 2e5 + 7;
const int NN = 1e6 + 7;
const int mod = 1e9 + 7;
 
int n,k;
int ans = 1e9;
bool used[N];
int sz[N];
int m[NN];
vector < pair < int , int > > v[N];
 
void dfs( int x , int p , int d , vector < pair < int , int > > &t , int sum )
{
    if( sum > k )return;
    t.push_back({sum , d});
    for( auto y : v[x] ){
        if( y.fi != p && !used[y.fi] ){
            dfs(y.fi , x , d + 1 , t , sum + y.se);
        }
    }
}
 
int centr( int x , int p , int n )
{
    for( auto y : v[x] ){
        if( y.fi != p && !used[y.fi] && sz[y.fi] > n / 2 ){
            return centr(y.fi , x , n);
        }
    }
    return x;
}
 
void siz( int x , int p )
{
    sz[x] = 1;
    for( auto y : v[x] ){
        if( y.fi == p || used[y.fi] )continue;
        siz(y.fi , x);
        sz[x] += sz[y.fi];
    }
}
vector < int > g;
 vector < pair < int , int > > t;
void solve( int x )
{
    siz(x , x);
  	g.clear();
    for( auto y : v[x] ){
        if(used[y.fi]) continue;
        t.clear();
        dfs(y.fi , x , 1 , t , y.se);
        for( auto it : t ){
            if( it.fi < k ){
                if( m[k - it.fi] != mod ){
                    ans = min(ans , m[k - it.fi] + it.se);
                }
            }else if( it.fi == k ){
                ans = min(ans , it.se);
            }
        }
        for( auto it : t ){
            if( it.fi >= k )continue;
            m[it.fi] = min( m[it.fi] , it.se );
            g.push_back(it.fi);
        }
    }
    for( auto y : g ){
        m[y] = mod;
    }
    used[x] = true;
    for( auto y : v[x] ){
        if( !used[y.fi] ){
            solve(centr(y.fi , x , sz[y.fi]));
        }
    }
}
 
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];
        int y = H[i][1];
        int z = L[i];
        x++,y++;
        v[x].push_back({y , z});
        v[y].push_back({x , z});
    }
    for( int i = 0; i < NN; i++ ){
        m[i] = mod;
    }
    siz(1 , 1);
    solve(centr(1 , 1 , n));
    if( ans == 1e9 )ans = -1;
    return ans;
}

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