제출 #751143

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
751143		tranxuanbach	Race (IOI11_race)	C++17	100 / 100	416 ms	145320 KiB

race

#include "race.h"

#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

#define endl '\n'
#define fi first
#define se second
#define For(i, l, r) for (auto i = (l); i < (r); i++)
#define ForE(i, l, r) for (auto i = (l); i <= (r); i++)
#define FordE(i, l, r) for (auto i = (l); i >= (r); i--)
#define Fora(v, a) for (auto v: (a))
#define bend(a) (a).begin(), (a).end()
#define isz(a) ((signed)(a).size())

using ll = long long;
using ld = long double;
using pii = pair <int, int>;
using vi = vector <int>;
using vpii = vector <pii>;
using vvi = vector <vi>;

const int N = 2e5 + 5;

int k;
vpii adj[N];
int h[N];
ll d[N];
int sz[N];

void dfs_sz(int u, int p = -1){
    sz[u] = 1;
    for (auto [v, w]: adj[u]){
        if (v == p){
            continue;
        }
        h[v] = h[u] + 1;
        d[v] = d[u] + w;
        dfs_sz(v, u);
        sz[u] += sz[v];
    }
}

int ans = INT_MAX;
gp_hash_table <ll, int> mpp[N];

void dfs_mergeset(int u, int p = -1){
    int heavy = -1;
    for (auto [v, w]: adj[u]){
        if (v == p){
            continue;
        }
        dfs_mergeset(v, u);
        if (heavy == -1 or sz[heavy] < sz[v]){
            heavy = v;
        }
    }
    if (heavy != -1){
        mpp[u].swap(mpp[heavy]);
    }
    for (auto [v, w]: adj[u]){
        if (v == p or v == heavy){
            continue;
        }
        for (auto [dpath, hpath]: mpp[v]){
            auto itr = mpp[u].find(k + 2 * d[u] - dpath);
            if (itr != mpp[u].end()){
                ans = min(ans, hpath + itr->se - 2 * h[u]);
            }
        }
        for (auto [dpath, hpath]: mpp[v]){
            auto itr = mpp[u].find(dpath);
            if (itr != mpp[u].end()){
                itr->se = min(itr->se, hpath);
            }
            else{
                mpp[u][dpath] = hpath;
            }
        }
    }
    {
        auto itr = mpp[u].find(k + d[u]);
        if (itr != mpp[u].end()){
            ans = min(ans, itr->se - h[u]);
        }
        mpp[u][d[u]] = h[u];
    }
}

int best_path(int n, int _k, int edge[][2], int weight[]){
    k = _k;
    For(i, 0, n - 1){
        auto [u, v, w] = tuple{edge[i][0], edge[i][1], weight[i]};
        adj[u].emplace_back(v, w);
        adj[v].emplace_back(u, w);
    }
    dfs_sz(0);
    dfs_mergeset(0);
    if (ans == INT_MAX){
        ans = -1;
    }
    return ans;
}

/*
==================================================+
INPUT                                             |
--------------------------------------------------|

--------------------------------------------------|
==================================================+
OUTPUT                                            |
--------------------------------------------------|

--------------------------------------------------|
==================================================+
*/

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