| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1222060 | monaxia | Dreaming (IOI13_dreaming) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#include <ext/random>
#include <ext/pb_ds/assoc_container.hpp>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC optimize ("Ofast")
#define pb push_back
#define ppb pop_back
#define fr first
#define sc second
#define all(v) v.begin(), v.end()
#define all1(v) v.begin() + 1, v.begin() + n + 1
using namespace std;
using namespace __gnu_pbds;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
constexpr uint64_t Mod = 1e9 + 7;
constexpr ld eps = 1e-9;
constexpr int sqr = 447;
int n = 2e5;
ll ans = 0;
vector <ll> val(n + 1);
vector <vector <pair <int ,int>>> graph(n + 1);
vector <vector <int>> p(n + 5, vector <int> (40, -1));
vector <int> h(n + 1, 0), v(n + 1, 0);
void dfs1111(int node, int pr){
h[node] = h[pr] + 1;
p[node][0] = pr;
for(auto& x : graph[node]){
if(x.fr == pr) continue;
dfs1111(x.fr, node);
}
}
void preprocess(){
dfs1111(1, 0);
for(int j = 1; 1 << j <= n; j ++){
for(int i = 1; i <= n; i ++){
if(p[i][j - 1] != -1) p[i][j] = p[p[i][j - 1]][j - 1];
}
}
}
int lca(int u, int v){
if(h[u] < h[v]) swap(u, v);
while(h[u] > h[v]){
u = p[u][__lg(h[u] - h[v])];
}
if(u == v) return u;
for(int i = __lg(n); i >= 1; i --){
if(p[u][i] != p[v][i]){
u = p[u][i];
v = p[v][i];
}
}
while(u != v){
u = p[u][0];
v = p[v][0];
}
return u;
}
vector <gp_hash_table <int, ll>> cnt(n + 1), total(n + 1);
vector <multiset <ll>> value(n + 1);
ll mn = LLONG_MAX, mx = LLONG_MIN;
void dfs1(int node, int p){
v[node] = 1;
for(auto& x : graph[node]){
if(x.fr == p) continue;
dfs1(x.fr, node);
total[node][x.fr] += total[x.fr][x.fr];
total[node][node] = max(total[node][node], total[x.fr][x.fr] + cnt[x.fr][x.fr] * x.sc);
value[node].insert(total[x.fr][x.fr] + cnt[x.fr][x.fr] * x.sc);
}
}
void dfs(int node, int p, int d){
if(p){
auto w = value[p].rbegin();
if(cnt[node][node] * d + total[node][node] == total[p][p]) w ++;
total[node][node] = max(total[node][node], *w + d);
value[node].insert(*w + d);
// cout << node << ' ' << *w << " " << d << "\n";
// cout << node << " " << p << " " << cnt[p][p] - cnt[p][node] << " " << (cnt[p][p] - cnt[p][node]) * d << "\n";
}
auto test = value[node].end();
test ++;
mn = min(mn, total[node][node]);
for(auto& x : graph[node]){
if(x.fr == p) continue;
dfs(x.fr, node, x.sc);
}
}
void solve(){
ll n, m, l;
cin >> n >> m >> l;
for(int i = 1; i <= m; i ++){
int u, v, d;
cin >> u >> v >> d;
u ++;
v ++;
// cout << u << ' ' << v << " " << d << "\n";
graph[u].pb({v, d});
graph[v].pb({u, d});
}
for(int i = 1; i <= n; i ++) cnt[i][i] = 1, value[i].insert(0);
vector <ll> ans;
for(int i = 1; i <= n; i ++){
if(v[i]) continue;
dfs1(i, 0);
dfs(i, 0, 0);
ans.pb(mn);
// for(int j = 1; j <= n; j ++) cout << v[j] << ' '; cout << "\n";
// cout << mn << '\n';
mn = LLONG_MAX;
// cout << "\n";
}
// for(int i = 1; i <= n; i ++){
// for(int j = 1; j <= n; j ++) cout << total[i][j] << ' '; cout << '\n';
// } cout << "\n";
// for(int i = 1; i <= n; i ++){
// for(int j = 1; j <= n; j ++) cout << cnt[i][j] << ' '; cout << '\n';
// }
sort(all(ans), greater <> ());
for(int i = 1; i < ans.size(); i ++) ans[i] += l;
sort(all(ans), greater <> ());
// for(auto& x : ans) cout << x << ' ';
if(ans.size() > 1) cout << ans[0] + ans[1];
else cout << ans[0];
}
signed main()
{
cin.tie(0)->sync_with_stdio(0);
ll n = 1;
// cin >> n;
while(n) {
solve();
n --;
cout << "\n";
}
cerr << "t elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
}