이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
template< class T, class T2 > inline bool chkmin( T& a, const T2& b ){ return a > b ? a = b, 1 : 0 ; }
#ifndef LOCAL
#define cerr if( false )cerr
#endif
#define out(x) #x << " = " << x << " "
typedef long long ll;
const int MAX_N = 1e5 + 42;
const ll mod = 1e9 + 7;
int n, k;
std::vector< std::pair< int , int >> v[MAX_N];
int l[MAX_N];
bool viz[MAX_N];
int sz[MAX_N];
void dfs( int x, int par = -1 ){
sz[x] = 1;
for( auto J : v[x] ){
int j = J.first;
if( j == par || viz[j] ) continue;
dfs( j, x );
sz[x] += sz[j];
}
}
int centroid( int x, int SZ, int par = -1 ){
for( auto J : v[x] ){
int j = J.first;
if( j == par || viz[j] ) continue;
if( sz[j] > ( SZ / 2 ) ) return centroid( j, SZ, x );
}
return x;
}
std::unordered_map< int , int >m;
ll nas = mod;
void findNas( int x, bool type, int len, int par = -1, int d = 1 ){
auto pos = m.find( k - len );
if( type ){
if( pos != m.end() ){
chkmin( nas, d + pos->second );
}
}else m[len] = d;
for( auto J : v[x] ){
int j = J.first;
if( j == par || viz[j] ) continue;
findNas( j, type, len + J.second, x, d + 1 );
}
}
void centDecomp( int x, int par = -1 ){
dfs( x );
int c = centroid( x, sz[x] );
viz[c] = true;
m[0] = 0;
for( auto J : v[c] ){
int j = J.first;
if( viz[j] ) continue;
findNas( j, true , J.second);
findNas( j, false, J.second );
}
m.clear();
for( auto J : v[c] ){
int j = J.first;
if( viz[j] ) continue;
centDecomp( j, c );
}
}
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 a = H[i][0];
int b = H[i][1];
v[a].push_back({ b, L[i] });
v[b].push_back({ a, L[i] });
}
centDecomp( 0 );
if( nas == mod ) nas = -1;
return nas;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |