| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 712529 | tosivanmak | 경주 (Race) (IOI11_race) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define MAX 1e18
const ll Log=20;
map<pair<ll,ll>,ll>courselen;
ll subtree_size[200005],cenfa[200005];
bool visited[200005],visitedlca[200005];
vector<ll>adj[200005];
ll up[200005][25];
ll jumplen[200005][25];
ll fa[200005];
ll dist[200005];
map<ll,ll>foreachlength[200005];
map<ll,bool>visitedeachlength[200005];
vector<ll>have[200005];
void dfslca(ll s){
visitedlca[s]=true;
for(auto u: adj[s]){
if(!visitedlca[u]){
dist[u]=dist[s]+1;
fa[u]=s;
dfslca(u);
}
}
}
void precompute(ll n){
for(int i=1;i<=n;i++){
up[i][0]=fa[i];
}
for(int j=1;j<=Log;j++){
for(int i=1;i<=n;i++){
up[i][j]=up[up[i][j-1]][j-1];
}
}
for(int i=1;i<=n;i++){
jumplen[i][0]=courselen[{i,fa[i]}];
}
for(int j=1;j<=Log;j++){
for(int i=1;i<=n;i++){
jumplen[i][j]=jumplen[i][j-1]+jumplen[up[i][j-1]][j-1];
}
}
}
ll kthancestor(ll a, ll k){
for(int i=Log;i>=0;i--){
if(k-(1<<i)>=0){
k-=(1<<i);
a=up[a][i];
}
}
return a;
}
ll lca(ll a, ll b){
if(dist[a]<dist[b]){
swap(a,b);
}
ll k=dist[a]-dist[b];
a=kthancestor(a,k);
if(a==b){
return a;
}
else{
for(int i=Log;i>=0;i--){
if(up[a][i]!=up[b][i]){
a=up[a][i];
b=up[b][i];
}
}
return up[a][0];
}
}
//course track length from a to b
ll course(ll a, ll b){
if(dist[a]<dist[b]){
swap(a,b);
}
ll k=dist[a]-dist[b];
ll ans=0;
for(int i=Log;i>=0;i--){
if(k-(1<<i)>=0){
k-=(1<<i);
ans+=jumplen[a][i];
a=up[a][i];
}
}
if(a==b){
return ans;
}
else{
for(int i=Log;i>=0;i--){
if(up[a][i]!=up[b][i]){
ans+=jumplen[a][i];
ans+=jumplen[b][i];
a=up[a][i];
b=up[b][i];
}
}
ans+=jumplen[a][0];
ans+=jumplen[b][0];
return ans;
}
}
//end
void dfs(ll s, ll par){
subtree_size[s]=1;
for(auto u: adj[s]){
if(!visited[u]&&par!=u){
dfs(u,s);
subtree_size[s]+=subtree_size[u];
}
}
}
ll get_centroid(ll s, ll par, ll treesize){
for(auto u: adj[s]){
if(u!=par&&!visited[u]&&subtree_size[u]*2>treesize){
return get_centroid(u,s,treesize);
}
}
return s;
}
void centroid_decomposition(ll s, ll par){
dfs(s,-1);
ll k=get_centroid(s,-1,subtree_size[s]);
cenfa[k]=par;
visited[k]=true;
for(auto u: adj[k]){
if(!visited[u]){
centroid_decomposition(u,k);
}
}
}
void upd(ll node){
ll storenode=node;
while(storenode!=-1){
ll low_com_an=lca(storenode,node);
ll notracks=dist[storenode]+dist[node]-2*dist[low_com_an];
ll lengthoftracks=course(storenode,node);
if(visitedeachlength[storenode][lengthoftracks]){
foreachlength[storenode][lengthoftracks]=min(foreachlength[storenode][lengthoftracks],notracks);
}
else{
visitedeachlength[storenode][lengthoftracks]=true;
foreachlength[storenode][lengthoftracks]=notracks;
have[storenode].push_back(lengthoftracks);
}
storenode=cenfa[storenode];
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
ll n,k;
cin>>n>>k;
for(int i=1;i<=n-1;i++){
ll l,r,len;
cin>>l>>r>>len;
l++;
r++;
adj[l].push_back(r);
adj[r].push_back(l);
courselen[{l,r}]=len;
courselen[{r,l}]=len;
}
dfslca(1);
precompute(n);
centroid_decomposition(1,-1);
for(int i=1;i<=n;i++){
upd(i);
}
ll ans=MAX;
for(int i=1;i<=n;i++){
for(auto u: have[i]){
if(visitedeachlength[i][k-u]){
ans=min(ans,foreachlength[i][k-u]+foreachlength[i][u]);
}
}
}
if(ans==MAX){
cout<<"-1\n";
}
else{
cout<<ans<<"\n";
}
// for(int i=1;i<=n;i++){
// cout<<cenfa[i]<<" ";
// for(int j=0;j<=Log;j++){
// cout<<jumplen[i][j]<<" ";
// }
// cout<<"\n";
// }
}