Submission #242148

#	Time	Username	Problem	Language	Result	Execution time	Memory
242148		LifeHappen__	Race (IOI11_race)	C++14	100 / 100	501 ms	55268 KiB

race

#include <bits/stdc++.h>
#include "race.h"
using namespace std;

const int N = 1e6 + 5;
int n, cnt, k;
int dd[N], sz[N], d[N], f[N];
vector <pair<int, int>> ad[N], val;
int ans;

void dfs(int u, int par) {
    cnt++;
    sz[u] = 1;
    for(auto v : ad[u]) {
        if(v.first != par && !dd[v.first]) dfs(v.first, u), sz[u] += sz[v.first];
    }
}
int ftr(int u, int par) {
    for(auto &v : ad[u]) if(v.first != par && !dd[v.first] && sz[v.first] > cnt / 2) return ftr(v.first, u);
    return u;
}
void bfs(int u, int par, int len, int cnt) {
    if(len > k) return;
    val.emplace_back(len, cnt);
    for(auto &v : ad[u]) {
        if(v.first != par && !dd[v.first] && v.second + len <= k) {
            bfs(v.first, u, v.second + len, cnt + 1);
        }
    }
}
void ctr(int u, int par) {
    cnt = 0;
    dfs(u, 0);
    int c = ftr(u, u);
    dd[c] = 1;
    f[0] = 0;
    vector<int> del;
    for(auto v : ad[c]) {
        if(!dd[v.first]) {
            bfs(v.first, c, v.second, 1);
            for(auto &i : val) if(k >= i.first && f[k - i.first] != -1) ans = min(ans, i.second + f[k - i.first]);
            for(auto &i : val) f[i.first] = (f[i.first] < 0) ? i.second : min(i.second, f[i.first]), del.emplace_back(i.first);
            val.clear();
        }
    }
    for(auto &v : del) f[v] = -1;
    for(auto &v : ad[c]) if(!dd[v.first]) ctr(v.first, c);

}
int best_path(int _n, int _k, int h[][2], int l[]) {
    n = _n, k = _k;
    for(int i = 0; i < n - 1; ++i) {
        int u = h[i][0], v = h[i][1], c = l[i]; u++; v++;
        ad[u].emplace_back(v, c);
        ad[v].emplace_back(u, c);
    }
    memset(f, -1, sizeof(f));
    ans = INT_MAX;
    ctr(1, 0);
    return (ans == INT_MAX) ? -1 : ans;
}
/*
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    cin >> n >> k;
    static int h[N][2], le[N];
    for(int i = 0; i < n - 1; ++i) cin >> h[i][0] >> h[i][1] >> le[i];
    cout << best_path(n, k, h, le);
}
*/

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