Submission #526931

#	Time	Username	Problem	Language	Result	Execution time	Memory
526931		LFFB	Race (IOI11_race)	C++17	0 / 100	31 ms	48116 KiB

race

#include <iostream>
#include <vector>
#include <string>

#define debug(args...) //printf(args)

typedef std::pair<int, int> intPair;

#define forAllChild(node, code) for (intPair childPair : neighbors[node]) {\
    int child = childPair.first;\
    int childWeight = childPair.second;\
    if (child == parent.get(node)) continue;\
    if (removed.get(child)) continue;\
    code;\
}

const int MAX_N = 1000000 + 1;
const int INF = 1000000000;

template<typename T>
class SpecialVector {

    private:
        int time;
        T values[MAX_N];
        T standard;
        int lastChanged[MAX_N];

    public:
        SpecialVector(T val) {
            time = 1;
            standard = val;
        }

        T get(int i) {
            if (i >= MAX_N) return standard;
            if (lastChanged[i] == time) return values[i];
            return standard;
        }

        void set(int i, T v) {
            if (i >= MAX_N) return;
            values[i] = v;
            lastChanged[i] = time;
        }

        bool defined(int i) {
            if (i >= MAX_N) return false;
            return lastChanged[i] == time;
        }

        void clear() {
            time++;
        }

};

int n;
int k;

std::vector<intPair> neighbors[MAX_N];

SpecialVector<int> parent(-1);
SpecialVector<int> parentWeight(-1);

SpecialVector<bool> removed(false);

SpecialVector<int> lengths(-1);

SpecialVector<int> lengthMap(-1);

namespace CentroidDecomposition {

    int findBetterCentroid(int node, int root) {
        forAllChild(node, {
            if (lengths.get(child) > lengths.get(root)/2) return child;
        });
        return -1;
    }

    int findCentroid(int root) {
        int node = root;
        while (findBetterCentroid(node, root) != -1) {
            debug("found better centroid for %d (root: %d)\n", node, root);
            node = findBetterCentroid(node, root);
        }
        debug("root %d, found centroid %d\n", root, node);
        return node;
    }

}

void setMin(int &a, int b) {
    a = std::min(a, b);
}

void findParents(int node) {
    lengths.set(node, 1);
    forAllChild(node, {
        parent.set(child, node);
        parentWeight.set(child, childWeight);
        findParents(child);
        lengths.set(node, lengths.get(node) + lengths.get(child));
    });
}

int getMin(int node, int depth, int distance) {
    int minimum;
    if (lengthMap.defined(k - distance)) {
        minimum = depth + lengthMap.get(k - distance);
    } else {
        minimum = INF;
    }

    forAllChild(node, {
        int childMinumum = getMin(child, depth + 1, distance + childWeight);
        setMin(minimum, childMinumum);
    });

    return minimum;
}

void addToMapping(int node, int depth, int distance) {

    if (lengthMap.get(distance) > depth || !lengthMap.defined(distance)) {
        lengthMap.set(distance, depth);
    }

    forAllChild(node, {
        addToMapping(child, depth + 1, distance + childWeight);
    });

}

int getMinimumLength(int root) {

    parent.clear();
    lengths.clear();
    findParents(root);

    int centroid = CentroidDecomposition::findCentroid(root);
    removed.set(centroid, true);

    lengthMap.clear();
    lengths.clear();
    parent.clear();

    int minimum = INF;

    for (intPair neighborPair : neighbors[centroid]) {
        int neighbor = neighborPair.first;
        int neighborWeight = neighborPair.second;
        if (removed.get(neighbor)) continue;

        findParents(neighbor);

        int neighborMinimum = getMin(neighbor, 1, neighborWeight);
        setMin(minimum, neighborMinimum);

        addToMapping(neighbor, 1, neighborWeight);
    }

    for (intPair neighborPair : neighbors[centroid]) {
        int neighbor = neighborPair.first;
        int neighborWeight = neighborPair.second;
        if (removed.get(neighbor)) continue;

        int neighborMinimum = getMinimumLength(neighbor);
        setMin(minimum, neighborMinimum);
    }

    debug("root %d, centroid %d, returning %d\n", root, centroid, minimum);
    return minimum;
}

void printRepeated(std::string s, int x) {
    for (int i = 0; i < x; i++) printf("%s", s.c_str());
}
void printTree(int node, int depth=0) {
    printRepeated("- ", depth);
    printf("%d\n", node);
    forAllChild(node, {
        printTree(child, depth + 1);
    });
}

int best_path(int N, int K, int H[][2], int L[]) {
    n = N;
    k = K;
    for (int i = 0; i < n - 1; i++) {
        int a = H[i][0];
        int b = H[i][1];
        int w = L[i];
        neighbors[a].push_back(std::make_pair(b, w));
        neighbors[b].push_back(std::make_pair(a, w));
    }
    //findParents(0);
    //printTree(0);
    int answer = getMinimumLength(0);
    if (answer == INF) answer = -1;
    return answer;
}

Compilation message (stderr)

race.cpp: In function 'int CentroidDecomposition::findBetterCentroid(int, int)':
race.cpp:12:9: warning: unused variable 'childWeight' [-Wunused-variable]
   12 |     int childWeight = childPair.second;\
      |         ^~~~~~~~~~~
race.cpp:76:9: note: in expansion of macro 'forAllChild'
   76 |         forAllChild(node, {
      |         ^~~~~~~~~~~
race.cpp: In function 'int getMinimumLength(int)':
race.cpp:166:13: warning: unused variable 'neighborWeight' [-Wunused-variable]
  166 |         int neighborWeight = neighborPair.second;
      |             ^~~~~~~~~~~~~~
race.cpp: In function 'void printTree(int, int)':
race.cpp:12:9: warning: unused variable 'childWeight' [-Wunused-variable]
   12 |     int childWeight = childPair.second;\
      |         ^~~~~~~~~~~
race.cpp:183:5: note: in expansion of macro 'forAllChild'
  183 |     forAllChild(node, {
      |     ^~~~~~~~~~~

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