제출 #1365686

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1365686		hamza_albrahim	경주 (Race) (IOI11_race)	C++20	0 / 100	4 ms	9796 KiB

race

#include <bits/stdc++.h>
using namespace std;

const int mxn = 200001;

vector<pair<int, int>> adj[mxn];

map<int, int> m[mxn];
int dis[mxn];
int dep[mxn];
int ans = mxn;
int K;

void check(int v, int di, int de){
    int tar = K - di + (2 * dis[v]);
    if(m[v][tar] != 0){
        ans = min(ans, m[v][tar] + de - (2 * dep[v]));
    }
}

void add(int v, int di, int de){
    if(m[v][di] == 0){
        m[v][di] = de;
    }
    else{
        if(de < m[v][di]){
            m[v][di] = de;
        }
    }
}

void dfs(int v, int p){
    dep[v] = dep[p] + 1;
    int ind = -1;
    for(auto [i, j] : adj[v]){
        if(i != p){
            dis[i] = dis[v] + j;
            dfs(i, v);
            if(ind != -1 || m[i].size() > m[ind].size()){
                ind = i;
            }
        }
    }
    if(ind != -1){
        swap(m[ind], m[v]);
    }
    for(auto [i, j] : adj[v]){
        if(i != p && i != ind){
            for(auto [a, b] : m[i]){
                check(v, a, b);
            }
        }
    }
    for(auto [i, j] : adj[v]){
        if(i != p && i != ind){
            for(auto [a, b] : m[i]){
                add(v, a, b);
            }
        }
    }
    add(v, dis[v], dep[v]); 
}



int best_path(int n, int k, int h[][2], int l[])
{
    K = k;
    for(int i = 1; i < n; i++){
        adj[h[i][0]].push_back({h[i][1], l[i]});
        adj[h[i][1]].push_back({h[i][0], l[i]});
    }
    dfs(1, 0);
    return ans;
}

• 서브태스크 1: 0 / 9
• 서브태스크 2: 0 / 12
• 서브태스크 3: 0 / 22
• 서브태스크 4: 0 / 57