Submission #1244275

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244275		enjeeeff	Race (IOI11_race)	C++17	0 / 100	1 ms	320 KiB

race

#include<iostream>
#include<vector>
#include<map>
#include<set>
#include"race.h"
typedef long long ll;
#define vec vector
using namespace std;

struct Centroid {
    vec<vec<pair<ll, ll> > > adj;
    vec<ll> s, deleted;
    ll ans = 1e18, k;
    map<ll, multiset<ll> > mp, mp1;

    Centroid(ll n, ll dist) {
        k = dist;
        s.assign(n + 1, 0);
        deleted.assign(n + 1, 0);
        adj.assign(n + 1, {});
        // mp.assign(n + 1, {});
        // mp1.assign(n + 1, {});
    }

    void add(ll a, ll b, ll w) {
        adj[a].emplace_back(b, w);
        adj[b].emplace_back(a, w);
    }

    void count_sizes(ll v, ll par = -1) {
        s[v] = 1;
        for (auto &e : adj[v])
            if (!deleted[v] && par != e.first) {
                count_sizes(e.first, v);
                s[v] += s[e.first];
            }
    }

    ll find_centroid(ll v, ll n, ll par = -1) {
        for (auto &e : adj[v])
            if (!deleted[v] && par != e.first && s[e.first] * 2 > n)
                return find_centroid(e.first, n, v);
        return v;
    }

    void fullfill(ll v, ll par, ll dist, ll dist1 = 1) {
        for (auto &e : adj[v])
            if (!deleted[e.first] && e.first != par)
                fullfill(e.first, v, dist + e.second, dist1 + 1);
        mp[dist].insert(dist1);
    }

    void fullfill1(ll v, ll par, ll dist, ll dist1 = 1) {
        if (dist == k)
            ans = min(dist1, ans);
        for (auto &e : adj[v])
            if (!deleted[e.first] && e.first != par)
                fullfill1(e.first, v, dist + e.second, dist1 + 1);
        mp1[dist].insert(dist1);
        auto &gotSet = mp[dist];
        gotSet.erase(gotSet.find(dist1));
    }

    void constructAnswer(ll v = 0) {
        count_sizes(v);
        ll cnt = find_centroid(v, s[v]);

        mp.clear();
        deleted[cnt] = 1;
        for (auto &e : adj[cnt]) {
            if (deleted[e.first]) continue;
            fullfill(e.first, cnt, e.second);
        }

        for (auto &e : adj[cnt]) {
            if (deleted[e.first]) continue;
            fullfill1(e.first, cnt, e.second);

            for (auto &ofLength : mp1) {
                auto p = mp.find(k - ofLength.first);
                if (p == mp.end() || !p->second.size()) continue;
                ans = min(*p->second.begin() + *ofLength.second.begin(), ans);
            }

            fullfill(e.first, cnt, e.second);
            mp1.clear();
        }

        for (auto &e : adj[cnt])
            if (!deleted[e.first])
                constructAnswer(e.first);
    }
};

int best_path(int N, int K, int H[][2], int L[]) {
    ll n, k;
    // cin >> n >> k;
    n = N;
    k = K;
    Centroid structure(n, k);

    while (--n) {
        ll w;
        // cin >> a >> b >> w;
        auto [a, b] = H[n];
        w = L[n];
        
        structure.add(a, b, w);
    }
    structure.constructAnswer();

    cout << (structure.ans == 1e18 ? -1 : structure.ans) << '\n';
}

Compilation message (stderr)

race.cpp: In function 'int best_path(int, int, int (*)[2], int*)':
race.cpp:113:1: warning: no return statement in function returning non-void [-Wreturn-type]
  113 | }
      | ^

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