Submission #699258

#	Time	Username	Problem	Language	Result	Execution time	Memory
699258		gagik_2007	Race (IOI11_race)	C++17	0 / 100	5 ms	9684 KiB

race

#include "race.h"
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <chrono>
#include <ctime>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <limits>
#include <iomanip>
#include <unordered_set>
#include <unordered_map>
#include <fstream>
#include <functional>
#include <random>
#include <cassert>
using namespace std;

typedef long long ll;
typedef long double ld;

#define ff first
#define ss second

ll ttt;
const ll INF = 1e18;
const ll MOD = 1e9 + 7;
const ll maxN = 200507;
const ll LG = 18;
ll n, m, k;
set<pair<ll, ll>>g[maxN];
ll sz[maxN];
ll ans = INF;
map<ll, ll>cnt;

void dfs(ll v, ll par = -1) {
    sz[v] = 1;
    for (auto to : g[v]) {
        if (to.ff != par) {
            dfs(to.ff, v);
            sz[v] += sz[to.ff];
        }
    }
}

ll centroid(ll v, ll size, ll par = -1) {
    for (auto to : g[v]) {
        if (to.ff != par && sz[to.ff] > size / 2) {
            return centroid(to.ff, size, v);
        }
    }
    return v;
}

void upd_ans(ll v, ll dpt, ll size, ll cur, ll par = -1) {
    if (dpt <= k && k - dpt <= size) {
        if (k == dpt) {
            ans = min(ans, cur);
        }
        else {
            ans = min(ans, (cnt[k - dpt] == 0 ? INF : cnt[k - dpt]) + cur);
        }
    }
    else return;
    for (auto to : g[v]) {
        if (to.ff != par) {
            upd_ans(to.ff, dpt + to.ss, size, cur + 1, v);
        }
    }
}

void upd_cnt(ll v, ll dpt, ll cur, ll par = -1) {
    if (dpt != 0) {
        if (cnt[dpt] == 0) {
            cnt[dpt] = cur;
        }
        else {
            cnt[dpt] = min(cnt[dpt], cur);
        }
        //cout << v << ": " << dpt << ": " << cnt[dpt] << endl;
    }
    for (auto to : g[v]) {
        if (to.ff != par) {
            upd_cnt(to.ff, dpt + to.ss, cur + 1, v);
        }
    }
}

void mshak(ll c, ll size) {
    //cout << "MSHAKUM ENQ: " << c << endl;
    cnt.clear();
    for (auto to : g[c]) {
        upd_ans(to.ff, to.ss, size, 1, c);
        upd_cnt(to.ff, to.ss, 1, c);
    }
    /*for (auto x : cnt) {
        cout << x.ff << ": " << x.ss << endl;
    }*/
}

void cntr_dec(ll v, ll par = -1) {
    dfs(v, par);
    ll c = centroid(v, sz[v], par);
    mshak(c, sz[v]);
    set<pair<ll, ll>>g_copy(g[c]);
    for (auto to : g_copy) {
        g[c].erase(to);
        g[to.ff].erase({ c,to.ss });
        cntr_dec(to.ff, c);
    }
}

int best_path(int NN, int K, int H[][2], int L[]) {
    n = NN;
    k = K;
    for (int i = 0; i < n - 1; i++) {
        g[H[i][0]].insert({ H[i][1],L[i] });
        g[H[i][1]].insert({ H[i][0],L[i] });
    }
    cntr_dec(1);
    return (ans == INF ? -1 : ans);
}

/// ---- - --------  ------ -------- -- - - -
/// Just a reminder. Ubuntu password is I O I
/// ---- - --------  ------ -------- -- - - -

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