Submission #873084

#	Time	Username	Problem	Language	Result	Execution time	Memory
873084		andre_stan	Race (IOI11_race)	C++17	Compilation error	0 ms	0 KiB

race

#include <iostream>
#include <vector>

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;
}

Compilation message (stderr)

/usr/bin/ld: /tmp/cccP97vc.o: in function `main':
race.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccEMAg4a.o:grader.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status