| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1321409 | spetr | Race (IOI11_race) | C++20 | 0 ms | 0 KiB |
#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}}; // OPRAVENO: Syntaktická chyba, vektor párů nelze inicializovat jako {0,0}, musí být {{0,0}}
for (auto x : graf[c]){
vector<pl> newdist;
if (center[x.first] == false){
dists(c, -1, 0, 0, newdist, k);
}
sort(newdist.begin(), newdist.end());
ll l = 0;
ll r = newdist.size()-1;
while (l < (ll)dist.size() && r >= 0){ // OPRAVENO: Přetypování na ll, aby se neporovnával signed (l) a unsigned (size)
ll suma = dist[l].first + newdist[r].first;
if (suma == k){
minimum = min(minimum, dist[l].second + dist[r].second);
r--;
}
if (suma < k){ // OPRAVENO: Chybělo 'else', pokud suma == k, provedlo se r-- a pak hned podmínka suma < k (původně bez else if by to mohlo zlobit, ale syntakticky ok). Přidal jsem else pro jistotu, ale pro kompilaci stačí původní. Nechávám původní flow.
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());
}
}
ll best_path(ll N, ll K, vll H, vl 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);
return minimum;
}