제출 #851119

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
851119		andrei_marciuc	Race (IOI11_race)	C++14	100 / 100	1688 ms	51016 KiB

race

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
 
const int inf = 1e9+9999;
vector<vector<pair<int, int>>> graph;
map<int, int> sums, tempsums;
vector<int> sub;
int k, centroid;
int ans = inf;
int rem;
 
vector<bool> vis, mark;
int dfs1(int node, int par) {
    int val = 1;
    mark[node] = true;
    for(auto it : graph[node]) {
        if(it.first == par)
            continue;
        if(vis[it.first])
            continue;
        val += dfs1(it.first, node);
    }
    sub[node] = val;
    return val;
}

void dfs2(int node, int par, int cur, int len) {
    if(cur > k)
        return;
    if(k == cur)
        ans = min(ans, len);
    else if(sums[k - cur])
        ans = min(ans, sums[k - cur] + len);

    for(auto it : graph[node]) {
        if(vis[it.first])
            continue;
        if(it.first == par)
            continue;
        if(node == centroid) {
            for(auto it: tempsums) {
                if(!sums[it.first])
                    sums[it.first] = it.second;
                sums[it.first] = min(it.second, sums[it.first]);
            }
            tempsums.clear();
        }
        dfs2(it.first, node, cur + it.second, len + 1);
    }

    if(!tempsums[cur])
        tempsums[cur] = len;
    
    tempsums[cur] = min(len, tempsums[cur]);
    return;
}

int findcentroid(int node, int par, int sz) {
    for(auto it : graph[node]){
        if(vis[it.first])
            continue;
        if(it.first == par)
            continue;
        if(sub[it.first] >= sz / 2)
            return findcentroid(it.first, node, sz);
    }
    return node;
}

int best_path(int32_t N, int32_t K, int32_t H[][2], int32_t L[]) {
    rem = N;
    k = K;

    graph.assign(N + 5, vector<pair<int, int>>());
    vis.assign(N + 5, false);
    
    for(int i = 0; i < N - 1; i++) {
        graph[H[i][1]].push_back({H[i][0], L[i]});
        graph[H[i][0]].push_back({H[i][1], L[i]});
    }

    while(rem) {
        mark.assign(N + 5, false);
        sub.assign(N + 5, 0);
        for(int i = 0; i < N; i++) {
            sums.clear();
            tempsums.clear();
            if(mark[i] || vis[i])
                continue;
            int sz = dfs1(i, -1);
            centroid = findcentroid(i, -1, sz);
            dfs2(centroid, -1, 0, 0);
            vis[centroid] = true;
            rem--;
        }
    }

    if(ans == inf)
        return -1;
    return ans;
}

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