| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1286039 | dssfsuper2 | 경주 (Race) (IOI11_race) | C++20 | 0 ms | 0 KiB |
#include "race.h"
#include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
using pii = pair<long long, long long>;
vector<vector<pii>> graph;
bitset<200010> deactivated;
vector<long long> sts;
long long getsts(long long node, long long parent=-1){
sts[node]=1;
for(auto thing:graph[node]){
if(thing.first!=parent && !deactivated[thing.first])sts[node]+=getsts(thing.first, node);
}
return sts[node];
}
long long getcentroid(long long node, long long parent, long long tsize){
for(auto thing:graph[node]){
if(!deactivated[thing.first] && thing.first!=parent){
if(sts[thing.first]*2>tsize)return getcentroid(thing.first, node, tsize);
}
}
return node;
}
vector<pii> getpth(long long node, long long parent, long long ch, long long depth=0){
vector<pii> can;
can.push_back({ch, depth});
for(auto thing:graph[node]){
if(!deactivated[thing.first]&&thing.first!=parent){
vector<pii> thm=getpth(thing.first, node, ch+thing.second, depth+1);
for(auto thing:thm){
can.push_back(thing);
}
}
}
return can;
}
long long fres=1e9;
long long gk;
void calcmain(long long node){
long long res =0;
long long tsize=getsts(node);
long long curcen=getcentroid(node, -1, tsize);
//cerr << node << " a " << curcen << '\n';
//if(node==6)cerr<< sts[node] << ' ' << sts[8] << ' '<< sts[7] << ' ' << deactivated[0] << '\n';
long long cc=0;
map<long long, pair<pii, pii>> mc;
mc[0]={{0, 0}, {0, 0}};
vector<vector<long long>> total={{0, 0, 0}};
//i need a pair from different subtrees with the needed sum,
for(auto thing:graph[curcen]){
if(!deactivated[thing.first]){
cc++;
auto s = getpth(thing.first, curcen, thing.second, 1);
for(auto thing:s){
total.push_back({cc, thing.first, thing.second});
if(mc[thing.first].first.first==0 || mc[thing.first].first.first>thing.second)mc[thing.first].first={thing.second, cc};
}
}
}
long long cc2=0;
for(auto thing:total){
if(thing[0]!=mc[thing[1]].first.second && (mc[thing[1]].second.first==0 || mc[thing[1]].second.first>thing[2]))mc[thing[1]].second={thing[2], cc2};
}
for(auto thing:mc){
if(thing.second.first.first==0)continue;
//cerr << node << ' ' << thing.first << ' ' << thing.second.first.first << ' ' << thing.second.first.second << ' ' << thing.second.second.first << ' ' << thing.second.second.second << '\n';
long long clen=gk-thing.first;
pii cf=mc[clen].first;
if(cf.first==0)continue;
pii cs=mc[clen].second;
if(cf.second==thing.second.first.second){
if(cs.first==0)continue;
fres=min(fres, cs.first+thing.second.first.first);
//cerr << node << ' ' << cs.first << ' ' << thing.second.first.first << '\n';
}
else{
fres=min(fres, cf.first+thing.second.first.first);
//cerr << node <<' ' << cf.first << ' ' << thing.second.first.first << '\n';
}
}
//cerr << node << ' ' << fres << '\n';
deactivated[curcen]=1;
for(auto thing:graph[curcen]){
if(!deactivated[thing.first])calcmain(thing.first);
}
}
int best_path(int N, int K, int H[][2], int L[])
{
gk=K;
sts.resize(N+1);
graph.resize(N+1);
for(int i = 0;i<N-1;i++){
graph[H[i][0]].push_back({H[i][1], L[i]});
graph[H[i][1]].push_back({H[i][0], L[i]});
}
calcmain(0);
if(fres==1e9)return -1;
return fres;
}