Submission #894610

#	Time	Username	Problem	Language	Result	Execution time	Memory
894610		IWKR	Race (IOI11_race)	C++17	100 / 100	332 ms	42812 KiB

race

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

vector<pair<int, int>> adjlist[200000];
int dist[1000001];
int subsz[200000], level[200000];
vector<pair<int, int>> v;
vector<int> v2;
int k, ans;

void dfs(int x, int p) {
    subsz[x] = 1;
    for (auto i: adjlist[x]) {
        if (i.first == p || level[i.first] != 0) {
            continue;
        }
        dfs(i.first, x);
        subsz[x] += subsz[i.first];
    }
}

int centroid(int x, int p, int treesz) {
    for (auto i: adjlist[x]) {
        if (i.first == p || level[i.first] != 0) {
            continue;
        }
        if (treesz < subsz[i.first] * 2) {
            return centroid(i.first, x, treesz);
        }
    }
    return x;
}

void dfs2(int x, int p, int depth, int cost) {
    if (cost > k) {
        return;
    }
    v.push_back({cost, depth});
    for (auto i: adjlist[x]) {
        if (i.first == p || level[i.first] != 0) {
            continue;
        }
        dfs2(i.first, x, depth + 1, cost + i.second);
    }
}

void decomp(int x) {
    dfs(x, -1);
    int cent = centroid(x, -1, subsz[x]);
    level[cent] = 1;
    dist[0] = 0;
    for (auto i: adjlist[cent]) {
		if (level[i.first] != 0) {
			continue;
		}
        dfs2(i.first, -1, 1, i.second);
        for (auto j: v) {
            if (dist[k - j.first] == INT_MAX) {
                continue;
            }
            ans = min(ans, dist[k - j.first] + j.second);
        }
        for (auto j: v) {
            v2.push_back(j.first);
            dist[j.first] = min(dist[j.first], j.second);
        }
        v.clear();
    }
    for (auto i: v2) {
        dist[i] = INT_MAX;
    }
    v2.clear();
    for (auto i: adjlist[cent]) {
        if (level[i.first] == 0) {
            decomp(i.first);
        }
    }
}

int best_path(int N, int K, int H[][2], int L[]) {
    for (int i = 0; i < N - 1; i++) {
        adjlist[H[i][0]].push_back({H[i][1], L[i]});
        adjlist[H[i][1]].push_back({H[i][0], L[i]});
    }
    k = K;
    for (int i = 1; i <= k; i++) {
        dist[i] = INT_MAX;
    }
    ans = N;
    decomp(0);
    if (ans == N) {
        return -1;
    } else {
        return ans;
    }
}

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