제출 #1210873

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1210873		Born_To_Laugh	Race (IOI11_race)	C++17	0 / 100	4 ms	9032 KiB

race

// Born_To_Laugh - Hughie Do
#include <bits/stdc++.h>
#define alle(Lotus) Lotus.begin(), Lotus.end()
using namespace std;
typedef long long ll;
[[maybe_unused]] const ll MOD = 998244353, INF = 1e9 + 7;

const int maxn = 2e5 + 5;
int n, k;
int ans = INF;
vector<int> sz(maxn, 1), bigchild(maxn, -1), dep(maxn, 0), dist(maxn, 0), mp(maxn, -1);
vector<int> adj[maxn];
map<pair<int,int>, int> wei;
vector<int> st;
void pre_dfs(int a, int par){
    for(auto &elm: adj[a]){
        if(elm == par)continue;
        dep[elm] = dep[a] + 1;
        dist[elm] = dist[a] + wei[{a, elm}];
        pre_dfs(elm, a);

        sz[a] += sz[elm];
        if(bigchild[a] == -1 || sz[bigchild[a]] < sz[elm])bigchild[a] = elm;
    }
}

//dist[1] + dist[2] - 2*dist[lca] = k
//dep[1] + dep[2] - 2*dep[lca];
void calc(int a, int par, int distlca, int deplca){
    int dist1 = k + 2 * distlca - dist[a];
    if(mp[dist1] != -1){
        ans = min(ans, mp[dist1] + dep[a] - 2*deplca);
    }
    for(auto &elm: adj[a]){
        if(elm == par)continue;
        calc(elm, a, distlca, deplca);
    }
}
void add(int a, int par, bool godown){
    if(mp[dist[a]] == -1){
        mp[dist[a]] = dep[a];
        st.push_back(dist[a]);
    }
    else mp[dist[a]] = min(mp[dist[a]], dep[a]);

    if(!godown)return;
    for(auto &elm: adj[a]){
        if(elm == par)continue;
        add(elm, a, 1);
    }
}

void clsdata(){
    for(auto &elm: st){
        mp[elm] = -1;
    }
    st.clear();
}
void dfs(int a, int par){
    for(auto &elm: adj[a]){
        if(elm == par || elm == bigchild[a])continue;
        dfs(elm, a);
        clsdata();
    }

    if(bigchild[a] != -1) dfs(bigchild[a], a);

    for(auto &elm: adj[a]){
        if(elm == par || elm == bigchild[a])continue;
        calc(elm, a, dist[a], dep[a]);
        add(elm, a, 1);
    }

    int dist1 = k + dist[a];
    if(mp[dist1] != -1){
        ans = min(ans, mp[dist1] - dep[a]);
    }
    add(a, par, 0);
}
int best_path(int N, int K, int H[][2], int L[]){
    n = N;
    k = K;
    for(int i=0; i<n-1; ++i){
        int x = H[i][0], y = H[i][1];
        adj[x].push_back(y);
        adj[y].push_back(x);
        int w = L[i];
        wei[{x, y}] = w;
        wei[{y, x}] = w;
    }
    pre_dfs(0, -1);
    dfs(0, -1);
    return (ans == INF?-1:ans);
}

• Subtask 1: 0 / 9
• Subtask 2: 0 / 12
• Subtask 3: 0 / 22
• Subtask 4: 0 / 57