| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 571811 | vladislav11 | 경주 (Race) (IOI11_race) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n, ans;
ll k;
vector< vector<int> > ribs;
vector<int> l;
vector< vector< pair<int,int> > > grp;
vector<int> ssize, h;
vector<ll> pref;
int dfs_prec ( int v, int p )
{
for ( auto& [to,w] : grp[v] )
if ( to != p )
{
pref[to] = pref[v] + w;
h[to] = h[v] + 1;
ssize[v] += dfs_prec( to, v );
}
return ssize[v];
}
vector< vector<int>* > ver;
map<ll,int> mini;
void upd ( int in, int v )
{
ll len = pref[v] - pref[in];
if ( len == k )
ans = min( ans, h[v] - h[in] );
else if ( len < k && mini.count( pref[in] + k - len ) )
ans = min( ans, ( h[v] - h[in] ) + ( mini[ pref[in] + k - len ] - h[in] ) );
}
void add ( int v )
{
if ( mini.count( pref[v] ) )
mini[ pref[v] ] = min( mini[ pref[v] ], h[v] );
else
mini[ pref[v] ] = h[v];
}
void dfs ( int v, int p, bool keep )
{
int bigs = -1, bigv = -1;
for ( auto& [to,w] : grp[v] )
if ( to != p && ssize[to] > bigs )
{
bigs = ssize[to];
bigv = to;
}
for ( auto& [to,w] : grp[v] )
if ( to != p && to != bigv )
dfs( to, v, false );
if ( bigv == -1 )
ver[v] = new vector<int>();
else
{
dfs( bigv, v, true );
ver[v] = ver[bigv];
}
ver[v]->push_back( v );
for ( auto& [to,w] : grp[v] )
if ( to != p && to != bigv )
{
for ( auto& el : *ver[to] )
upd( v, el );
for ( auto& el : *ver[to] )
add( el );
}
if ( mini.count( pref[v] + k ) )
ans = min( ans, mini[ pref[v] + k ] - h[v] );
if ( !keep )
mini.clear();
}
int best_path ( int n_, int k_, vector< vector<int> > grp_, vector<int> l_ )
{
n = n_;
k = k_;
ribs.assign( grp_.begin(), grp_.end() );
l.assign( l_.begin(), l_.end() );
grp.assign( n, vector< pair<int,int> >() );
for ( int i=0; i<ribs.size(); i++ )
{
grp[ ribs[i][0] ].push_back({ ribs[i][1], l[i] });
grp[ ribs[i][1] ].push_back({ ribs[i][0], l[i] });
}
cout << "grp:\n";
for ( int i=0; i<grp.size(); i++ )
{
cout << i << ": ";
for ( auto& [to,w] : grp[i] )
cout << "(" << to << ' ' << w << ") ";
cout << '\n';
}
ssize.assign( n, 1 );
h.assign( n, 1 );
pref.assign( n, 0 );
dfs_prec( 0, -1 );
cout << "sszie: ";
for ( auto& el : ssize )
cout << el << ' ';
cout << '\n';
cout << "h: ";
for ( auto& el : h )
cout << el << ' ';
cout << '\n';
cout << "pref: ";
for ( auto& el : pref )
cout << el << ' ';
cout << '\n';
ver.assign( n, nullptr );
mini.clear();
ans = 1e9;
dfs( 0, -1, false );
return ans;
}
int main ()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int n_, k_;
vector< vector<int> > grp_;
vector<int> l_;
cin >> n_ >> k_;
grp_.assign( n_-1, vector<int>(2) );
l_.assign( n_-1, 0 );
for ( int i=0; i<n_-1; i++ )
cin >> grp_[i][0] >> grp_[i][1] >> l_[i];
cout << best_path( n_, k_, grp_, l_ );
return 0;
}
/**
4 3
0 1 1
1 2 2
1 3 4
*/