Submission #859751

#	Time	Username	Problem	Language	Result	Execution time	Memory
859751		lbadea1000	Race (IOI11_race)	C++17	100 / 100	269 ms	42180 KiB

race

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

const int NMAX = 2e5;
const int INF = 1e9;
const int KMAX = 1e6;

int totalSize;
vector<pair<int, int>> edges[NMAX];
int sz[NMAX];
int centroidParent[NMAX];
bool isIn[NMAX];

int minimumDist[KMAX];
vector<long long> used;
int kk;
int ans;

int dfsCalcSize(int node, int parent) {
    sz[node] = 1;
    for(auto child : edges[node]) {
        if(child.first != parent && isIn[child.first]) {
            sz[node] += dfsCalcSize(child.first, node);
        }
    }
    return sz[node];
}

int dfsDetCentroid(int node, int parent) {
    for(auto child : edges[node]) {
        if(child.first != parent && sz[child.first] > totalSize / 2 && isIn[child.first]) {
            return dfsDetCentroid(child.first, node);
        }
    }
    return node;
}

void computeDist(int node, int parent, int depth, long long sum, int flag) {
    if(sum > kk)
        return;
    used.push_back(sum);
    if(flag == true) {
        ans = min(ans, minimumDist[kk - sum] + depth);
    } else {
        minimumDist[sum] = min(minimumDist[sum], depth);
    }
    for(auto child : edges[node]) {
        if(isIn[child.first] && child.first != parent) {
            computeDist(child.first, node, depth + 1, sum + child.second, flag);
        }
    }
}

void decompose(int root, int parent) {
    totalSize = dfsCalcSize(root, root);
    int centroid = dfsDetCentroid(root, root);
    isIn[centroid] = false;

    minimumDist[0] = 0;
    for(auto child : edges[centroid]) {
        if(isIn[child.first]) {
            computeDist(child.first, centroid, 1, child.second, true);
            computeDist(child.first, centroid, 1, child.second, false);
        }
    }
    for(auto x : used) {
        minimumDist[x] = INF;
    }
    used.clear();

    centroidParent[centroid] = parent;
    for(auto child : edges[centroid]) {
        if(isIn[child.first])
            decompose(child.first, centroid);
    }
}

int best_path(int n, int k, int h[][2], int len[]) {
    for(int i = 0; i < n - 1; i++) {
        edges[h[i][0]].push_back({h[i][1], len[i]});
        edges[h[i][1]].push_back({h[i][0], len[i]});
    }

    kk = k;
    for(int i = 0; i <= k; i++)
        minimumDist[i] = INF;
    for(int i = 0; i < n; i++)
        isIn[i] = true;
    ans = INF;
    decompose(0, -1);
    if(ans == INF)
        ans = -1;
    return ans;
}

/*int h[NMAX][2];
int len[NMAX];

int main() {
    int n, k;
    cin >> n >> k;
    for(int i = 0; i < n - 1; i++)
        cin >> h[i][0] >> h[i][1];
    for(int i = 0; i < n - 1; i++)
        cin >> len[i];
    cout << best_path(n, k, h, len);
    return 0;
}*/

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