Submission #639761

#	Time	Username	Problem	Language	Result	Execution time	Memory
639761		gozonite	Race (IOI11_race)	C++14	21 / 100	3079 ms	39492 KiB

race

#include <iostream>
#include <vector>
#include <string>
#include <fstream>
#include <algorithm>
#include <climits>
#include <cstdlib>
#include <cstdio>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <bitset>
#include <deque>
#include <queue>
#include <tuple>
#include <cmath>
#include <cctype>
#include <stack>
#include <cassert>
#include <iomanip>
#include <complex>
using namespace std;
using ll = long long;

vector<pair<int, int>> adj[200000];
int subs[200000];
bool rm[200000];
int ans;
unordered_map<int, int> mh; // minimum number of highways to construct path of length idx
vector<pair<int, int>> cand;

int rsubs(int v, int p) {
    subs[v] = 1;
    for (auto u : adj[v])
        if (u.first != p && !rm[u.first]) subs[v] += rsubs(u.first, v);
    return subs[v];
}
int find_centroid(int v, int p, int sz) {
    for (auto u : adj[v])
        if (u.first != p && !rm[u.first] && subs[u.first] > sz/2) return find_centroid(u.first, v, sz);
    return v;
}
void dfs(int v, int p, int len, int d) {
    cand.push_back({len, d});
    for (auto u : adj[v])
        if (u.first != p && !rm[u.first]) dfs(u.first, v, len+u.second, d+1);
}

void build(int v, int K) {
    rsubs(v, -1);
    v = find_centroid(v, -1, subs[v]);

    // consider all paths passing through node v
    mh[0] = 0;
    for (auto u: adj[v]) {
        if (rm[u.first]) continue;
        dfs(u.first, v, u.second, 1);
        for (auto pp : cand) {
            int len = pp.first, d = pp.second;
            if (mh.find(K-len) != mh.end()) ans = min(ans, mh[K-len]+d);
        }
        for (auto pp : cand) {
            if (mh.find(pp.first) == mh.end()) mh[pp.first] = pp.second;
            else mh[pp.first] = min(mh[pp.first], pp.second);
        }
        cand.clear();
    }
    mh.clear();

    rm[v] = true;
    for (auto u : adj[v]) {
        if (rm[u.first]) continue;
        build(u.first, K);
    }
}

int best_path(int N, int K, int H[][2], int L[]) {
    for (int i = 0; i < N; i++) {
        adj[i].clear();
        rm[i] = false;
    }
    for (int i = 0; i < N-1; i++) {
        adj[H[i][0]].push_back({H[i][1], L[i]});
        adj[H[i][1]].push_back({H[i][0], L[i]});
    }
    ans = 1e9;
    build(1, K);
    return ans==1e9 ? -1 : ans;
}

/*int main() {
    //int N = 4, K = 3;
    //int H[][2] = {{0, 1}, {1, 2}, {1, 3}};
    //int L[] = {1, 2, 4};
    //cout << best_path(N, K, H, L) << endl;

    //int N = 3, K = 3;
    //int H[][2] = {{0, 1}, {1, 2}};
    //int L[] = {1, 1};
    //cout << best_path(N, K, H, L) << endl;

    int N = 11, K = 12;
    int H[][2] = {{0, 1}, {0, 2}, {2, 3}, {3, 4}, {4, 5}, {0, 6}, {6, 7}, {6, 8}, {8, 9}, {8, 10}};
    int L[] = {3, 4, 5, 4, 6, 3, 2, 5, 6, 7};
    cout << best_path(N, K, H, L) << endl;
}*/

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