| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 710486 | aggrovector | Race (IOI11_race) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
int n,k,x,y,w,used[200005],vi[200005],fa[200005],subtree[200005],d[200005],d1[200005];
long long ans;
vector<pair<int,int>> v[200005];
vector<int> centroids;
unordered_map<int,int> cnt,cnt1;
bool flag,iscentroid;
const long long INF=1e15;
void dfs(int x, int f) {//subtree size
vi[x]=1;
fa[x]=f;
for (unsigned int i=0;i<v[x].size();i++) {
if (vi[v[x][i].first]==0 && used[v[x][i].first]==0) {
d1[v[x][i].first]=d1[x]+1;
dfs(v[x][i].first,f);
subtree[x]+=subtree[v[x][i].first];
}
}
subtree[x]++;
}
void dfs1(int x) {//distance by length and number of nodes
vi[x]=1;
for (unsigned int i=0;i<v[x].size();i++) {
if (vi[v[x][i].first]==0 && used[v[x][i].first]==0) {
d[v[x][i].first]=d[x]+v[x][i].second;
d1[v[x][i].first]=d1[x]+1;
dfs1(v[x][i].first);
}
}
}
void dfs2(int x, int f) {
vi[x]=1;
if (cnt.find(k-d[x])!=cnt.end()) {
ans=min(ans,(long long)cnt[k-d[x]]+d1[x]);
}
if (cnt1.find(d[x])==cnt1.end()) {
cnt1[d[x]]=d1[x];
}
else {
cnt1[d[x]]=min(cnt1[d[x]],d1[x]);
}
for (unsigned int i=0;i<v[x].size();i++) {
if (vi[v[x][i].first]==0 && used[v[x][i].first]==0) {
dfs2(v[x][i].first,f);
if (x==f) {
// cout << "x,i: " << x << ' ' << i << endl;
// cout << "cnt1: " << endl;
// for (auto it=cnt1.begin();it!=cnt1.end();it++) {
// cout << it->first << ' ' << it->second << endl;
// }
// cout << "cnt: " << endl;
for (auto it=cnt1.begin();it!=cnt1.end();it++) {
if (cnt.find(it->first)==cnt.end()) {
cnt[it->first]=it->second;
}
else {
cnt[it->first]=min(cnt[it->first],it->second);
}
}
// for (auto it=cnt.begin();it!=cnt.end();it++) {
// cout << it->first << ' ' << it->second << endl;
// }
cnt1.clear();
}
}
}
}
int main() {
// ifstream fin("P4149_5.in");
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> k;
for (auto i=1;i<n;i++) {
cin >> x >> y >> w;
v[x].emplace_back(y,w);
v[y].emplace_back(x,w);
}
ans=INF;
int cntt=0;
while(true) {
cntt++;
flag=true;
for (auto i=0;i<n;i++) {
subtree[i]=0;
vi[i]=0;
fa[i]=0;
d1[i]=0;
}
// cout << 1111 << endl;
for (auto i=0;i<n;i++) {
if (used[i]==0 && vi[i]==0) {
flag=false;
dfs(i,i);
}
}
// cout << 2222 << endl;
// cout << "subtree: ";
// for (i=0;i<n;i++) {
// cout << subtree[i] << ' ';
// }
// cout << endl;
// cout << "fa: ";
// for (i=0;i<n;i++) {
// cout << fa[i] << ' ';
// }
// cout << endl;
if (flag) {
break;
}
centroids.clear();
for (auto i=0;i<n;i++) {
if (used[i]==1) {
continue;
}
iscentroid=true;
for (long unsigned int j=0;j<v[i].size();j++) {
if (d1[v[i][j].first]>d1[i] && subtree[v[i][j].first]>subtree[fa[i]]/2) {
iscentroid=false;
}
}
if (subtree[fa[i]]-subtree[i]>subtree[fa[i]]/2) {
iscentroid=false;
}
if (iscentroid) {
centroids.push_back(i);
}
}
// cout << "centroids: ";
// for (i=0;i<centroids.size();i++) {
// cout << centroids[i] << ' ';
// }
// cout << endl;
for (auto i=0;i<n;i++) {
d[i]=0;
d1[i]=0;
vi[i]=0;
}
for (long unsigned int i=0;i<centroids.size();i++) {
if (vi[centroids[i]]==0) {
dfs1(centroids[i]);
}
}
// cout << "d: ";
// for (i=0;i<n;i++) {
// cout << d[i] << ' ';
// }
// cout << endl;
// cout << "d1: ";
// for (i=0;i<n;i++) {
// cout << d1[i] << ' ';
// }
// cout << endl;
for (auto i=0;i<n;i++) {
vi[i]=0;
}
for (long unsigned int i=0;i<centroids.size();i++) {
if (vi[centroids[i]]==0) {
cnt.clear();
cnt1.clear();
dfs2(centroids[i],centroids[i]);
used[centroids[i]]=1;
}
}
// cout << "used: ";
// for (i=0;i<n;i++) {
// cout << used[i] << ' ';
// }
// cout << endl;
// cout << "ans: " << ans << endl << endl;
}
if (ans==INF) {
cout << -1 << endl;
}
else {
cout << ans << endl;
}
// cout << cntt << endl;
}