| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 405069 | Vladth11 | Race (IOI11_race) | C++14 | 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>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define debug(x) cerr << #x << " " << x << "\n"
#define debug_with_space(x) cerr << #x << " " << x << " "
//#include"race.h"
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair <ll, ll> pii;
typedef pair <long double, pii> muchie;
typedef tree <ll, null_type, less_equal <ll>, rb_tree_tag, tree_order_statistics_node_update> OST;
const ll NMAX = 200001;
const ll INF = (1LL << 60);
const ll MOD = 1000000009;
const ll BLOCK = 225;
const ll base = 31;
const ll base2 = 53;
const ll nr_of_bits = 21;
vector <pii> v[NMAX];
int best = 2e9;
int k;
int sz[NMAX];
int total;
int viz[NMAX];
int d[NMAX];
struct ura{
int first, pfirst, second, psecond;
};
ura mp[1000001];
void getsize(int node, int p){
sz[node] = 1;
for(auto x : v[node]){
if(x.first == p || viz[x.first])
continue;
sz[node] += sz[x.first];
}
}
int centroid(int node, int p){
for(auto x : v[node]){
if(viz[x.first] || x.first == p){
continue;
}
if(sz[x.first] > total / 2)
return centroid(x.first, node);
}
return node;
}
int OneCentroid(int node){
getsize(node, 0);
return centroid(node, 0);
}
void ComputeDist(int node, int p, int subTree, int dist, int level){
d[node] = dist;
pii act = {level, subTree};
if(dist <= k && (mp[dist].pfirst != -1 || mp[dist].first >= level)){
if(mp[dist].pfirst != subTree){
swap(mp[dist].pfirst, mp[dist].psecond);
swap(mp[dist].first, mp[dist].second);
}
mp[dist].first = level;
mp[dist].pfirst = subTree;
}else if(dist <= k && mp[dist].pfirst != subTree && (mp[dist].psecond != -1 || mp[dist].second >= level)){
mp[dist].second = level;
mp[dist].psecond = subTree;
}
for(auto x : v[node]){
if(x.first == p || viz[x.first])
continue;
ComputeDist(x.first, node, subTree, d[node] + x.second, level + 1);
}
}
void Erase(int node, int p, int subTree, int level){
int dist = d[node];
pii act = {level, subTree};
if(dist <= k && (mp[dist].pfirst != -1 && mp[dist].pfirst == subTree)){
swap(mp[dist].pfirst, mp[dist].psecond);
swap(mp[dist].first, mp[dist].second);
mp[dist].psecond = -1;
mp[dist].second = 2e9;
}
for(auto x : v[node]){
if(x.first == p || viz[x.first])
continue;
Erase(x.first, node, subTree, level + 1);
}
}
void Add(int node, int p, int subTree, int level){
int dist = d[node];
pii act = {level, subTree};
if(dist <= k && (mp[dist].pfirst != -1 || mp[dist].first >= level)){
if(mp[dist].pfirst != subTree){
swap(mp[dist].pfirst, mp[dist].psecond);
swap(mp[dist].first, mp[dist].second);
}
mp[dist].first = level;
mp[dist].pfirst = subTree;
}else if(dist <= k && mp[dist].pfirst != subTree && (mp[dist].psecond != -1 || mp[dist].second >= level)){
mp[dist].second = level;
mp[dist].psecond = subTree;
}
for(auto x : v[node]){
if(x.first == p || viz[x.first])
continue;
Add(x.first, node, subTree, level + 1);
}
}
void Compute(int node, int p, int level){
int trb = k - d[node];
if(trb >= 0 && mp[trb].pfirst != -1)
{
int b = mp[trb].first;
best = min(best, b + level);
}
for(auto x : v[node]){
if(x.first == p || viz[x.first])
continue;
Compute(x.first, node, level + 1);
}
}
void CD(int node){
int c = OneCentroid(node);
viz[c] = 1;
for(int i = 0; i <= k; i++)
mp[i] = {(int)2e9, -1, (int)2e9, -1};
mp[0].first = 0;
mp[0].pfirst = 0;
for(auto x : v[c]){
if(viz[x.first])
continue;
ComputeDist(x.first, c, x.first, x.second, 1);
}
for(auto x : v[c]){
if(viz[x.first])
continue;
Erase(x.first, c, x.first, 1);
Compute(x.first, 0, 1);
Add(x.first, c, x.first, 1);
}
for(auto x : v[c]){
if(viz[x.first])
continue;
CD(x.first);
}
}
int best_path(int N, int K, int H[][2], int L[])
{
k = K;
for(int i = 0; i < N - 1; i++){
int a = H[i][0] + 1;
int b = H[i][1] + 1;
v[a].push_back({b, L[i]});
v[b].push_back({a, L[i]});
}
CD(1);
if(best == 2e9)
best = -1;
return best;
}
///
#define MAX_N 500000
static int N, K;
static int H[MAX_N][2];
static int L[MAX_N];
static int solution;
inline
void my_assert(int e) {if (!e) abort();}
void read_input()
{
int i;
my_assert(2==scanf("%d %d",&N,&K));
for(i=0; i<N-1; i++)
my_assert(3==scanf("%d %d %d",&H[i][0],&H[i][1],&L[i]));
my_assert(1==scanf("%d",&solution));
}
int main()
{
int ans;
read_input();
ans = best_path(N,K,H,L);
if(ans==solution)
printf("Correct.\n");
else
printf("Incorrect. Returned %d, Expected %d.\n",ans,solution);
return 0;
}