| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1288336 | vivkostov | Race (IOI11_race) | C11 | 0 ms | 0 KiB |
#include "race.h"
#include <bits/stdc++.h>
using namespace std;
struct cell
{
int to,st;
};
struct ver
{
int lon,br;
};
int n,k,otg,dist=1e9,lead[200005],con[200005],dis[200005];
vector<cell>v[200005];
map<int,ver>m[200005];
void dfs(int beg,int par)
{
int w;
int ma=0,ind=0,va,cdi;
ver h;
if(beg!=0&&v[beg].size()==1)
{
lead[beg]=beg;
dis[beg]=0;
h.br=1;
h.lon=0;
m[beg][0]=h;
return;
}
for(int i=0;i<v[beg].size();i++)
{
w=v[beg][i].to;
if(w==par)continue;
dfs(w,beg);
con[lead[w]]+=v[beg][i].st;
dis[lead[w]]++;
if(ma<m[lead[w]].size())
{
ma=m[lead[w]].size();
ind=w;
}
}
lead[beg]=lead[ind];
h.br=1;
h.lon=-dis[lead[beg]];
m[lead[beg]][-con[lead[beg]]]=h;
cout<<ind<<" "<<ma<<endl;
for(int i=0;i<v[beg].size();i++)
{
w=v[beg][i].to;
if(w==par||w==ind)continue;
for(auto j=m[lead[w]].begin();j!=m[lead[w]].end();j++)
{
va=j->first;
va=k-va+con[lead[w]]-con[lead[beg]];
cdi=m[lead[beg]][va].lon+j->second.lon+dis[lead[beg]]+dis[lead[w]];
cout<<va<<" "<<cdi<<endl;
if(m[lead[beg]][va].br>0&&cdi<=dist)
{
cout<<beg<<"1111"<<endl;
if(cdi<dist)
{
dist=cdi;
otg=0;
}
otg+=m[lead[beg]][va].br;
}
if(m[lead[beg]][va].br==0)
{
m[lead[beg]].erase(va);
}
va=j->first;
va=va+con[lead[w]]-con[lead[beg]];
j->second.lon+=dis[lead[w]]-dis[lead[beg]];
if(m[lead[beg]][va].lon>j->second.lon)
{
m[lead[beg]][va]=j->second;
}
else if(m[lead[beg]][va].lon==j->second.lon)
{
m[lead[beg]][va].br+=j->second.br;
}
}
}
cout<<endl;
cout<<beg<<endl;
cout<<m[lead[beg]].size()<<endl;
cout<<beg<<" "<<con[lead[beg]]<<" "<<dis[lead[beg]]<<endl;
for(auto i=m[lead[beg]].begin();i!=m[lead[beg]].end();i++)
{
cout<<i->first<<" "<<i->second.lon<<" "<<i->second.br<<endl;
}
cout<<endl;
}
int best_path(int N, int K, int H[][2], int L[])
{
n=N;
k=K;
cell c;
for(int i=0;i<n-1;i++)
{
c.st=L[i];
c.to=H[i][1];
v[H[i][0]].push_back(c);
c.to=H[i][0];
v[H[i][1]].push_back(c);
}
dfs(0,0);
cout<<otg<<" "<<dist<<endl;
return N;
}