이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "race.h"
#include <unordered_map>
#include <vector>
#include <iostream>
using namespace std;
typedef long long ll;
vector<pair<ll, ll>> graf[200005];
unordered_map<ll, ll> mp;
bool rmv[200005];
ll sz[200005];
ll rez = -1;
ll k = 0;
ll sbsz(ll u, ll p)
{
sz[u] = 1;
for (auto [v, w] : graf[u])
{
if (rmv[v] || v == p)
continue;
sz[u] += sbsz(v, u);
}
return sz[u];
}
ll gct(ll u, ll vel, ll p)
{
for (auto [v, w] : graf[u])
{
if (rmv[v] || v == p)
continue;
if (sz[v]*2 > vel)
return gct(v, vel, u);
}
return u;
}
void dfs(ll u, ll tr, ll gl, ll p, bool polni)
{
if (tr > k)
return;
if (polni)
{
if (mp.find(tr) == mp.end())
mp[tr] = gl;
else
mp[tr] = min(mp[tr], gl);
}
else
{
if (mp.find(k-tr) != mp.end())
rez = min((rez == -1 ? gl+mp[k-tr] : rez), gl+mp[k-tr]);
}
for (auto [v, w] : graf[u])
{
if (rmv[v] || v == p)
continue;
dfs(v, tr+w, gl+1, u, polni);
}
}
void decom(ll u)
{
ll ct = gct(u, sbsz(u, -1), -1);
mp.clear();
rmv[ct] = 1;
mp[0] = 0;
for (auto [v, w] : graf[ct])
{
if (rmv[v])
continue;
dfs(v, w, 1, u, false);
dfs(v, w, 1, u, true);
}
for (auto [v, w] : graf[ct])
if (!rmv[v])
decom(v);
return;
}
int best_path(int N, int K, int H[][2], int L[])
{
ll n = N;
k = K;
for (ll i = 0; i < n-1; i++)
{
ll u = H[i][0], v = H[i][1];
ll w = L[i];
// cout << "--> " << u << " " << v << " " << w << "\n";
graf[u].push_back({v, w});
graf[v].push_back({u, w});
}
mp.clear();
decom(0);
return rez;
}
컴파일 시 표준 에러 (stderr) 메시지
race.cpp: In function 'll sbsz(ll, ll)':
race.cpp:19:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
19 | for (auto [v, w] : graf[u])
| ^
race.cpp: In function 'll gct(ll, ll, ll)':
race.cpp:30:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
30 | for (auto [v, w] : graf[u])
| ^
race.cpp: In function 'void dfs(ll, ll, ll, ll, bool)':
race.cpp:56:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
56 | for (auto [v, w] : graf[u])
| ^
race.cpp: In function 'void decom(ll)':
race.cpp:70:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
70 | for (auto [v, w] : graf[ct])
| ^
race.cpp:77:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
77 | for (auto [v, w] : graf[ct])
| ^
# | 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... |