| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 703023 | vuk_ | Dreaming (IOI13_dreaming) | 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.
#include <bits/stdc++.h>
using namespace std;
// Loops
#define FOR(n) for(int i=0;i<n;i++)
#define FORJ(n) for(int j=0;j<n;j++)
#define FORN(n,x) for(int x=0;i<n;i++)
#define RFOR(n) for(int i=n-1;i>=0;i--)
#define RFORN(n,x) for(int x=n-1;x>=0;x--)
#define ODD_FOR(n) for(int i=1;i<n;i+=2)
#define EVEN_FOR(n) for(int i=2;i<n;i+=2)
#define FROM(n,m) for(int i=n;i<m;i++)
#define FROMJ(n,m) for(int j=n;j<m;j++)
#define RFROM(n,m) for(int i=n-1;i>=m;i--)
#define RFROMJ(n,m) for(int j=n-1;j>=m;j--)
#define STL_FOR(a) for(auto i=a.begin();i!=a.end();i++)
#define STL_FORJ(a) for(auto j=a.begin();j!=a.end();j++)
#define STL_FORN(a,x) for(auto x=a.begin();x!=a.end();x++)
#define STL_FROM(a,n,m) for(auto i=n;i!=m;i++)
#define STL_FROMJ(n,m) for(auto j=n;j!=m;j++)
#define RSTL_FOR(a) for(auto i=a.rbegin();i!=a.rend();i++)
#define RSTL_FORJ(a) for(auto j=a.rbegin();j!=a.rend();j++)
// Types
#define ll long long int
#define vec vector
#define veci vector<int>
#define pb push_back
#define pf push_front
#define fi first
#define se second
#define umap unordered_map
#define ummap unordered_multimap
#define mmap multimap
#define mset multiset
#define uset unordered_set
#define umset unordered_multiset
#define endl '\n'
#define all(a) a.begin(), a.end()
// I/O
void read() {}
template<typename type, typename... types>
void read(type& arg,types&... args) { cin>>arg; read(args...); }
void write() { cout<<endl; }
template<typename type, typename... types>
void write(type arg, types... args) { cout<<arg<<' '; write(args...); }
#define dbg(x) cerr<<#x<<" = "<<x<<endl;
template<typename T>
class arr{
uint32_t n;
T* a;
public:
arr(const uint32_t& size):n(size) {
a=new T[n];
}
~arr() {
delete[] a;
}
T& operator[] (uint32_t indx) {
return a[indx];
}
uint32_t size() {
return n;
}
friend istream& operator>> (istream& in, arr& self) {
FOR(self.size()) {
in>>self[i];
}
return in;
}
friend ostream& operator<< (ostream& out, arr& self) {
FOR(self.size()) {
out<<self[i]<<'\n';
}
return out;
}
};
struct weighted_edge {
int edge, weight;
};
struct graph {
int n, m;
list<weighted_edge> *adj;
graph(int n, int m)
:n(n), m(m)
{
adj=new list<weighted_edge>[n];
}
~graph() {delete[] adj;}
void add_edge(int node,int edge, int weight) {
adj[node].push_back({edge, weight});
adj[edge].push_back({node, weight});
}
friend istream& operator>> (istream& in, graph& g) {
int node, edge, weight;
for(int i=0;i<g.m;i++) {
in>>node>>edge>>weight;
g.add_edge(node, edge, weight);
}
return in;
}
};
const int M=1e6;
struct node_dist{
int node;
ll dist=0;
};
struct two_max{
node_dist fi, se;
void add(int n, int d) {
if(fi.dist<d) {
se=fi;
fi={n, d};
} else if(se.dist<d) {
se={n, d};
}
}
};
two_max node_max_dist[M];
ll graph_min_dist=INT_MAX;
ll graph_min_node=-1;
ll max_dist=-1;
bool seen[M]={};
int billabong_front(graph& g, int node, int edge) {
seen[edge]=true;
for(weighted_edge x:g.adj[edge]) {
if(x.edge!=node) {
node_max_dist[edge].add(x.edge, billabong_front(g, edge, x.edge)+x.weight);
}
}
return node_max_dist[edge].fi.dist;
}
void billabong_back(graph& g, int node, int edge) {
if(graph_min_dist>node_max_dist[edge].fi.dist) {
graph_min_dist=node_max_dist[edge].fi.dist;
graph_min_node=edge;
}
for(weighted_edge x:g.adj[edge]) {
if(x.edge!=node) {
if(node_max_dist[edge].fi.node!=x.edge) {
node_max_dist[x.edge].add(edge, node_max_dist[edge].fi.dist+x.weight);
} else {
node_max_dist[x.edge].add(edge, node_max_dist[edge].se.dist+x.weight);
}
max_dist=max(max_dist, node_max_dist[x.edge].fi.dist+node_max_dist[x.edge].se.dist);
billabong_back(g, edge, x.edge);
}
}
}
inline void billabong(graph& g, int node) {
billabong_front(g, -1, node);
billabong_back(g, -1, node);
}
void insert(int a[3], int x) {
if(a[0]<x) {
a[2]=a[1];
a[1]=a[0];
a[0]=x;
} else if(a[1]<x) {
a[2]=a[1];
a[1]=x;
} else if(a[2]<x) {
a[2]=x;
}
}
int main() {
ifstream f("input.in");
int n, m, l;
f >> n >> m >> l;
graph g(n, m);
int node, edge, weight;
for (int i = 0; i < g.m; i++) {
f >> node >> edge >> weight;
g.add_edge(node, edge, weight);
}
f.close();
int a[3]={-l, -l, -l};
FOR(n) {
if(!seen[i]) {
graph_min_dist=INT_MAX;
billabong(g, i);
insert(a, graph_min_dist);
}
}
cout<<max(max_dist, max(a[0]+a[1]+l, a[1]+a[2]+l+l))<<endl;
}