| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 378262 | Blerargh | 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 "race.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define _ <<" "<<
#define cerr if(false)cerr
/*
Test case :
11 12
0 1 3
0 2 4
2 3 5
3 4 4
4 5 6
0 6 3
6 7 2
6 8 5
8 9 6
8 10 7
2
Test case :
4 3
0 1 1
1 2 2
1 3 4
2
*/
typedef pair<ll,ll> ii;
typedef tuple<ll,ll,ll,ll> tl; //actual dist, tree dist, offset, node
const ll MAXN = 2e5+5;
const ll INF = 1e18;
vector<ii> adjlist[MAXN];
bool visited[MAXN];
multiset<ii> s[MAXN];
int ans=INF, stsize[MAXN], k;
void setmerging(ll u, ll dis, ll dep){
visited[u] = 1;
stsize[u] = 1;
ll maxsize=0, maxid=-1;
for (auto v : adjlist[u]){
if (visited[v.first]) continue;
setmerging(v.first, dis+v.second, dep+1);
stsize[u] += stsize[v.first];
if (stsize[v.first] > maxsize){
maxsize = stsize[v.first];
maxid = v.first;
}
}
cerr << "1Node" _ u _ ": ";
for (auto st : s[u]) {
cerr << "{" << st.first << "," _ st.second << "}, ";
}
cerr << '\n';
cerr << maxid _ maxsize _ '\n';
s[u].emplace(dis, dep);
if (maxid != -1) s[u].swap(s[maxid]);
cerr << "2Node" _ u _ ": ";
for (auto st : s[u]) {
cerr << "{" << st.first << "," _ st.second << "}, ";
}
cerr << '\n';
for (auto v : adjlist[u]){
ll node = v.first;
for (auto ss : s[node]){
ll actdist = ss.first;
ll treedist = ss.second;
auto it = s[u].lower_bound(make_pair(k-actdist+2*dis, 0));
if ((*it).first == k - actdist + 2*dis){
ans = min(ans, treedist + (*it).second - 2*dep);
cerr << "Found:" _ "{" << ss.first << "," _ ss.second << "}, {" << (*it).first << "," _ (*it).second << "}\n";
}
}
for (auto ss : s[node]) s[u].emplace(ss);
}
cerr << "3Node" _ u _ ": ";
for (auto st : s[u]) {
cerr << "{" << st.first << "," _ st.second << "}, ";
}
cerr << '\n';
}
int best_path(int N, int K, int H[][2], int L[]){
k = K;
for (int i=0; i<N-1; i++){
ll a = H[i][0], b = H[i][1], w = L[i];
adjlist[a].emplace_back(b, w);
adjlist[b].emplace_back(a, w);
}
setmerging(0, 0, 0);
if (ans == INF) return -1;
else return ans;
}