Submission #697244

#	Time	Username	Problem	Language	Result	Execution time	Memory
697244		Hacv16	Race (IOI11_race)	C++17	0 / 100	61 ms	95708 KiB

race

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

#define fr first
#define sc second

typedef long long ll;
const int MAX = 2e6 + 15;
const int INF = 0x3f3f3f3f;

ll n, k, ans, sub[MAX], f[MAX];
vector<pair<ll, ll>> adj[MAX], update;
vector<ll> fixupdate;
bool removed[MAX];

void dfsInit(int u, int p){
    sub[u] = 1;

    for(auto e : adj[u]){
        int v = e.fr;
        if(v == p || removed[v]) continue;
        dfsInit(v, u);
        sub[u] += sub[v];
    }
}

int findCentroid(ll u, ll p, ll sz){
    for(auto e : adj[u]){
        if(e.fr == p || removed[e.fr]) continue;
        if(sub[e.fr] > sz / 2) 
            return findCentroid(e.fr, u, sz);
    }

    return u;
}

void dfsCalc(ll u, ll p, ll edges, ll length){
    update.emplace_back(length, edges);
    fixupdate.emplace_back(length);

    for(auto e : adj[u]){
        ll v = e.fr, w = e.sc;
        if(v == p || removed[v]) continue;
        dfsCalc(v, u,  edges + 1, length + w);
    }
}

void decompose(ll u){
    dfsInit(u, -1);
    ll centroid = findCentroid(u, -1, sub[u]);
    removed[centroid] = true;   

    f[0] = 0;

    for(auto e : adj[centroid]){
        if(removed[e.fr]) continue; 
        dfsCalc(e.fr, centroid, 1, e.sc);

        for(auto p : update)
            if(p.fr <= k) ans = min(ans, p.sc + f[k - p.fr]);

        for(auto p : update)
            if(p.fr <= k) f[p.fr] = min(f[p.fr], p.sc);

        update.clear();
    }

    for(auto x : fixupdate) f[x] = INF;
    fixupdate.clear();

    for(auto e : adj[centroid])
        if(!removed[e.fr]) decompose(e.fr);
}

int best_path(int _n, int _k, int h[][2], int l[]){
    n = _n, k = _k;

    for(int i = 0; i < n - 1; i++){
        ll u = h[i][0], v = h[i][1], w = l[i];
        adj[u].emplace_back(v, w);
        adj[v].emplace_back(u, w);
    }

    ans = INF;
    for(int i = 0; i <= k; i++) f[i] = INF;

    decompose(0);

    return (ans == INF ? -1 : ans);
}

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