| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 702083 |
2023-02-22T19:11:33 Z |
vuk_ |
Dreaming (IOI13_dreaming) |
C++17 |
|
0 ms |
0 KB |
#pragma once
#include "dreaming.h"
#include <iostream>
#include <list>
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;
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, 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];
int graph_min_dist = INT_MAX;
int graph_min_node = -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);
}
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 travelTime(int n, int m, int l, int A[], int B[], int T[]) {
graph g(n, m);
FOR(m) {
g.add_edge(A[i], B[i], T[i]);
}
int a[3] = { -l, -l, -l };
FOR(n) {
if (!seen[i]) {
graph_min_dist = INT_MAX;
billabong(g, i);
insert(a, graph_min_dist);
}
}
return max(a[0] + a[1] + l, a[1] + a[2] + l + l);
}
Compilation message
dreaming.cpp:1:9: warning: #pragma once in main file
1 | #pragma once
| ^~~~
dreaming.cpp:106:22: error: 'INT_MAX' was not declared in this scope
106 | int graph_min_dist = INT_MAX;
| ^~~~~~~
dreaming.cpp:7:1: note: 'INT_MAX' is defined in header '<climits>'; did you forget to '#include <climits>'?
6 | #include <list>
+++ |+#include <climits>
7 | using namespace std;
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:171:21: error: 'INT_MAX' was not declared in this scope
171 | graph_min_dist = INT_MAX;
| ^~~~~~~
dreaming.cpp:171:21: note: 'INT_MAX' is defined in header '<climits>'; did you forget to '#include <climits>'?
