제출 #743730

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
743730		vjudge1	경주 (Race) (IOI11_race)	C++17	0 / 100	18 ms	31660 KiB

race

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define EPS 1e-9
#define all(x) x.begin(),x.end()
#define allr(x) x.rbegin(),x.rend()
#define yes cout << "YES" << '\n';
#define no cout << "NO" << '\n';
#define mem(arrr, xx) memset(arrr,xx,sizeof arrr)
#define endl '\n'
#define PI acos(-1)
#define Ones(n) __builtin_popcount(n)
#define Onesl(n) __builtin_popcountll(n)
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
const ll MOD = 1e9 + 7;
const ll M = 1e6 + 5;
const int OO = 0x3f3f3f3f;
const ll LOO = 0x3f3f3f3f3f3f3f3f;
int dx8[] = {+0, +0, -1, +1, +1, +1, -1, -1};
int dy8[] = {-1, +1, +0, +0, +1, -1, +1, -1};
int dx4[] = {+0, +0, -1, +1};
int dy4[] = {-1, +1, +0, +0};

void Fast() {
    cin.tie(nullptr), cout.tie(nullptr), cin.sync_with_stdio(false), cout.sync_with_stdio(false);
#ifdef Clion
    freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout);
#endif
}

int sz[M],par[M];
vector<pair<int ,int>> adj[M];
vector<pair<ll, ll>> nodes;
bool vis[M];
int dfsSz(int u, int p) {
    int &ret = sz[u] = 1;
    for (auto v: adj[u]) {
        if (vis[v.first] || v.first == p)continue;
        ret += dfsSz(v.first, u);
    }
    return ret;
}

int getCentroid(int u, int p, int n) {
    for (auto v: adj[u]) {
        if (vis[v.first] || v.first == p)continue;
        if (sz[v.first] * 2 > n)
            return getCentroid(v.first, u, n);
    }
    return u;
}

vector<ll> vals;
ll ans;
int k;
void collect(int u, int p, ll sum, int dis) {
    nodes.emplace_back(sum, dis);
    vals.emplace_back(sum);
    for(auto v:adj[u]){
        if(vis[v.first] || v.first == p)continue;
        collect(v.first,u, sum + v.second, dis + 1);
    }
}
ll dp[M];
void build(int u, int p) {
    int n = dfsSz(u, p);
    int centroid = getCentroid(u, p, n);

    if(~p)par[centroid] = p;
    else par[centroid] = centroid;

    vis[centroid] = true;
    for (auto v: adj[centroid]) {
        if(vis[v.first] || v.first == par[centroid])continue;
        nodes.clear();
        collect(v.first, centroid, v.second, 1);
        for(auto f : nodes){
            if(f.first > k)continue;
            ans = min(ans, dp[k - f.first] + f.second);
        }
        for(auto f : nodes){
            if(f.first > k)continue;
            dp[f.first] = min(dp[f.first], f.second);
        }

    }
    for(auto f : vals){
        if(f > k)continue;
        dp[f] = OO;
    }
    vals.clear();
    for (auto v: adj[centroid]) {
        if(vis[v.first] || v.first == par[centroid])continue;
        build(v.first, centroid);
    }
}
int best_path(int N, int K, int H[][2], int L[]) {
    int n;
    n = N, k = K;
    for (int i = 0; i < M; ++i) {
        dp[i] = OO;
    }
    for (int i = 0; i < n - 1;   ++i) {
        int u = H[i][0] - 1, v = H[i][1] - 1, c = L[i];
        adj[u].emplace_back(v, c);
        adj[v].emplace_back(u, c);
    }
    ans = OO;
    build(0, 0);
    if(ans == OO){
        ans = -1;
    }
    return ans;
}

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