Submission #905079

#	Time	Username	Problem	Language	Result	Execution time	Memory
905079		a_l_i_r_e_z_a	Race (IOI11_race)	C++17	100 / 100	425 ms	104596 KiB

race

// In the name of God

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

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define pb push_back
#define S second
#define F first
#define mp make_pair
#define smax(x, y) (x) = max((x), (y))
#define smin(x, y) (x) = min((x), (y))
#define all(x) (x).begin(), (x).end()
#define len(x) ((int)(x).size())

const int maxn = 2e5 + 5, maxk = 1e6  + 5;
const int inf = 1e9 + 7;
ll n, k, ans = inf;
vector<pll> adj[maxn];
map<ll, ll> mn[maxn];

void dfs(int v = 0, int h = 0, ll d = 0, int p = -1){
    mn[v].insert(mp(d, h));
    for(auto [u, w]: adj[v]){
        if(u == p) continue;
        dfs(u, h + 1, d + w, v);
        if(mn[u].size() > mn[v].size()) swap(mn[u], mn[v]);
        for(auto w: mn[u]){
            ll x = k + 2 * d - w.F;
            auto it = mn[v].find(x);
            if(it != mn[v].end()) smin(ans, w.S + (*it).S - 2 * h);
        }
        for(auto w: mn[u]){
            auto it = mn[v].find(w.F);
            if(it != mn[v].end()) smin((*it).S, w.S);
            else mn[v].insert(w);
        }
    }
}

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], w = L[i];
        adj[u].pb(mp(v, w));
        adj[v].pb(mp(u, w));
    }
    dfs();
    return (ans >= inf ? -1 : ans);
}

// int32_t main()
// {
//     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

//     cin >> n >> k;
//     for(int i = 0; i < n - 1; i++){
//         int u, v, w; cin >> u >> v >> w;
//         adj[u].pb(mp(v, w));
//         adj[v].pb(mp(u, w));
//     }
//     dfs();
//     cout << (ans >= inf ? -1 : ans) << '\n';

//     return 0;
// }

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