제출 #766570

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
766570		Mahmoud_Atia	Race (IOI11_race)	C++14	100 / 100	347 ms	52064 KiB

race

#include <iostream>
#include <vector>
#include "race.h"
using namespace std;

const int N = 1e6 + 5, M = 1e6 + 5;

int t, n, m, k, a[N], sz[N], tmp[N], mx, l[N], r[N];
vector<pair<int, int>> v[N];
bool vis[N];
int ans = 1e9;

int get_subtree_sizes(int node, int p = -1) {
    sz[node] = 1;
    for (auto x:v[node]) if (x.first != p && !vis[x.first]) sz[node] += get_subtree_sizes(x.first, node);
    return sz[node];
}

int get_centroid(int node, int size, int p = -1) {
    for (auto x:v[node]) {
        if (x.first == p || vis[x.first]) continue;
        if (sz[x.first] >= size) return get_centroid(x.first, size, node);
    }
    return node;
}



void get_cnt(int node, int p, int yes, int sum, int level) {
    if (sum > k) return;
    if (sum == k) ans = min(ans, level);
    if (yes == 1) tmp[sum] = min(tmp[sum], level);
    else if (yes) tmp[sum] = 1e9;
    else ans = min(ans, level + tmp[k - sum]);
    for (auto x:v[node]) if (x.first != p && !vis[x.first]) get_cnt(x.first, node, yes, sum + x.second, level + 1);
}

void centroid_decomp(int node = 0) {
    get_subtree_sizes(node);
    int c = get_centroid(node, sz[node] / 2);
    vis[c] = 1;
    mx = 0;
    for (auto x:v[c]) if (!vis[x.first]) get_cnt(x.first, c, 0, x.second, 1), get_cnt(x.first, c, 1, x.second, 1);
    for (auto x:v[c]) if (!vis[x.first]) get_cnt(x.first, c, 2, x.second, 1);
    for (auto x:v[c]) if (!vis[x.first]) centroid_decomp(x.first);
}


int best_path(int N, int K, int H[][2], int L[]) {
    fill(tmp, tmp + 1000000 + 5, 1e9);
    n = N, k = K;
    for (int i = 0; i < n-1; i++) {
        v[H[i][1]].push_back({H[i][0], L[i]});
        v[H[i][0]].push_back({H[i][1], L[i]});
    }
    centroid_decomp();
    return (ans == 1e9 ? -1 : ans);
}

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