이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include "race.h"
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,avx2,bmi,bmi2,fma,sse,sse2,sse4")
using namespace std;
typedef long long ll;
vector<pair<ll,ll>> adj[200001];
ll sz[200001];
bool marked[200001]={0};
ll m[1000001];
ll k;
ll dfs_sizes(ll v, ll pV){
sz[v]=1;
for(auto [w,d] : adj[v]){
if(w!=pV&&!marked[w]){
sz[v]+=dfs_sizes(w,v);
}
}
return sz[v];
}
ll dfs_centroid(ll v, ll pV, ll subtree_sz){
for(auto [w,d] : adj[v]){
if(pV!=w&&!marked[w]&&sz[w]>=(subtree_sz/2)){
return dfs_centroid(w,v,subtree_sz);
}
}
return v;
}
void dfs_paths(ll v, ll pV,ll dist,ll l, vector<pair<ll,ll>> &a){
if(dist<=k)a.push_back({dist,l});
for(auto [w,d] : adj[v]){
if(w!=pV&&!marked[w]){
if(dist+d<=k){
dfs_paths(w,v,dist+d,l+1,a);
}
}
}
}
ll centroid_decomposition(ll v){
ll c = dfs_centroid(v,v,dfs_sizes(v,v));
marked[c]=1;
ll ans=1000001;
vector<ll> sus;
m[0]=0;
for(auto [w,d] : adj[c]){
if(!marked[w]){
vector<pair<ll,ll>> a;
a.push_back({0,0});
dfs_paths(w,c,d,1,a);
for(auto [dist,l] : a){
if(m[k-dist]!=1000001){
ans=min(ans,l+m[k-dist]);
}
}
for(auto [dist,l] : a){
if(m[dist]!=1000001)m[dist]=min(m[dist],l);
else{
m[dist]=l;
sus.push_back(dist);
}
}
}
}
for(ll i : sus)m[i]=1000001;
m[0]=0;
for(auto [w,d] : adj[c]){
if(!marked[w]){
ans = min(ans,centroid_decomposition(w));
}
}
return ans;
}
int best_path(int N, int K, int H[][2], int L[]){
for(ll i=0;i<N-1;i++){
adj[H[i][0]].push_back({H[i][1],L[i]});
adj[H[i][1]].push_back({H[i][0],L[i]});
}
k=K;
for(ll i=0;i<=k;i++)m[i]=1000001;
m[0]=0;
ll ans = centroid_decomposition(0);
return (ans==1000001?-1:ans);
}
컴파일 시 표준 에러 (stderr) 메시지
race.cpp: In function 'll dfs_sizes(ll, ll)':
race.cpp:23:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
23 | for(auto [w,d] : adj[v]){
| ^
race.cpp: In function 'll dfs_centroid(ll, ll, ll)':
race.cpp:32:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
32 | for(auto [w,d] : adj[v]){
| ^
race.cpp: In function 'void dfs_paths(ll, ll, ll, ll, std::vector<std::pair<long long int, long long int> >&)':
race.cpp:42:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
42 | for(auto [w,d] : adj[v]){
| ^
race.cpp: In function 'll centroid_decomposition(ll)':
race.cpp:63:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
63 | for(auto [w,d] : adj[c]){
| ^
race.cpp:70:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
70 | for(auto [dist,l] : a){
| ^
race.cpp:75:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
75 | for(auto [dist,l] : a){
| ^
race.cpp:88:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
88 | for(auto [w,d] : adj[c]){
| ^
# | 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... |