Submission #873097

#	Time	Username	Problem	Language	Result	Execution time	Memory
873097		andre_stan	Race (IOI11_race)	C++14	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 k;
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 > k)
        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]});
    }
    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;
}

Compilation message (stderr)

race.cpp: In function 'void computeDist(int, int, int, long long int, int)':
race.cpp:45:36: error: 'kk' was not declared in this scope; did you mean 'k'?
   45 |         ans = min(ans, minimumDist[kk - sum] + depth);
      |                                    ^~
      |                                    k