제출 #330982

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
330982		quindecim	Race (IOI11_race)	C++14	100 / 100	531 ms	33260 KiB

race

#include "race.h"
#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx2")
#include <bits/stdc++.h>
using namespace std;
using ull = long long;
const int INF = 0x3f3f3f3f;
const int MX = 200005;

int ans = INF, k, s[MX], used[300005], c;
vector<pair<int, int>> adj[MX], t;
vector<int> val(1000005, INF);
bitset<MX> r;

int dfs(int u, int p) {
    s[u] = 1;
    for(auto &v : adj[u])
        if(v.first!=p&&!r[v.first])
            s[u] += dfs(v.first, u);
    return s[u];
}

void dfs2(int u, int p, int l, int c) {
    if(k-l<0) return;
    if(val[k-l]!=INF) ans = min(ans, val[k-l]+c);
    t.push_back({l, c});
    for(auto &v : adj[u])
        if(v.first!=p&&!r[v.first])
            dfs2(v.first, u, l+v.second, c+1);
}

int get_centroid(int u, int p, int ms) {
    for(auto &v : adj[u])
        if(v.first!=p&&!r[v.first]&&s[v.first]*2>ms)
            return get_centroid(v.first, u, ms);
    return u;
}

void centroid(int u = 1) {
    int C = get_centroid(u, u, dfs(u, u));
    r[C] = 1;
    c = 0;
    for(auto &x : adj[C]) {
        if(!r[x.first]) {
            t.clear();
            dfs2(x.first, C, x.second, 1);
            for(auto &i : t) {
                if(i.first<=k) {
                    val[i.first] = min(val[i.first], i.second);
                    used[++c] = i.first;
                }
            }
        }
    }
    ans = min(ans, val[k]);
    for(; c; c--)
        val[used[c]] = INF;
    for(auto v : adj[C])
        if(!r[v.first])
            centroid(v.first);
}

int best_path(int N, int K, int H[][2], int L[]) {
    k = K;
    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]});
    }
    centroid();
    if(ans==INF) ans = -1;
    return ans;
}

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