제출 #1321457

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1321457		spetr	경주 (Race) (IOI11_race)	C++20	100 / 100	378 ms	47856 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;
vl dist; 

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){
    dist.push_back({d, depth});
    for (auto x : graf[v]){
        if (center[x.first] == false && x.first != u){
            if (d + x.second <= k){
                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;
    vl found;
    for (auto x : graf[c]){
        vector<pl> newdist;
        if (center[x.first] == false){
            dists(x.first, c, x.second, 1, newdist, k);
        }

        for (ll i = 0; i < newdist.size(); i++){
            if (newdist[i].first > k ){
                break;
            }
            if (dist[k-newdist[i].first] != -1){
                minimum = min(minimum, newdist[i].second + dist[k-newdist[i].first]);
            }
        }
        for (ll i = 0; i < newdist.size(); i++){
            if (newdist[i].first > k ){
                break;
            }
            dist[newdist[i].first] = min(dist[newdist[i].first], newdist[i].second);
            if ( dist[newdist[i].first] == -1){
                dist[newdist[i].first] = newdist[i].second;
            }
        }

        for (ll i = 0; i < newdist.size(); i++){
            found.push_back(newdist[i].first);
        }
        
    }
    for (auto x : found){
        if (x != 0 && x <= k){
            dist[x] = -1;
        }
    }

    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.clear(); center.clear(); sizes.clear(); minimum = 1e14;
    graf.resize(n);
    center.resize(n, false);
    sizes.resize(n,0);
    dist.clear(); dist.resize(k+1, -1);
    dist[0] = 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: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 22 / 22
• Subtask 4: 57 / 57