Submission #616692
Source Code Expand
#ifndef KOMAKI_LOCAL
#define NDEBUG
#endif
#include <bits/stdc++.h>
#include <sys/time.h>
#include <unistd.h>
using namespace std;
#define i64 int64_t
#define rep(i, n) for(i64 i = 0; i < ((i64)(n)); ++i)
#define sz(v) ((i64)((v).size()))
#define bit(n) (((i64)1)<<((i64)(n)))
#define all(v) (v).begin(), (v).end()
std::string dbgDelim(int &i){ return (i++ == 0 ? "" : ", "); }
#define dbgEmbrace(exp) { int i = 0; os << "{"; { exp; } os << "}"; return os; }
template <class T> std::ostream& operator<<(std::ostream &os, std::vector<T> v);
template <class T> std::ostream& operator<<(std::ostream &os, std::set<T> v);
template <class T> std::ostream& operator<<(std::ostream &os, std::queue<T> q);
template <class T> std::ostream& operator<<(std::ostream &os, std::priority_queue<T> q);
template <class T, class K> std::ostream& operator<<(std::ostream &os, std::pair<T, K> p);
template <class T, class K> std::ostream& operator<<(std::ostream &os, std::map<T, K> mp);
template <class T, class K> std::ostream& operator<<(std::ostream &os, std::unordered_map<T, K> mp);
template <int INDEX, class TUPLE> void dbgDeploy(std::ostream &os, TUPLE tuple){}
template <int INDEX, class TUPLE, class H, class ...Ts> void dbgDeploy(std::ostream &os, TUPLE t)
{ os << (INDEX == 0 ? "" : ", ") << get<INDEX>(t); dbgDeploy<INDEX + 1, TUPLE, Ts...>(os, t); }
template <class T, class K> void dbgDeploy(std::ostream &os, std::pair<T, K> p, std::string delim)
{ os << "(" << p.first << delim << p.second << ")"; }
template <class ...Ts> std::ostream& operator<<(std::ostream &os, std::tuple<Ts...> t)
{ os << "("; dbgDeploy<0, std::tuple<Ts...>, Ts...>(os, t); os << ")"; return os; }
template <class T, class K> std::ostream& operator<<(std::ostream &os, std::pair<T, K> p)
{ dbgDeploy(os, p, ", "); return os; }
template <class T> std::ostream& operator<<(std::ostream &os, std::vector<T> v)
{ dbgEmbrace( for(T t: v){ os << dbgDelim(i) << t; }); }
template <class T> std::ostream& operator<<(std::ostream &os, std::set<T> s)
{ dbgEmbrace( for(T t: s){ os << dbgDelim(i) << t; }); }
template <class T> std::ostream& operator<<(std::ostream &os, std::queue<T> q)
{ dbgEmbrace( for(; q.size(); q.pop()){ os << dbgDelim(i) << q.front(); }); }
template <class T> std::ostream& operator<<(std::ostream &os, std::priority_queue<T> q)
{ dbgEmbrace( for(; q.size(); q.pop()){ os << dbgDelim(i) << q.top(); }); }
template <class T, class K> std::ostream& operator<<(std::ostream &os, std::map<T, K> mp)
{ dbgEmbrace( for(auto p: mp){ os << dbgDelim(i); dbgDeploy(os, p, "->"); }); }
template <class T, class K> std::ostream& operator<<(std::ostream &os, std::unordered_map<T, K> mp)
{ dbgEmbrace( for(auto p: mp){ os << dbgDelim(i); dbgDeploy(os, p, "->"); }); }
#define DBG_OUT std::cerr
#define DBG_OVERLOAD(_1, _2, _3, _4, _5, _6, macro_name, ...) macro_name
#define DBG_LINE() { char s[99]; sprintf(s, "line:%3d | ", __LINE__); DBG_OUT << s; }
#define DBG_OUTPUT(v) { DBG_OUT << (#v) << "=" << (v); }
#define DBG1(v, ...) { DBG_OUTPUT(v); }
#define DBG2(v, ...) { DBG_OUTPUT(v); DBG_OUT << ", "; DBG1(__VA_ARGS__); }
#define DBG3(v, ...) { DBG_OUTPUT(v); DBG_OUT << ", "; DBG2(__VA_ARGS__); }
#define DBG4(v, ...) { DBG_OUTPUT(v); DBG_OUT << ", "; DBG3(__VA_ARGS__); }
#define DBG5(v, ...) { DBG_OUTPUT(v); DBG_OUT << ", "; DBG4(__VA_ARGS__); }
#define DBG6(v, ...) { DBG_OUTPUT(v); DBG_OUT << ", "; DBG5(__VA_ARGS__); }
#define DEBUG0() { DBG_LINE(); DBG_OUT << std::endl; }
#define DEBUG(...) \
{ \
DBG_LINE(); \
DBG_OVERLOAD(__VA_ARGS__, DBG6, DBG5, DBG4, DBG3, DBG2, DBG1)(__VA_ARGS__); \
DBG_OUT << std::endl; \
}
#include <bits/stdc++.h>
template <typename T> class Dijkstra
{
public:
Dijkstra<T>& addEdge(int from, int dest, T cost);
void update(int source);
T getDistance(int vertex);
~Dijkstra();
Dijkstra(int vertex_num);
private:
const int vertex_num;
T *distances;
class Edge
{
public:
int target;
T distance;
Edge(int target, T distance) : target(target), distance(distance) {}
};
std::vector<Edge> *edges;
class QueueElement
{
public:
T distance;
int vertex;
inline QueueElement(T distance, int vertex) : distance(distance), vertex(vertex){}
inline bool operator>(const QueueElement &e)const{ return distance > e.distance; }
};
};
template <typename T>
inline Dijkstra<T>::~Dijkstra()
{
delete [] edges;
delete [] distances;
}
template <typename T>
inline Dijkstra<T>::Dijkstra(int vertex_num) : vertex_num(vertex_num)
{
edges = new std::vector<Edge>[vertex_num];
distances = new T[vertex_num];
}
template <typename T>
inline T Dijkstra<T>::getDistance(int vertex)
{
return distances[vertex];
}
template <typename T>
inline void Dijkstra<T>::update(int source)
{
memset(distances, -1, sizeof(T) * vertex_num);
std::priority_queue<QueueElement, std::vector<QueueElement>, std::greater<QueueElement> > q;
distances[source] = 0;
q.push(QueueElement(0, source));
for(int total_size = 1; 0 < total_size;){
int vertex = q.top().vertex;
T distance = q.top().distance;
q.pop();
if(distances[vertex] < distance) continue;
--total_size;
for(Edge e : edges[vertex]){
int next_vertex = e.target;
T next_distance = e.distance + distance;
if(distances[next_vertex] == -1){
++total_size;
distances[next_vertex] = next_distance;
q.push(QueueElement(next_distance, next_vertex));
}else if(next_distance < distances[next_vertex]){
distances[next_vertex] = next_distance;
q.push(QueueElement(next_distance, next_vertex));
}
}
}
}
template <typename T>
inline Dijkstra<T>& Dijkstra<T>::addEdge(int from, int dest, T cost)
{
edges[from].push_back(Edge(dest, cost));
return *this;
}
int main()
{
i64 n, m, s, t;
cin >> n >> m >> s >> t;
Dijkstra<i64> dijkstra(n);
vector<vector<pair<pair<i64, i64>, pair<i64, i64>>>> edges(n);
rep(i, m){
i64 l;
cin >> l;
vector<i64> stations(l);
vector<i64> distances(l - 1);
vector<i64> distances_to_first(l);
vector<i64> distances_to_last(l);
rep(j, l) cin >> stations[j];
rep(j, l - 1) cin >> distances[j];
distances_to_first[0] = 0;
rep(j, l - 1) distances_to_first[j + 1] = distances_to_first[j] + distances[j];
distances_to_last[0] = distances_to_first[l - 1];
rep(j, l - 1) distances_to_last[j + 1] = distances_to_last[j] - distances[j];
assert(distances_to_last[l - 1] == 0);
rep(j, l - 1){
edges[stations[j + 0]].push_back(make_pair(make_pair(stations[j + 1], distances[j]), make_pair(stations[l - 1], distances_to_last [j + 0])));
edges[stations[j + 1]].push_back(make_pair(make_pair(stations[j + 0], distances[j]), make_pair(stations[0] , distances_to_first[j + 1])));
}
rep(j, l - 1){
dijkstra.addEdge(stations[j + 0], stations[j + 1], distances[j]);
dijkstra.addEdge(stations[j + 1], stations[j + 0], distances[j]);
}
}
dijkstra.update(t);
//rep(i, n) DEBUG(i, dijkstra.getDistance(i));
i64 low = 0, high = bit(30);
while(low + 1 < high){
i64 limit = (low + high) / 2;
bool ok = false;
typedef pair<i64, i64> e;
priority_queue<e, vector<e>, greater<e>> q;
q.push(make_pair((i64)0, s));
vector<i64> bests(n, bit(50));
bests[s] = 0;
while(sz(q)){
i64 dist = q.top().first;
i64 pos = q.top().second;
q.pop();
if(pos == t){
ok = true;
break;
}
if(bests[pos] < dist) continue;
for(auto &p: edges[pos]){
if(limit < dist + p.second.second + dijkstra.getDistance(p.second.first)) continue;
i64 next_pos = p.first.first;
i64 next_dist = dist + p.first.second;
if(bests[next_pos] <= next_dist) continue;
bests[next_pos] = next_dist;
q.push(make_pair(next_dist, next_pos));
}
}
if(ok) high = limit;
else low = limit;
}
cout << high << endl;
}
Submission Info
Submission Time |
|
Task |
C - メンテナンス明け |
User |
Komaki |
Language |
C++11 (GCC 4.9.2) |
Score |
100 |
Code Size |
8484 Byte |
Status |
AC |
Exec Time |
330 ms |
Memory |
9092 KB |
Judge Result
Set Name |
Subtask1 |
Subtask2 |
Score / Max Score |
50 / 50 |
50 / 50 |
Status |
|
|
Set Name |
Test Cases |
Subtask1 |
small/00_sample00, small/00_sample01, small/00_sample02, small/10_small-0000, small/10_small-0001, small/10_small-0002, small/10_small-0003, small/10_small-0004, small/10_small-0005, small/10_small-0006, small/10_small-0007, small/10_small-0008, small/10_small-0009, small/10_small-0010, small/10_small-0011, small/10_small-0012, small/10_small-0013, small/10_small-0014, small/10_small-0015, small/10_small-0016, small/10_small-0017, small/10_small-0018, small/10_small-0019, small/30_max_small, small/40_simple_0000, small/40_simple_0001, small/40_simple_0002, small/40_simple_0003, small/40_simple_0004, small/40_simple_0005, small/40_simple_0006, small/40_simple_0007, small/40_simple_0008, small/40_simple_0009, small/40_simple_0010, small/40_simple_0011, small/40_simple_0012, small/40_simple_0013, small/40_simple_0014, small/40_simple_0015, small/40_simple_0016, small/40_simple_0017, small/40_simple_0018, small/40_simple_0019, small/90_dijkstra_killer_00, small/90_dijkstra_killer_01, small/91_tayama_killer_00, small/91_tayama_killer_01, small/91_tayama_killer_02, small/91_tayama_killer_03, small/91_tayama_killer_04, small/91_tayama_killer_05 |
Subtask2 |
large/20_large-00, large/20_large-01, large/20_large-02, large/20_large-03, large/20_large-04, large/31_max_large |
Case Name |
Status |
Exec Time |
Memory |
large/20_large-00 |
AC |
175 ms |
8880 KB |
large/20_large-01 |
AC |
231 ms |
9092 KB |
large/20_large-02 |
AC |
170 ms |
9052 KB |
large/20_large-03 |
AC |
290 ms |
9024 KB |
large/20_large-04 |
AC |
330 ms |
9072 KB |
large/31_max_large |
AC |
68 ms |
5920 KB |
small/00_sample00 |
AC |
26 ms |
804 KB |
small/00_sample01 |
AC |
24 ms |
928 KB |
small/00_sample02 |
AC |
27 ms |
920 KB |
small/10_small-0000 |
AC |
25 ms |
920 KB |
small/10_small-0001 |
AC |
24 ms |
924 KB |
small/10_small-0002 |
AC |
25 ms |
924 KB |
small/10_small-0003 |
AC |
26 ms |
800 KB |
small/10_small-0004 |
AC |
26 ms |
924 KB |
small/10_small-0005 |
AC |
25 ms |
844 KB |
small/10_small-0006 |
AC |
27 ms |
928 KB |
small/10_small-0007 |
AC |
25 ms |
928 KB |
small/10_small-0008 |
AC |
24 ms |
924 KB |
small/10_small-0009 |
AC |
25 ms |
928 KB |
small/10_small-0010 |
AC |
26 ms |
804 KB |
small/10_small-0011 |
AC |
27 ms |
924 KB |
small/10_small-0012 |
AC |
27 ms |
920 KB |
small/10_small-0013 |
AC |
29 ms |
924 KB |
small/10_small-0014 |
AC |
26 ms |
924 KB |
small/10_small-0015 |
AC |
28 ms |
924 KB |
small/10_small-0016 |
AC |
27 ms |
916 KB |
small/10_small-0017 |
AC |
27 ms |
932 KB |
small/10_small-0018 |
AC |
26 ms |
924 KB |
small/10_small-0019 |
AC |
27 ms |
804 KB |
small/30_max_small |
AC |
27 ms |
796 KB |
small/40_simple_0000 |
AC |
25 ms |
800 KB |
small/40_simple_0001 |
AC |
25 ms |
792 KB |
small/40_simple_0002 |
AC |
27 ms |
920 KB |
small/40_simple_0003 |
AC |
27 ms |
800 KB |
small/40_simple_0004 |
AC |
25 ms |
912 KB |
small/40_simple_0005 |
AC |
26 ms |
920 KB |
small/40_simple_0006 |
AC |
27 ms |
924 KB |
small/40_simple_0007 |
AC |
25 ms |
800 KB |
small/40_simple_0008 |
AC |
27 ms |
800 KB |
small/40_simple_0009 |
AC |
27 ms |
916 KB |
small/40_simple_0010 |
AC |
26 ms |
804 KB |
small/40_simple_0011 |
AC |
26 ms |
792 KB |
small/40_simple_0012 |
AC |
26 ms |
704 KB |
small/40_simple_0013 |
AC |
26 ms |
840 KB |
small/40_simple_0014 |
AC |
27 ms |
924 KB |
small/40_simple_0015 |
AC |
26 ms |
920 KB |
small/40_simple_0016 |
AC |
25 ms |
920 KB |
small/40_simple_0017 |
AC |
25 ms |
924 KB |
small/40_simple_0018 |
AC |
26 ms |
800 KB |
small/40_simple_0019 |
AC |
26 ms |
800 KB |
small/90_dijkstra_killer_00 |
AC |
26 ms |
912 KB |
small/90_dijkstra_killer_01 |
AC |
26 ms |
808 KB |
small/91_tayama_killer_00 |
AC |
26 ms |
924 KB |
small/91_tayama_killer_01 |
AC |
27 ms |
920 KB |
small/91_tayama_killer_02 |
AC |
26 ms |
924 KB |
small/91_tayama_killer_03 |
AC |
27 ms |
916 KB |
small/91_tayama_killer_04 |
AC |
27 ms |
920 KB |
small/91_tayama_killer_05 |
AC |
27 ms |
920 KB |