Submission #552807

#	Time	Username	Problem	Language	Result	Execution time	Memory
552807		Olympia	Race (IOI11_race)	C++17	100 / 100	1881 ms	74004 KiB

race

#include <iostream>
#include <algorithm>
#include <map>
#include <vector>
#include <cassert>
#include <climits>
#include "race.h"
using namespace std;
class Tree {
public:
    vector<vector<int>> adj;
    map<pair<int,int>,int64_t> weight;
    vector<bool> hasVisited;
    vector<int> sub;
    vector<int> parent;
    vector<int> gw;
    int sz = 0;
    void prelim (int curNode, int prevNode) {
        parent[curNode] = prevNode;
        gw[curNode] = weight[make_pair(curNode, prevNode)];
        for (int i: adj[curNode]) {
            if (i != prevNode) {
                prelim(i, curNode);
            }
        }
    }
    int get_weight (int curNode, int prevNode) {
        if (parent[curNode] == prevNode) {
            return gw[curNode];
        } else if (parent[prevNode] == curNode){
            return gw[prevNode];
        }
      assert(false);
    }
    int dfs_for_sz (int curNode, int prevNode) {
        sub[curNode] = 1;
        for (int i: adj[curNode]) {
            if (i != prevNode && !hasVisited[i]) {
                sub[curNode] += dfs_for_sz (i, curNode);
            }
        }
        return (sz = sub[curNode]);
    }
    int find_centroid (int curNode, int prevNode) {
        for (int i: adj[curNode]) {
            if (sub[i] * 2 > sz && !hasVisited[i] && i != prevNode) {
                return find_centroid(i, curNode);
            }
        }
        return curNode;
    }
    map<int64_t,int> tot, exc;
    void dfs (int curNode, int prevNode, int64_t w, int d) {
        if (exc.count(w)) exc[w] = min(exc[w], d);
        else exc[w] = d;
        for (int i: adj[curNode]) {
            if (i != prevNode && !hasVisited[i]) {
                dfs (i, curNode, w + get_weight(i, curNode), d + 1);
            }
        }
    }
    int ans = INT_MAX;
    int64_t k;
    void solve (int curNode) {
        dfs_for_sz(curNode, curNode);
        int centroid = find_centroid(curNode, curNode);
        hasVisited[centroid] = true;
        //Two Cases:
        //(1) It passes through the centroid
        //(2) It doesn't pass through the centroid
        for (int i: adj[centroid]) {
            if (!hasVisited[i]) {
                dfs (i, i, get_weight(i, centroid), 1);
                for (auto& p: exc) {
                    if (tot.count(k - p.first)) {
                        ans = min(ans, tot[k - p.first] + p.second);
                    }
                }
                for (auto& p: exc) {
                    if (tot.count(p.first)) tot[p.first] = min(tot[p.first], p.second);
                    else tot[p.first] = p.second;
                }
                exc.clear();
            }
        }
        if (tot.count(k)) {
            ans = min(ans, tot[k]);
        }
        tot.clear();
        for (int i: adj[centroid]) {
            if (!hasVisited[i]) {
                solve (i);
            }
        }
    }
    void add_weight (int u, int v, int64_t w) {
        weight[make_pair(u, v)] = weight[make_pair(v, u)] = w;
        adj[u].push_back(v), adj[v].push_back(u);
    }
    Tree (int n, int k) {
        adj.resize(n), hasVisited.assign(n, false), sub.assign(n, false), gw.resize(n), parent.resize(n);
        this->k = k;
    }
};
int best_path(int n, int k, int H[][2], int L[]){
    Tree myTree(n, k);
    for (int i = 0; i < n - 1; i++) {
        myTree.add_weight(H[i][0], H[i][1], L[i]);
    }
    myTree.prelim(0, 0);
    myTree.solve(0);
    if (myTree.ans == INT_MAX) return -1;
    return myTree.ans;
}
/*
int main() {
    
}
*/

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