| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 859765 | vladburac | 경주 (Race) (IOI11_race) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
//#include "race.h"
#define int long long
using namespace std;
using ll = long long;
const int NMAX = 2e5;
const int INF = 1e9;
const int MAXLOG = 18;
int parent[NMAX+1];
bool is_removed[NMAX+1];
int sz[NMAX+1];
vector <pair<ll, int>> distSubtree[NMAX+1];
vector <pair<int, int>> edges[NMAX+1];
vector<int> centroidEdges[NMAX+1];
int calcSize( int node, int parent ) {
sz[node] = 1;
for( auto vec: edges[node] ) {
if( vec.first != parent && !is_removed[vec.first] )
sz[node] += calcSize( vec.first, node );
}
return sz[node];
}
int find_centroid( int node, int parent, int totalSz ) {
for( auto vec: edges[node] ) {
if( vec.first != parent && !is_removed[vec.first] && sz[vec.first] > totalSz / 2 )
return find_centroid( vec.first, node, totalSz );
}
return node;
}
struct Ancestor{
ll sum;
int length;
};
Ancestor anc[NMAX+1][MAXLOG+3];
int depth[NMAX+1];
void updDist( int init, int node, int parent, int dep, ll sumEdges ) {
distSubtree[init].push_back( { sumEdges, node } );
anc[node][depth[init]] = { sumEdges, dep };
for( auto vec: edges[node] ) {
if( !is_removed[vec.first] && vec.first != parent )
updDist( init, vec.first, node, dep + 1, sumEdges + vec.second );
}
}
void decomposition( int node, int centroidParent, int dep ) {
int totalSz = calcSize( node, -1 );
int centroid = find_centroid( node, -1, totalSz );
depth[centroid] = dep;
is_removed[centroid] = true;
parent[centroid] = centroidParent;
centroidEdges[centroid].push_back( centroidParent );
centroidEdges[centroidParent].push_back( centroid );
updDist( centroid, centroid, -1, 0, 0 );
for( auto vec: edges[centroid] ) {
//cout << vec.first << " ";
if( !is_removed[vec.first] )
decomposition( vec.first, centroid, dep + 1 );
}
}
map<ll, int> dp;
int ans = INF;
void dfs( int node, int i, int type, int k ) {
ll sum = anc[node][depth[i]].sum;
int length = anc[node][depth[i]].length;
if( type == 0 && dp[k-sum] )
ans = min( ans, dp[k-sum] + length );
else if( type == 1 ) {
if( dp[sum] )
dp[sum] = min( dp[sum], length );
else
dp[sum] = length;
}
for( auto vec: centroidEdges[node] ) {
if( vec != parent[node] )
dfs( vec, i, type, k );
}
}
int best_path( int n, int k, int h[][2], int len[] ) {
int i;
for( i = 0; i < n - 1; i++ ) {
edges[h[i][0]].push_back( { h[i][1], len[i] } );
edges[h[i][1]].push_back( { h[i][0], len[i] } );
}
decomposition( 0, -1, 0 );
ans = INF;
for( i = 0; i < n; i++ ) {
dp.clear();
for( auto vec: centroidEdges[i] ) {
if( vec != parent[i] ) {
dfs( vec, i, 0, k );
dfs( vec, i, 1, k );
}
}
}
if( ans == INF )
ans = -1;
return ans;
}