제출 #1294676

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1294676		quanta07	경주 (Race) (IOI11_race)	C++20	100 / 100	537 ms	53280 KiB

race

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

using ll = long long;


const int K = 1e6+10;


vector<vector<pair<int,int>>> g;
vector<int> min_edges(K,1e7);
vector<int> vis;
vector<int> sz;
vector<int> dist;
vector<int> wt;
int ans = 1e7;

void dfs(int u, int p = -1){
    sz[u] = 1;
    for(auto [v,w]: g[u]){
        if(v == p || vis[v]) continue;
        dfs(v,u);
        sz[u] += sz[v];
    }
    return;
}

int get_centroid(int tot, int u, int p = -1){
    for(auto [v,w]: g[u]){
        if(v == p || vis[v]) continue;
        if(2*sz[v] > tot) return get_centroid(tot,v,u);
    }
    return u;
}


void get_dis(vector<int> &nodes, vector<int> &dist, vector<int> &wt, int k, int u, int p = -1){
    nodes.push_back(u);
    for(auto [v,w]: g[u]){
        if(v == p || vis[v]) continue;
        dist[v] = 1 + dist[u];
        wt[v] = w+wt[u];
        get_dis(nodes,dist,wt,k,v,u);
    }
}


void calculate_min(int n, int k, int u, int p = -1){
    dfs(u,p);
    int r = get_centroid(sz[u], u, p);
    // cout << "centroid: " << r << "\n";
    vis[r] = 1;
    min_edges[0] = 0;
    set<int> global_nodes;
    for(auto[v,w]: g[r]){
        if(vis[v] || v == p) continue;
        vector<int> nodes;
        dist[v] = 1;
        wt[v] = w;
        get_dis(nodes,dist,wt,k,v,r);
        for(int v: nodes){
            if(wt[v] <= k) global_nodes.insert(wt[v]), ans = min(ans, min_edges[k-wt[v]]+dist[v]);
        }
        for(int v: nodes){
            if(wt[v] <= k) min_edges[wt[v]] = min(min_edges[wt[v]],dist[v]);
        }
    }

    for(auto it: global_nodes) min_edges[it] = 1e7;
    for(auto [v,w]: g[r]){
        if(vis[v] || v == p) continue;
        calculate_min(n,k,v,r);
    }

}


int best_path(int n, int k, int h[][2], int l[]){
    g.resize(n+1);
    vis.assign(n+1,0);
    sz.resize(n+1);
    dist.assign(n+1,1e7);
    wt.assign(n+1,1e7);
    for(int i=0; i<n-1; i++){
        g[h[i][0]].push_back({h[i][1],l[i]});
        g[h[i][1]].push_back({h[i][0],l[i]});
    }
    calculate_min(n,k,0);
    if(ans >= 1e7)  return -1;
    return ans;
}


// int32_t main(){
//     int n,k; cin >> n >> k;
//     int h[n-1][2]; 
//     for(int i=0; i<n-1; i++) cin >> h[i][0] >> h[i][1];
//     int l[n-1];
//     for(int i=0; i<n-1; i++) cin >> l[i];
//     int r = best_path(n,k,h,l);
//     cout << r << "\n";
//     // for(int i=0; i<=k; i++) cout << min_edges[i] << " ";
//     // cout << "\n";
//     return 0;
// }

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