Submission #175569

#	Time	Username	Problem	Language	Result	Execution time	Memory
175569		muhammad_hokimiyon	Race (IOI11_race)	C++14	21 / 100	3010 ms	19632 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 = 1e7 + 7;
const int mod = 1e9 + 7;

int n,k;
int ans = 1e9;
bool used[N];
int sz[N];
map < int , int > m;
vector < pair < int , int > > v[N];

void dfs( int x , int p , int d , vector < pair < int , int > > &t , int sum )
{
    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];
    }
}

void solve( int x )
{
    siz(x , x);
    m.clear();
    for( auto y : v[x] ){
        vector < pair < int , int > > t;
        dfs(y.fi , x , 1 , t , y.se);
        for( auto it : t ){
            if( it.fi < k ){
                if( m.find(k - it.fi) != m.end() ){
                    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;
            if( m.find(it.fi) == m.end() )m[it.fi] = it.se;
            else m[it.fi] = min( m[it.fi] , it.se );
        }
    }
    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});
    }
    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: 0 / 22
• Subtask 4: 0 / 57