제출 #704750

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
704750		thimote75	경주 (Race) (IOI11_race)	C++14	100 / 100	1167 ms	64672 KiB

race

#include "race.h"
#include <bits/stdc++.h>

using namespace std;

#define num long long
#define di pair<int, num>
#define sdi set<di>
#define graph vector<sdi>
#define idata vector<int>

#define INF 1e18

graph roads;

int nbNodes, pathLength;

struct MMap {
    map<num, num> m;

    bool has (num depth) {
        return m.find(depth) != m.end();
    }
    num get (num depth) {
        return (*(m.find(depth))).second;
    }
    void set (num depth, num value) {
        if (has(depth)) {
            value = min(value, get(depth));
            m.erase(depth);
        }

        m.insert({ depth, value });
    }
    void clear () {
        m.clear();
    }
    void show () {
        for (auto u : m)
            printf("%lld:%lld ", u.first, u.second);
        cout << endl;
    }
};

struct CDecompose {
    num answer = 1e18;
    idata subtree;

    MMap min_map;

    void init () {
        subtree.resize(nbNodes);

        build (0, -1);
    }
    void build (int node, int parent) {
        int compSize = w_dfs(node, parent);
        int centroid = c_dfs(node, parent, compSize >> 1);

        min_map.set(0, 0);

        for (di next : roads[centroid]) {
            comp(next.first, centroid, next.second, 1);
            fill(next.first, centroid, next.second, 1);
        }

        min_map.clear();

        while (roads[centroid].size() != 0) {
            di err = *roads[centroid].begin();   

            roads[centroid ].erase(err);
            roads[err.first].erase({ centroid, err.second });

            build (err.first, -1);
        }
    }

    int w_dfs (int node, int parent) {
        subtree[node] = 1;

        for (di next : roads[node]) {
            if (next.first == parent) continue ;
            subtree[node] += w_dfs(next.first, node);
        }

        return subtree[node];
    }
    int c_dfs (int node, int parent, int desired) {
        for (di next : roads[node])
            if (next.first != parent && desired <= subtree[next.first])
                return c_dfs(next.first, node, desired);
        return node;
    }

    void comp (int node, int parent, num length, int depth) {
        if (length > pathLength) return ;
        if (depth  > answer)     return ;

        if (min_map.has(pathLength - length)) {
            answer = min(
                answer,
                min_map.get(pathLength - length) + depth
            );
        }

        for (di next : roads[node]) {
            if (next.first == parent) continue ;
            comp(next.first, node, length + next.second, depth + 1);
        }
    }
    void fill (int node, int parent, num length, int depth) {
        if (length > pathLength) return ;
        if (depth  > answer)     return ;

        min_map.set(length, depth);

        for (di next : roads[node]) {
            if (next.first == parent) continue ;
            fill(next.first, node, length + next.second, depth + 1);
        }
    }
};

int best_path(int N, int K, int H[][2], int L[])
{
    nbNodes    = N;
    pathLength = K;
    roads.resize(nbNodes);

    for (int idRoad = 0; idRoad + 1 < nbNodes; idRoad ++) {
        int a, b; num l;
        a = H[idRoad][0];
        b = H[idRoad][1];
        l = L[idRoad];

        roads[a].insert({ b, l });
        roads[b].insert({ a, l });
    }

    CDecompose dec;
    dec.init();

    return dec.answer == INF ? -1 : dec.answer;
}

/*int main () {
    int N, K;
    cin >> N >> K;
    int H[N][2];
    int L[N];
    for (int i = 0; i + 1 < N; i++)
        cin >> H[i][0] >> H[i][1] >> L[i];
    printf("%d", best_path(N, K, H, L));
}*/

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