| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1269622 | omarpaladines95 | Dreaming (IOI13_dreaming) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = (1LL<<60);
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
long long L;
if(!(cin >> n >> m >> L)) return 0;
vector<vector<pair<int,long long>>> adj(n+1);
for(int i=0;i<m;i++){
int u,v; long long w;
cin >> u >> v >> w;
adj[u].push_back({v,w});
adj[v].push_back({u,w});
}
vector<int> vis(n+1, 0);
vector<long long> radii; // radii of components
long long maxDiam = 0; // maximum diameter among components
// Dijkstra on a given component starting from node s,
// returns farthest node and fills dist array.
auto dijkstra_on_component = [&](int s, vector<long long>& dist, vector<int>& comp_nodes) -> int {
// discover component nodes with BFS/stack (graph is forest but edges weighted)
comp_nodes.clear();
stack<int> st;
st.push(s);
vis[s] = 1; // mark temporarily (we'll rely on this for component discovery)
while(!st.empty()){
int u = st.top(); st.pop();
comp_nodes.push_back(u);
for(auto &e: adj[u]){
int v = e.first;
if(!vis[v]){
vis[v] = 1;
st.push(v);
}
}
}
// reset visited marks for Dijkstra use (we'll keep these nodes tracked)
for(int v: comp_nodes) vis[v] = 0;
// run Dijkstra from s but only on nodes in this component
unordered_set<int> compset(comp_nodes.begin(), comp_nodes.end());
dist.assign(n+1, INF);
using pli = pair<long long,int>;
priority_queue<pli, vector<pli>, greater<pli>> pq;
dist[s] = 0;
pq.push({0,s});
while(!pq.empty()){
auto [d,u] = pq.top(); pq.pop();
if(d != dist[u]) continue;
for(auto &e: adj[u]){
int v = e.first; long long w = e.second;
if(compset.count(v) == 0) continue;
if(dist[v] > d + w){
dist[v] = d + w;
pq.push({dist[v], v});
}
}
}
// find farthest node
int far = s;
long long best = -1;
for(int v: comp_nodes){
if(dist[v] < INF && dist[v] > best){
best = dist[v]; far = v;
}
}
return far;
};
vector<long long> distA, distB;
vector<int> comp_nodes;
// We'll iterate all nodes; when we find an unvisited node, we discover its component and compute diam & radius.
vector<char> seen(n+1, 0);
for(int i=1;i<=n;i++){
if(seen[i]) continue;
// collect component nodes by DFS (unweighted) to mark them as seen
comp_nodes.clear();
stack<int> st;
st.push(i);
seen[i] = 1;
while(!st.empty()){
int u = st.top(); st.pop();
comp_nodes.push_back(u);
for(auto &e: adj[u]){
int v = e.first;
if(!seen[v]){
seen[v] = 1;
st.push(v);
}
}
}
// pick arbitrary node s = comp_nodes[0]
int s = comp_nodes[0];
// Dijkstra from s to get farthest a
// To restrict Dijkstra to this component, we will create a set of its nodes (below)
// Dijkstra from s -> far a
// reuse the helper: but it re-discovers component; easier: we directly run Dijkstra twice
unordered_set<int> compset(comp_nodes.begin(), comp_nodes.end());
auto do_dij = [&](int start, vector<long long> &distOut){
distOut.assign(n+1, INF);
using pli = pair<long long,int>;
priority_queue<pli, vector<pli>, greater<pli>> pq;
distOut[start] = 0;
pq.push({0, start});
while(!pq.empty()){
auto [d,u] = pq.top(); pq.pop();
if(d != distOut[u]) continue;
for(auto &e: adj[u]){
int v = e.first; long long w = e.second;
if(compset.count(v) == 0) continue;
if(distOut[v] > d + w){
distOut[v] = d + w;
pq.push({distOut[v], v});
}
}
}
};
// first Dijkstra
do_dij(s, distA);
int a = s;
long long bestd = -1;
for(int v: comp_nodes){
if(distA[v] < INF && distA[v] > bestd){
bestd = distA[v]; a = v;
}
}
// second Dijkstra from a
do_dij(a, distA); // distA now distances from a
int b = a; bestd = -1;
for(int v: comp_nodes){
if(distA[v] < INF && distA[v] > bestd){
bestd = distA[v]; b = v;
}
}
long long diam = bestd; // diameter of this component
maxDiam = max(maxDiam, diam);
// run dijkstra from b to get distB
do_dij(b, distB);
// compute radius = min_v max(distA[v], distB[v])
long long radius = INF;
for(int v: comp_nodes){
long long ecc = max(distA[v], distB[v]);
radius = min(radius, ecc);
}
// radius should be finite
radii.push_back(radius);
}
// If there is only one component, answer is its internal maxDiam
sort(radii.begin(), radii.end(), greater<long long>());
long long answer = maxDiam;
int k = (int)radii.size();
if(k == 1){
// already answer = maxDiam
} else if(k == 2){
answer = max(answer, radii[0] + radii[1] + L);
} else {
// three or more components
answer = max(answer, radii[0] + radii[1] + L);
answer = max(answer, radii[1] + radii[2] + 2*L);
}
cout << answer << "\n";
return 0;
}