이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include "race.h"
#define ve vector
#define ll long long
#define fi first
#define se second
using namespace std;
typedef pair<ll, ll> pll;
const int MAXN = 1e6 + 10;
ll k;
ve<pll> g[MAXN];
map<ll, ll> st[MAXN];
ll res;
void dfs(int v, int p){
pll mx = {-1, -1};
for(auto& to : g[v])
if(to.fi != p){
dfs(to.fi, v);
if(st[v].find(k - to.se) != st[v].end())
res = min(res, st[v][k - to.se] + 1);
for(auto& i : st[to.fi]){
if(st[v].find(k - (i.fi + to.se)) != st[v].end())
res = min(res, i.se + 1 + st[v][k - (i.fi + to.se)]);
}
st[v][to.se] = 1;
for(auto i : st[to.fi])
st[v][i.fi + to.se] = min(st[v][i.fi + to.se], i.se + 1);
}
if(st[v].find(k) != st[v].end())
res = min(res, st[v][k]);
}
int best_path(int N, int K, int H[][2], int L[])
{
k = K;
res = 1e18;
for(int i = 0; i < N; i++){
g[i].clear();
// delete(st[i]);
st[i].clear();
}
for(int i = 0; i < N - 1; i++){
g[H[i][0]].push_back({H[i][1], L[i]});
g[H[i][1]].push_back({H[i][0], L[i]});
}
dfs(0, 0);
return res == 1e18 ? -1 : res;
}
컴파일 시 표준 에러 (stderr) 메시지
race.cpp: In function 'void dfs(int, int)':
race.cpp:21:9: warning: variable 'mx' set but not used [-Wunused-but-set-variable]
21 | pll mx = {-1, -1};
| ^~
# | 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... |