| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1213627 | moondarkside | Race (IOI11_race) | C++20 | 0 ms | 0 KiB |
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
int n,k;
map<int,std::vector<std::pair<int, int>>> Roads;
vector<bool> Visited;
priority_queue<struct PriorityPoint> EdgePriority;
vector<pair<int,int>>Steps;
map<int,int> Win;
bool Unit;
struct PriorityPoint {
int id;
int priority;
};
bool operator< (const struct PriorityPoint& a,const struct PriorityPoint& b) {
return b.priority>a.priority;
}
void bfsFindEdges(int parent,int current) {
int exec=0;
for(int i=0; i<Roads[current].size(); i++) {
int next=Roads[current][i].first;
if(Visited[next]==false) {
exec++;
if(parent!=next) {
bfsFindEdges(current,next);
}
}
}
if(exec==0) {
Unit=true;
}
if(exec==1) {
EdgePriority.push({current,1});
}
return;
}
int GetCentriod(int base) {
EdgePriority=priority_queue <struct PriorityPoint>();
Unit=false;
bfsFindEdges(-1,base);
if(Unit) {
return -1;
}
int last=0;
vector<int> TimesVisited (n,0);
vector<int> Value(n,1);
int iter=0;
while(!EdgePriority.empty() && iter<100000) {
iter++;
int me=EdgePriority.top().id;
TimesVisited[me]=-1000000;
last=me;
for(int i=0; i<Roads[me].size(); i++) {
int other=Roads[me][i].first;
if(Visited[other]==false) {
Value[other]=Value[other]+EdgePriority.top().priority;
TimesVisited[other]=TimesVisited[other]+1;
if(TimesVisited[other]+1==Win[other]) {
EdgePriority.push({other,Value[other]});
}
}
}
EdgePriority.pop();
}
return last;
}
void bfsGetDistance(int parent,int base,int steps,int lenght) {
Steps.push_back({lenght,steps});
for(int i=0; i<Roads[base].size(); i++) {
int next=Roads[base][i].first;
if(Visited[next]==false) {
if(parent!=next) {
bfsGetDistance(base,next,steps+1,lenght+Roads[base][i].second);
}
}
}
}
int bestPathFrom(int base) {
int res=100000000;
int centroid=GetCentriod(base);
if(centroid==-1) {
Visited[base]=true;
return 100000000;
}
Visited[centroid]=true;
map<int,int> Best;
Best[0]=1;
for(int i=0; i<Roads[centroid].size(); i++) {
int next=Roads[centroid][i].first;
if(Visited[next]==false) {
Steps.clear();
Win[next]=Win[next]-1;
bfsGetDistance(centroid,Roads[centroid][i].first,1,Roads[centroid][i].second);
map<int,std::vector<std::pair<int, int>>> p =Roads;
for(int i=0; i<Steps.size(); i++) {
int len=Steps[i].first;
if(Best[k-len]>0) {
res=min(Best[k-len]+Steps[i].second-1,res);
}
}
for(int i=0; i<Steps.size(); i++) {
int len=Steps[i].first;
if(Best[len]==0) {
Best[len]=Steps[i].second+1;
}
else {
Best[len]=min(Best[len],Steps[i].second+1);
}
}
}
}
for(int i=0; i<Roads[centroid].size(); i++) {
int next=Roads[centroid][i].first;
if(Visited[next]==false) {
res=min(res,bestPathFrom(next));
}
}
return res;
}
int best_path(int N,int K,int H[][2],int L[] ) {
n=N;
k=K;
Visited.push_back(false);
for(int i=0; i<N-1; i++) {
Visited.push_back(false);
Win[H[i][0]]=Win[H[i][0]]+1;
Win[H[i][1]]=Win[H[i][1]]+1;
int a=H[i][0];
int b=H[i][1];
Roads[a].push_back({b,L[i]});
Roads[b].push_back({a,L[i]});
}
int ret=bestPathFrom(0);
if(ret==100000000) {
return -1;
}
return ret;