Submission #1321417

#	Time	Username	Problem	Language	Result	Execution time	Memory
1321417		spetr	Race (IOI11_race)	C++20	0 / 100	0 ms	332 KiB

race

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

using namespace std;

#define ll long long
const ll mmod = 998244353;
#define vl vector<long long>
#define vll vector<vector<long long>>
#define pl pair<long long, long long>
#define vb vector<bool>

vector<vector<pl>> graf;
vb center;
vl sizes;
ll minimum = 1e15;

ll getsize(ll v, ll u){
    ll s = 1;
    for (auto x : graf[v]){
        if (center[x.first] == false && x.first != u){
            s += getsize(x.first, v);
        }
    }
    sizes[v] = s;
    return s;
}

ll findcentroid(ll v, ll u, ll n){
    ll a = 1;
    for (auto x : graf[v]){
        if (center[x.first] == false && x.first != u){
            a = findcentroid(x.first, v, n);
            if (a!=-1){
                return a;
            }
        }
    }
    if (sizes[v] >= n/2){
        return v;
    }
    else{
        return -1;
    }
}

void dists(ll v, ll u, ll d, ll depth, vector<pl>& dist, ll k){
    for (auto x : graf[v]){
        if (center[x.first] == false && x.first != u){
            if (d + x.second <= k){
                dist.push_back({d + x.second, depth});
                dists(x.first, v, d + x.second, depth + 1, dist, k);
            }
        }
    }
}

void decompose(ll v, ll k){
    ll comp = getsize(v,-1);
    ll c = findcentroid(v, -1, comp);
    center[c] = true;

    vector<pl> dist = {{0,0}}; 
    for (auto x : graf[c]){
        vector<pl> newdist;
        if (center[x.first] == false){
            dists(x.first, c, x.second, 1, newdist, k);
        }
        sort(newdist.begin(), newdist.end());
        ll l = 0;
        ll r = newdist.size()-1;
        while (l < (ll)dist.size() && r >= 0){
            ll suma = dist[l].first + newdist[r].first;
            if (suma == k){
                minimum = min(minimum, dist[l].second + dist[r].second);
                r--; 
            }
            else if (suma < k){ 
                l++;
            }
            else{
                r--;
            }
        }
        if (dist.size() < newdist.size()){
            swap(dist, newdist);
        }
        for (ll i = 0; i < newdist.size(); i++){
            dist.push_back(newdist[i]);
        }
        sort(dist.begin(), dist.end());
        
    }

    for (auto x : graf[c]){
        if (center[x.first] == false){
            decompose(x.first, k);
        }
    }
}

int best_path(int N, int K, int H[][2], int L[]){
    ll n = N; ll k = K;

    graf.resize(n);
    center.resize(n, false);
    sizes.resize(n,0);
    for (ll i = 0; i < n-1; i++){
        ll a,b;
        a = H[i][0]; b = H[i][1]; 
        ll c = L[i];            
        graf[a].push_back({b,c});
        graf[b].push_back({a,c});

    }
    decompose(0, k);
    
    if (minimum >= 1e14) return -1;
    return (int)minimum;
}

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