| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 101180 | davitmarg | 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.
/*
DavitMarg
*/
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <iterator>
#include <ctype.h>
#include <stdlib.h>
#include <cassert>
#include <fstream>
#ifndef death
#include "race.h"
#endif
#define mod 1000000007ll
#define LL long long
#define LD long double
#define MP make_pair
#define PB push_back
#define all(v) v.begin(),v.end()
using namespace std;
int n, k, d[200005], used[200005], used1[200005], usedc[200005], ans = mod;
vector<pair<int, LL>> g[200005];
map<LL, int> dp;
vector<pair<LL, int>> upd;
void dfs1(int v)
{
usedc[v] = 1;
d[v] = 1;
for (int i = 0; i<g[v].size(); i++)
{
int to = g[v][i].first;
if (usedc[to])
continue;
dfs1(to);
d[v] += d[to];
}
}
int centroid(int v)
{
usedc[v] = 1;
for (int i = 0; i<g[v].size(); i++)
{
int to = g[v][i].first;
if (usedc[to])
continue;
if (d[to] > d[v] / 2)
return centroid(to);
}
return v;
}
void dfs(int v, LL dist, int depth)
{
used[v] = 1;
if (dp[dist] == 0)
dp[dist] = mod;
if (k > dist && dp[k - dist] == 0)
dp[k - dist] = mod;
upd.PB(MP(dist, depth));
if (k > dist)
ans = min(depth + dp[k - dist], ans);
else if (dist == k)
ans = min(depth, ans);
for (int i = 0; i<g[v].size(); i++)
{
int to = g[v][i].first;
LL D = g[v][i].second;
if (used[to])
continue;
dfs(to, dist + D, depth + 1);
}
}
void solve(int v)
{
used1[v] = 1;
usedc[v] = 1;
vector<int> nxt;
dp.clear();
memset(used, 0, sizeof(int)*(n + 2));
used[v] = 1;
for (int i = 0; i<g[v].size(); i++)
{
int to = g[v][i].first;
LL D = g[v][i].second;
if (used1[to])
continue;
nxt.PB(to);
upd.resize(0);
dfs(to, D, 1);
for (int j = 0; j < upd.size(); j++)
dp[upd[j].first] = min(upd[j].second, dp[upd[j].first]);
}
for (int i = 0; i < nxt.size(); i++)
solve(centroid(nxt[i]));
}
int Main()
{
dfs1(1);
memset(usedc, 0, sizeof(int)*(n + 2));
int c = centroid(1);
memset(usedc, 0, sizeof(int)*(n + 2));
solve(c);
if (ans == mod)
ans = -1;
return 0;
}
LL best_path(int N, int K, vector<vector<int>> h, vector<LL> l)
{
n = N;
k = K;
reverse(all(l));
for (int i = 0; i < h.size(); i++)
{
h[i][0]++;
for (int j = 1; j < h[i].size(); j++)
{
h[i][j]++;
g[h[i][0]].PB(MP(h[i][j], l.back()));
g[h[i][j]].PB(MP(h[i][0], l.back()));
l.pop_back();
}
}
Main();
return ans;
}
#ifdef death
int main()
{
cin >> n >> k;
for (int i = 0; i < n - 1; i++)
{
int a, b;
LL D;
cin >> a >> b >> D;
a++;
b++;
g[a].PB(MP(b, D));
g[b].PB(MP(a, D));
}
Main();
cout << ans << endl;
return 0;
}
#endif
/*
*/