이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define pii pair<int,int>
#define F first
#define S second
int n ,k ;
vector<pii> adj[200005];
long long ans = (long long) 1e18;
int sz[200005];
int dp[200005];
map<long long, int> tree[200005];
void pre_dfs(int x , int y){
sz[x] = 1;
dp[x] = dp[y] + 1;
for(int i = 0 ; i < adj[x].size() ; i++){
pii v = adj[x][i];
if(v.F == y) continue;
pre_dfs(v.F, x);
sz[x] += sz[v.F];
}
int maxxi = -1 , optmaxi = 0;
for(int i = 0 ; i < adj[x].size() ; i++){
pii v = adj[x][i];
if(v.F == y){
continue;
}
if(sz[v.F] >= maxxi){
optmaxi = i;
maxxi = sz[v.F];
}
}
if(x == y || adj[x].size() > 1)
swap(adj[x][0] , adj[x][optmaxi]);
}
void solve(int x , int y , long long d){
if(adj[x].size() == 1 && adj[x][0].F == y){
tree[x][d] = dp[x];
if(d == k) ans = min(ans , (long long) dp[x]);
}
else{
solve(adj[x][0].F , x , d + adj[x][0].S);
swap(tree[x] , tree[adj[x][0].F]);
for(int j = 1 ; j < adj[x].size() ; j++){
pii v = adj[x][j];
if(v.F == y) continue;
solve(v.F , x , v.S + d);
long long opt = k + 2*d;
queue<pii> q;
for(auto p : tree[v.F]){
if(tree[x].count(opt - p.F)){
ans = min(ans , (long long) p.S + tree[x][opt-p.F]- 2*dp[x]);
}
q.push(p);
}
while(!q.empty()){
pii p = q.front();
q.pop();
if(tree[x].count(p.F)) tree[x][p.F] = min(tree[x][p.F] , p.S);
else
tree[x][p.F] = p.S;
}
tree[v.F].clear();
}
if(tree[x].count(d)) tree[x][d] = min(tree[x][d] , dp[x]);
else tree[x][d] = dp[x];
if(tree[x].count(d + k)){ ans = min(ans , (long long) tree[x][d+k] - dp[x]);}
}
}
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 , y , z;
scanf("%d%d%d" , &x , &y , &z);
adj[H[i][0]].pb(pii(H[i][1],L[i]));
adj[H[i][1]].pb(pii(H[i][0],L[i]));
}
dp[0] = -1;
pre_dfs(0 , 0);
solve(0 , 0 , 0);
if(ans == (long long) 1e18) return -1;
else return ans;
}
컴파일 시 표준 에러 (stderr) 메시지
race.cpp: In function 'void pre_dfs(int, int)':
race.cpp:16:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0 ; i < adj[x].size() ; i++){
~~^~~~~~~~~~~~~~~
race.cpp:23:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0 ; i < adj[x].size() ; i++){
~~^~~~~~~~~~~~~~~
race.cpp: In function 'void solve(int, int, long long int)':
race.cpp:45:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 1 ; j < adj[x].size() ; j++){
~~^~~~~~~~~~~~~~~
race.cpp: In function 'int best_path(int, int, int (*)[2], int*)':
race.cpp:77:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d" , &x , &y , &z);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
# | 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... |