Submission #873802

#	Time	Username	Problem	Language	Result	Execution time	Memory
873802		AlesL0	Race (IOI11_race)	C++17	9 / 100	84 ms	19796 KiB

race

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

using namespace std;

typedef long long ll;

const ll maxn = 2e5+4;

vector <bool> vis;
vector <map <ll, ll>> f;
vector <ll> dep_points, dep_len;

ll sol = maxn;

void dfs_dep(ll c, vector <pair<ll, ll>> g[]){
    vis[c] = 1;
    for (auto x : g[c]){
        if (vis[x.first])continue;
        dep_points[x.first] = dep_points[c]+1;
        dep_len[x.first] = dep_len[c]+x.second;
        dfs_dep(x.first, g);
    }
    vis[c] = 0;
}

void compare_merge(map <ll, ll> &x, map <ll, ll> &y, ll add, ll c, ll k){
    if (x.size() > y.size())swap(x, y);
    for (auto it = x.begin(); it != x.end(); it++){
        if (k+add-(it->first) < 0)break;
        if (!y.count(k+add-(it->first)))continue;
        ll v = (it->first);
        sol = min(sol, x[v]+y[k+add-v]-dep_points[c]);
    }
    for (auto it = x.begin(); it != x.end(); it++){
        if (!y.count(it->first))y[it->first] = (it->second);
        else y[it->first] = min(y[it->first], it->second);
    }
    x.clear();

}

void dfs_solve(ll c, vector <pair<ll, ll>> g[], ll k){
    vis[c] = 1;
    f[c][dep_len[c]] = dep_points[c];
    for (auto x : g[c]){
        if (vis[x.first])continue;
        dfs_solve(x.first, g, k);
        compare_merge(f[x.first], f[c], 2*dep_len[c], c, k);
    }
    if (f[c].count(k+dep_len[c]))sol = min(sol, f[c][k+dep_len[c]]-dep_points[c]);
}

int best_path(int N, int K, int H[][2], int L[]){
    ll n = N, k = K;
    vector <pair<ll, ll>> g[n];
    vis.resize(n, 0);
    for (int i = 0; i < n-1; i++){
        g[H[i][0]].push_back({H[i][1], L[i]});
        g[H[i][1]].push_back({H[i][0], L[i]});
    }
    f.resize(n);
    dep_len.resize(n, 0);
    dep_points.resize(n, 0);
    dfs_dep(0, g);
    dfs_solve(0, g, k);
    if (sol == maxn)return -1;
    else return sol;
}

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