제출 #1137975

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1137975		antonn	경주 (Race) (IOI11_race)	C++20	100 / 100	395 ms	43080 KiB

race

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

#define F first
#define S second
 
using namespace std;
using ll = long long;
using pi = pair<int, int>;
using vi = vector<int>;
 
template<class T> bool ckmin(T& a, T b) { return b < a ? a = b, true : false; }
template<class T> bool ckmax(T& a, T b) { return a < b ? a = b, true : false; }

const int N = 2e5 + 7;
const int K = 1e6 + 7;

vector<pi> g[N];
int vis[N], sz[N], mn[K], full[K];
int ans = 1e9;

int centr = -1;

void calc_size(int u, int p = 0) {
    sz[u] = 1;
    for (auto [v, c] : g[u]) {
        if (!vis[v] && v != p) {
            calc_size(v, u);
            sz[u] += sz[v];
        }
    }
}

void fcen(int u, int total, int p = 0) {
    bool ok = 1;
    for (auto [v, c] : g[u]) {
        if (!vis[v] && v != p) {
            ok &= (2 * sz[v] <= total);
            fcen(v, total, u);
        }
    }
    ok &= (2 * (total - sz[u]) <= total);
    if (ok == 1) {
        centr = u;
    }
}

vector<int> now;

void build_chains(int u, int p, int sum, int len) {
    if (sum < K) {
        ckmin(mn[sum], len);
        now.push_back(sum);
    }
    
    for (auto [v, c] : g[u]) {
        if (!vis[v] && v != p) {
            build_chains(v, u, sum + c, len + 1);
        }
    }
}

void solve(int u, int k) {
    calc_size(u, u);
    fcen(u, sz[u]);
    calc_size(centr, centr);
    
    vector<int> all;
    for (auto [v, c] : g[centr]) {
        if (!vis[v]) {
            now.clear();
            build_chains(v, centr, c, 1);
            if (mn[k] != 1e9) ckmin(ans, mn[k]);
            for (auto x : now) if (x <= k) ckmin(ans, mn[x] + full[k - x]);
            for (auto x : now) ckmin(full[x], mn[x]);
            for (auto x : now) mn[x] = 1e9;
            for (auto x : now) all.push_back(x);
        }
    }
    for (auto x : all) full[x] = 1e9;
        
    vis[centr] = 1;
    int c = centr;
    for (auto [v, cost] : g[c]) {
        if (!vis[v]) {
            solve(v, k);
        }
    }
}

int best_path(int n, int k, int h[][2], int l[]) {
    for (int i = 0; i < n - 1; ++i) {
        ++h[i][0], ++h[i][1];
        g[h[i][0]].push_back({h[i][1], l[i]});
        g[h[i][1]].push_back({h[i][0], l[i]});
    }
    
    for (int i = 0; i < K; ++i) full[i] = mn[i] = 1e9;
    solve(1, k);
    if (ans >= 1e9) ans = -1;
    return ans;
}

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