Submission #1091739

#	Time	Username	Problem	Language	Result	Execution time	Memory
1091739		daviedu	Race (IOI11_race)	C++17	100 / 100	426 ms	90816 KiB

race

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

#define fastio ios_base::sync_with_stdio(0); cin.tie(0)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define sz(a) (int) (a).size()
#define ll long long
#define ld long double

struct P{
    ll x, y;
};

void dbg_out() { cerr << endl; }
template <typename H, typename... T>
void dbg_out(H h, T... t) { cerr << ' ' << h; dbg_out(t...); }
#define dbg(...) { cerr << #__VA_ARGS__ << ':'; dbg_out(__VA_ARGS__); }

const ll MX = 2e5+5;
vector<pair<ll, ll>> g [MX];
vector<ll> tour;
ll depth[MX], s[MX], st[MX], ed[MX];
ll dist[MX];

void calc(ll x, ll y, ll dp, ll ds){
    s[x] = 1;
    depth[x] = dp;
    st[x] = sz(tour);
    tour.push_back(x);
    dist[x] = ds;
    for (auto [z, w]: g[x]){
        if (z == y) continue;
        calc(z, x, dp+1, ds+w);
        s[x] += s[z];
    }
    ed[x] = sz(tour);
}

ll ans=MX+1;
ll delta = 0;
ll deltb = 0;
map<ll, ll> path;
set<ll> exists;
set<pair<ll, ll>> paths;
void dfs(ll x, ll y, ll k, bool keep){
    ll big=-1, bsize=-1, bdelta=0;
    for (auto [z, w]: g[x]){
        if (z == y) continue;
        if (s[z] > bsize) big = z, bsize = s[z], bdelta = w;
    }

    for (auto [z, w]: g[x]){
        if (z == y || z == big) continue;
        dfs(z, x, k, 0);
    }

    if (big != -1) dfs(big, x, k, 1), delta += bdelta, deltb++;

    // apply your delta to paths
    for (auto [z, w]: g[x]){
        if (z == y || z == big) continue;
        for (ll i=st[z]; i<ed[z]; i++){
            ll ds = dist[tour[i]] - dist[x];
            ll d = depth[tour[i]] - depth[x];

            if (!exists.count(k-ds-delta)) continue;
            ans = min(ans, d + path[k-ds-delta] + deltb);
        }
        for (ll i=st[z]; i<ed[z]; i++){
            ll ds = dist[tour[i]] - dist[x];
            ll d = depth[tour[i]] - depth[x];

            if (exists.count(ds-delta)) path[ds-delta] = min(path[ds-delta], d - deltb);
            else{
                exists.insert(ds-delta);
                path[ds-delta] = d - deltb;
            }
        }
    }
    if (exists.count(k-delta)){
        ans = min(path[k-delta] + deltb, ans);
    }
    exists.insert(-delta);
    path[-delta] = -deltb;

    if (keep) return;

    exists.clear();
    path.clear();
    delta = 0;
    deltb = 0;
}


int best_path(int n, int k, int edges[][2], int weights[]){
    for (int i=0; i<n-1; i++){
        g[edges[i][0]].push_back({edges[i][1], weights[i]});
        g[edges[i][1]].push_back({edges[i][0], weights[i]});
    }
    calc(0, 0, 0, 0);
    dfs(0, 0, k, 1);
    if (ans == MX+1) return -1;
    else return ans;
}

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