| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 472060 | a520huynm | 꿈 (IOI13_dreaming) | 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>
using namespace std;
#define int long long
#define endl "\n"
#define fi first
#define se second
#define pb push_back
#define FAST ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define MASK(i) (1LL << (i))
#define BIT(x, i) (((x) >> (i)) & 1)
#define ALL(v) v.begin(), v.end()
const int MOD = 1e9 + 7;
const int LOG = 18;
const int INF = 1e9+7;
template<class X, class Y>
bool minimize(X &x, const Y &y) {
if (x > y)
{
x = y;
return true;
}
return false;
}
template<class X, class Y>
bool maximize(X &x, const Y &y) {
if (x < y)
{
x = y;
return true;
}
return false;
}
int dx [] {-1, 1, 0, 0};
int dy [] {0, 0, 1, -1};
//using namespace __gnu_pbds;
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
// .find_by_order() the number i-th in orderset
// .order_of_key() the number less more than k
/* Authors: Nguyen Minh Huy from Le Quy Don high school for Gifted Students */
#define TASK .....
#define MAX 100005
int n, m, len, down[MAX][5], up[MAX], result;
vector<pair<int, int>> adj[MAX];
void read() {
cin >> n >> m >> len;
for (int i = 1; i <= m; i++) {
int u, v, cost;
cin >> u >> v >> cost;
adj[u].push_back({v, cost});
adj[v].push_back({u, cost});
}
}
void calc_down(int u, int p) {
down[u][1] = down[u][2] = 0;
for (auto tmp : adj[u]) {
int cost = tmp.se;
int v = tmp.fi;
if (v == p) continue;
calc_down(v, u);
if (down[u][1] < down[v][1] + cost) {
down[u][2] = down[u][1];
down[u][1] = down[v][1] + cost;
}
else maximize(down[u][2], down[v][1] + cost);
}
}
void calc_up(int u, int p) {
minimize(result, max(down[u][1], up[u]));
for (auto tmp : adj[u]) {
int cost = tmp.se;
int v = tmp.fi;
if (v == p) continue;
up[v] = up[u] + cost;
if (down[u][1] == down[v][1] + cost) {
maximize(up[v], down[u][2] + cost);
}
else maximize(up[v], down[u][1] + cost);
calc_up(v, u);
}
}
void solve() {
multiset<int> s;
for (int i = 1; i <= n - 1; i++) {
if (!down[i][1] && !up[i]) {
int root = i;
result = INF;
calc_down(root, root);
calc_up(root, root);
//cout << result << " " << root << endl;
s.insert(result);
}
}
auto itr = s.rbegin();
itr--;
itr--;
itr--;
result = *s.rbegin() + *itr + len;
for (int i = 1; i <= n; i++) {
maximize(result, down[i][1] + up[i]);
}
cout << result;
}
/* Don't coppy :D */
signed main() {
//freopen("TASK.inp", "r", stdin);
//freopen("TASK.out", "w", stdout);
FAST;
int num_test = 1;
//cin >> num_test;
while (num_test--) {
read();
solve();
}
}