제출 #1271466

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1271466		danilofv	Race (IOI11_race)	C++20	100 / 100	298 ms	37260 KiB

race

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

vector<vector<pair<int,int>>> grafo;
vector<int> subtrees;
vector<bool> visited;
int minCam;

vector<int> melhor, last_update;
int current_time = 0;

void calc_subtrees(int src, int parent){
    subtrees[src] = 1;
    for (auto& vz: grafo[src]){
        int v = vz.first;
        if (v == parent || visited[v]) continue; 
        calc_subtrees(v, src);
        subtrees[src] += subtrees[v];
    }
}

int centroid(int src, int parent, int subTreeSize){
    for (auto vz: grafo[src]){
        int v = vz.first;
        if (v == parent || visited[v]) continue; 
        if (subtrees[v] > subTreeSize/2){
            return centroid(v, src, subTreeSize);
        }
    }
    return src;
}

int find_centroid(int beg, int parent){
    calc_subtrees(beg, parent);
    return centroid(beg, -1, subtrees[beg]);
}

inline int get_val(int x){
    return (last_update[x] == current_time ? melhor[x] : INT_MAX);
}
inline void set_val(int x, int val){
    if (last_update[x] != current_time){
        last_update[x] = current_time;
        melhor[x] = val;
    } else {
        melhor[x] = min(melhor[x], val);
    }
}

void dfs1(int src, int parent, int currPathTam, int currPathArestas, int K){
    if (visited[src] || currPathTam > K) return;
    int need = K - currPathTam;
    if (get_val(need) != INT_MAX)
        minCam = min(minCam, currPathArestas + get_val(need));

    for (auto &[vz, w] : grafo[src]){
        if (vz == parent || visited[vz]) continue; 
        dfs1(vz, src, currPathTam + w, currPathArestas + 1, K);
    }
}

void dfs2(int src, int parent, int currPathTam, int currPathArestas, int K){
    if (visited[src] || currPathTam > K) return;
    set_val(currPathTam, currPathArestas);

    for (auto &[vz, w]: grafo[src]){
        if (vz == parent || visited[vz]) continue;
        dfs2(vz, src, currPathTam + w, currPathArestas + 1, K);
    }
}

void solve(int start, int K){
    int cntd = find_centroid(start, -1);
    visited[cntd] = true;

    current_time++;
    set_val(0, 0);

    for (auto &[v, w] : grafo[cntd]){
        if (visited[v]) continue;
        dfs1(v, cntd, w, 1, K);
        dfs2(v, cntd, w, 1, K);
    }

    for (auto &[v, w] : grafo[cntd]){
        if (!visited[v]){
            solve(v, K);
        }
    }
}

int best_path(int N, int K, int H[][2], int L[]){
    minCam = INT_MAX;
    visited.assign(N, false);
    subtrees.assign(N, 0);
    grafo.assign(N, {});
    melhor.assign(K+1, INT_MAX);
    last_update.assign(K+1, -1);
    current_time = 0;

    for (int i = 0; i < N - 1; i++){
        grafo[H[i][0]].push_back({H[i][1], L[i]});
        grafo[H[i][1]].push_back({H[i][0], L[i]});
    }

    solve(0, K);
    return (minCam == INT_MAX ? -1 : minCam);
}

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