Submission #401483

#	Time	Username	Problem	Language	Result	Execution time	Memory
401483		fvogel499	Race (IOI11_race)	C++17	21 / 100	273 ms	31404 KiB

race

#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>

using namespace std;

#define siz 200000/100
#define pii pair<int, int>
#define ll long long
#define int ll

int n;
vector<vector<int>> graph;
vector<vector<pii>> wGraph;
bool isCentroid [siz];
int centroidParent [siz];
int subtreeSize [siz];
int parent [siz];
vector<vector<int>> centroidGraph;
int nodeAssignedVal [siz];

int getSubtreeSizes(int curNode) {
    int locNodes = 1;
    subtreeSize[curNode] = 1;
    for (int newNode : graph[curNode]) {
        if (newNode != parent[curNode] and !isCentroid[newNode]) {
            parent[newNode] = curNode;
            locNodes += getSubtreeSizes(newNode);
            subtreeSize[curNode] += subtreeSize[newNode];
        }
    }
    return locNodes;
}

int getCentroidSub(int curNode, int& totalNodes) {
    bool centroidOk = true;
    int counter = totalNodes-1;
    for (int newNode : graph[curNode]) {
        if (isCentroid[newNode] or parent[curNode] == newNode) continue;
        counter -= subtreeSize[newNode];
        if (subtreeSize[newNode] > (totalNodes)/2) {
            centroidOk = false;
            break;
        }
    }
    if ((parent[curNode] == -1 or counter <= (totalNodes)/2) and centroidOk) return curNode;
    for (int newNode : graph[curNode]) {
        if (newNode != parent[curNode] and !isCentroid[newNode]) {
            int res = getCentroidSub(newNode, totalNodes);
            if (res != -1) return res;
        }
    }
    return -1;
}

int getCentroid(int root) {
    parent[root] = -1;
    int totalNodes = getSubtreeSizes(root);
    int res = getCentroidSub(root, totalNodes);
    return res;
}

int generateCentroidSubtree(int curNode) {
    int centroidNode = getCentroid(curNode);
    isCentroid[centroidNode] = true;
    for (int newNode : graph[centroidNode]) {
        if (!isCentroid[newNode]) {
            centroidParent[generateCentroidSubtree(newNode)] = centroidNode;
        }
    }
    return centroidNode;
}

int centroidDecomp() {
    for (int i = 0; i < n; i++) {
        isCentroid[i] = false;
        centroidParent[i] = -1;
    }
    generateCentroidSubtree(0);
    centroidGraph = vector<vector<int>>(n);
    int root;
    for (int i = 0; i < n; i++) {
        if (centroidParent[i] != -1) centroidGraph[centroidParent[i]].push_back(i);
        else root = i;
    }
    return root;
} 

void dfs(unordered_map<int, unordered_map<int, int>>& perChild, int curNode, int parentNode, int subtreeNode, int forbiddenNode, int curDist, int edgesOnPath) {
    if (curNode == forbiddenNode) return;
    if (subtreeNode == -1 and parentNode != -1) subtreeNode = curNode;
    if (subtreeNode != -1) {
        if (perChild[subtreeNode].find(curDist) == perChild[subtreeNode].end()) perChild[subtreeNode][curDist] = n;
        perChild[subtreeNode][curDist] = min(perChild[subtreeNode][curDist], edgesOnPath);
        perChild[subtreeNode][0] = 0;
    }
    for (pii newEdge : wGraph[curNode]) {
        if (newEdge.first == parentNode) continue;
        dfs(perChild, newEdge.first, curNode, subtreeNode, forbiddenNode, curDist+newEdge.second, edgesOnPath+1);
    }
}

int best_path(int32_t ln, int32_t kval, int32_t edges [siz-1][2], int32_t edgeLen [siz-1]) {
    n = ln;

    graph = vector<vector<int>>(n);
    wGraph = vector<vector<pii>>(n);    
    for (int i = 0; i < n-1; i++) {
        graph[edges[i][0]].push_back(edges[i][1]);
        graph[edges[i][1]].push_back(edges[i][0]);
        wGraph[edges[i][0]].push_back(pii(edges[i][1], edgeLen[i]));
        wGraph[edges[i][1]].push_back(pii(edges[i][0], edgeLen[i]));
    }

    centroidDecomp();

    int minEdgesInPath = n;

    for (int i = 0; i < n; i++) {
        unordered_map<int, unordered_map<int, int>> perChild;
        dfs(perChild, i, -1, -1, centroidParent[i], 0, 0);
        unordered_map<int, multiset<int>> s;
        for (pair<int, unordered_map<int, int>> j : perChild) {
            for (pii k : j.second) s[k.first].insert(k.second);
        }
        for (pair<int, unordered_map<int, int>> j : perChild) {
            for (pii k : j.second) s[k.first].erase(s[k.first].find(k.second));
            for (pii k : j.second) {
                if (s.find(kval-k.first) != s.end() and !s[kval-k.first].empty()) {
                    minEdgesInPath = min(minEdgesInPath, (*(s[kval-k.first].begin()))+k.second);
                }
            }
            for (pii k : j.second) s[k.first].insert(k.second);
        }
    }

    if (minEdgesInPath == n) minEdgesInPath = -1;

    return minEdgesInPath;
}

// int H[siz-1][2];
// int L[siz-1];

// int32_t 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 >> L[i];
//     cout << best_path(N, K, H, L);
// }

Compilation message (stderr)

race.cpp: In function 'long long int centroidDecomp()':
race.cpp:89:12: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
   89 |     return root;
      |            ^~~~

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