Submission #671332

#	Time	Username	Problem	Language	Result	Execution time	Memory
671332		shrimb	Race (IOI11_race)	C++17	100 / 100	354 ms	85972 KiB

race

#include "bits/stdc++.h"
#include "race.h"
 
using namespace std;
 
const int maxn = 200001;
 
vector<pair<int,int>> adj[maxn];
 
int k;
 
map<long long,int> *maps[maxn];
 
void Check (int cur, int x, int y, int& ret, int dep2, int dep) {
    if (maps[cur] -> count(k + 2 * dep - x)) {
        ret = min(ret, y + (*maps[cur])[k + 2 * dep - x] - 2 * dep2);
    }
}
 
void Insert (int cur, int x, int y) {
    if (maps[cur] -> count(x)) (*maps[cur])[x] = min((*maps[cur])[x], y);
    else (*maps[cur])[x] = y;
}
 
int dfs (int cur, int par, int dep, int dep2) { // dep = sum of weights // dep2 = number of edges from root
    if ((adj[cur].empty()) || (adj[cur].size() == 1 and cur != 0)) {
        maps[cur] = new map<long long, int>();
        maps[cur] -> insert({dep, dep2});
        return INT_MAX;
    }
 
    int mx = -1;
    int ret = INT_MAX;
 
    for (auto [i, j] : adj[cur]) {
        if (i != par) {
            ret = min(ret, dfs(i, cur, dep + j, dep2 + 1));
            if (mx == -1 || maps[i] -> size() > maps[mx] -> size()) mx = i;
        }
    }
 
    maps[cur] = maps[mx];
 
 
    for (auto [i, j] : adj[cur]) {
        if (i != par and i != mx) {
            for (auto [x, y] : *maps[i]) {
                Check(cur, x, y, ret, dep2, dep);
            }
            for (auto [x, y] : *maps[i]) {
                Insert(cur, x, y);
            }
        }
    }
    Check(cur, dep, dep2, ret, dep2, dep);
    Insert(cur, dep, dep2);
    return ret;
}
 
int best_path(int N, int K, int H[][2], int L[]) {
    k = K;
 
    for (int i = 0 ; i < N - 1 ; i++) {
        auto [u, v] = H[i];
        int w = L[i];
        adj[u].emplace_back(v, w);
        adj[v].emplace_back(u, w);
    }
 
    int ans;
 
    return (ans = dfs(0, 0, 0, 0)) == INT_MAX ? -1 : ans;
}

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