Submission #380338

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
380338	2021-03-21T04:33:03 Z	randomjohnnyh	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	452 ms	17276 KB

commuter_pass

#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <queue>
#include <numeric>
#include <functional>
#include <array>
#include <sstream>
#include <random>
using namespace std;

#define range1(n) for (int __i = 0, __n = int(n); __i < __n; ++__i)
#define range2(i, n) for (int i = 0, __n = int(n); i < __n; ++i)
#define range3(i, a, b) for (int i = int(a), __b = int(b); i < __b; ++i)
#define range4(i, a, b, c) for (int i = int(a), __b = int(b); (c > 0) ? (i < __b) : (i > __b); i += c)
#define GET_MACRO(_1,_2,_3,_4,NAME,...) NAME
#define range(...) GET_MACRO(__VA_ARGS__, range4, range3, range2, range1)(__VA_ARGS__)
#define each2(a, v) for (auto&& a : v)
#define each3(a, b, v) for (auto&& [a, b] : v)
#define each4(a, b, c, v) for (auto&& [a, b, c] : v)
#define each(...) GET_MACRO(__VA_ARGS__, each4, each3, each2, each1)(__VA_ARGS__)
#define iterate(i, a, v) for (auto [it, __end, i] = std::tuple{begin(v), end(v), 0}; it != __end; it++, i++) if (auto&& a = *it; true)
#define len(v) ((int)(v).size())
#define pb push_back
#define all(v) begin(v), end(v)
#define getindex(f,v,...) int(f(all(v),##__VA_ARGS__) - begin(v))
#define endl '\n';
#ifdef DEBUG
#define dprint(a) print(a)
#else
#define dprint(a)
#endif


template <typename U, typename T1, typename T2>
U& operator>>(U& is, std::pair<T1, T2>& p) { return is >> p.first >> p.second; }
template <typename U, typename T, typename enable_if<!is_same<T,string>::value>::type* = nullptr>
U& operator>>(U& is, T& a) { for (auto&& e : a) { is >> e; } return is; }
template <typename U, typename T1, typename T2>
U& operator<<(U& os, const std::pair<T1, T2>& p) { return os << p.first << " " << p.second; }
template <typename U, typename T, typename enable_if<!is_same<T,string>::value>::type* = nullptr>
U& operator<<(U& os, const T& a) { bool f = true; for (auto&& e : a) { if (f) f = false; else os << " "; os << e; } return os; }
template<typename T> void read(T& value) { cin >> value; }
template<typename T, typename... Args> void read(T& value, Args&&... args) { cin >> value; read(forward<Args>(args)...); }
void print() { cout << endl; }
template<typename T, typename... Args> void print(const T& value) { cout << value; print(); }
template<typename T, typename... Args> void print(const T& value, Args&&... args) { cout << value << " "; print(forward<Args>(args)...); }
template <typename T> bool setmin(T& a, const T& b) { if (b < a) {a = b; return true;} return false; }
template <typename T> bool setmax(T& a, const T& b) { if (b > a) {a = b; return true;} return false; }
template <typename T> T gcd(T a, T b) { return b == 0 ? a : gcd(b, a % b); }
template <typename T> int sign(T a) { return a < 0 ? -1 : (a > 0 ? 1 : 0); }
template <typename T> T square(T a) { return a * a; }
template <typename T> void sortunique(T& v) { sort(all(v)); v.erase(unique(all(v)), v.end()); }
template <typename T, typename U=typename T::value_type, typename O=less<U>> vector<int> argsort(const T& v, const O& op = O()) { vector<int> w(len(v)); iota(all(w), 0); sort(all(w), [&](int a, int b) {return v[a] != v[b] ? op(v[a], v[b]) : a < b;}); return w; }
vector<int> invert(const vector<int>& v) { vector<int> w(len(v)); range(i, len(v)) { w[v[i]] = i; } return w; }
template <typename T, typename U=typename T::value_type, typename O=plus<U>> vector<U> prefixes(const T& v, const O& op = O()) { vector<U> sums(len(v)+1); partial_sum(all(v), ++sums.begin(), op); return sums; }
template <typename T, typename U=typename T::value_type> map<U, int> counter(const T& v) { map<U, int> f; for (auto&& e : v) { f[e]++; }; return f; }
template <typename T, typename U=typename T::value_type, typename O=equal_to<U>> vector<pair<U, int> > groupby(const T& v, const O& op = O()) {vector<pair<U, int> > w; for(auto&& a : v) {if (not w.empty() and op(a, w.back().first)) {w.back().second++; } else {w.emplace_back(a, 1); } } return w; }
template <typename Key, typename Value> const Value& getdefault(const map<Key, Value>& m, const Key& key, const Value& default_value) { auto it = m.find(key); if (it == m.end()) {return default_value; } return it->second; }
template <typename Key, typename Value> Value& getdefault(map<Key, Value>& m, const Key& key, Value& default_value) { auto it = m.find(key); if (it == m.end()) {return default_value; } return it->second; }
string OK(bool a) { return a ? "YES" : "NO"; }
string Ok(bool a) { return a ? "Yes" : "No"; }

template<class Fun>
class y_combinator_result {
  Fun fun_;
public:
  template<class T>
  explicit y_combinator_result(T &&fun): fun_(std::forward<T>(fun)) {}

  template<class ...Args>
  decltype(auto) operator()(Args &&...args) {
    return fun_(std::ref(*this), std::forward<Args>(args)...);
  }
};

template<class Fun> decltype(auto) y_combinator(Fun &&fun) { return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun)); }

typedef vector<int> vi;
typedef long long ll;
typedef pair<int,int> pii;

const double pi = acos(-1.0);
constexpr ll inf = (int)1e9 + 7;

void solve()
{
	int n, m;
	read(n, m);
	vector<vector<pii> > adj(n);
	int s, t;
	read(s, t);
	s--; t--;
	int u, v;
	read(u, v);
	u--; v--;
	range(m) {
		int a, b, c;
		read(a, b, c);
		a--; b--;
		adj[a].pb({b, c});
		adj[b].pb({a, c});
	}
	auto dijkstra = [&](vector<vector<pii> >& g, int a) {
		typedef pair<ll,int> point;
		vector<ll> dist(n, inf * inf);
		priority_queue<point, vector<point>, greater<point> > pq;
		dist[a] = 0;
		pq.push({0ll, a});
		while (not pq.empty()) {
			auto [d, cur] = pq.top(); pq.pop();
			if (d != dist[cur]) continue;
			for (auto [nxt, w] : g[cur]) {
				if (setmin(dist[nxt], d + w)) {
					pq.push({dist[nxt], nxt});
				}
			}
		}
		return dist;
	};
	auto distS = dijkstra(adj, s);
	auto distT = dijkstra(adj, t);
	auto distU = dijkstra(adj, u);
	auto distV = dijkstra(adj, v);
	ll totDist = distS[t];
	ll ans = inf * inf;
	{
		auto ordS = argsort(distS);
		auto dp = distU;
		each(a, ordS) {
			for (auto&& [b, w] : adj[a]) {
				if (distS[a] + w + distT[b] == totDist) {
					setmin(dp[b], dp[a]);
				}
			}
		}
		range(i, n) {
			setmin(ans, distV[i] + dp[i]);
		}
	}
	{
		auto ordT = argsort(distT);
		auto dp = distU;
		each(a, ordT) {
			for (auto&& [b, w] : adj[a]) {
				if (distT[a] + w + distS[b] == totDist) {
					setmin(dp[b], dp[a]);
				}
			}
		}
		range(i, n) {
			setmin(ans, distV[i] + dp[i]);
		}
	}
	print(ans);
}

void go()
{
	int testn = 1;
	// read(testn);
	for (int testi = 1; testi <= testn; testi++)
	{
		solve();
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout << fixed << setprecision(10);
	cout << setfill('0');
	go();
}

Compilation message

commuter_pass.cpp: In lambda function:
commuter_pass.cpp:118:9: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  118 |    auto [d, cur] = pq.top(); pq.pop();
      |         ^
commuter_pass.cpp:120:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  120 |    for (auto [nxt, w] : g[cur]) {
      |              ^
commuter_pass.cpp: In function 'void solve()':
commuter_pass.cpp:138:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  138 |    for (auto&& [b, w] : adj[a]) {
      |                ^
commuter_pass.cpp:152:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  152 |    for (auto&& [b, w] : adj[a]) {
      |                ^

Subtask #1

16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	417 ms	15304 KB	Output is correct
2	Correct	372 ms	14424 KB	Output is correct
3	Correct	452 ms	13832 KB	Output is correct
4	Correct	364 ms	15268 KB	Output is correct
5	Correct	374 ms	13976 KB	Output is correct
6	Correct	448 ms	15284 KB	Output is correct
7	Correct	388 ms	13856 KB	Output is correct
8	Correct	390 ms	14036 KB	Output is correct
9	Correct	373 ms	13928 KB	Output is correct
10	Correct	328 ms	13784 KB	Output is correct
11	Correct	184 ms	10092 KB	Output is correct
12	Correct	438 ms	13828 KB	Output is correct

Subtask #2

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	403 ms	14036 KB	Output is correct
2	Correct	408 ms	14148 KB	Output is correct
3	Correct	418 ms	14096 KB	Output is correct
4	Correct	397 ms	14200 KB	Output is correct
5	Correct	399 ms	14032 KB	Output is correct
6	Correct	396 ms	13880 KB	Output is correct
7	Correct	414 ms	13904 KB	Output is correct
8	Correct	425 ms	14184 KB	Output is correct
9	Correct	397 ms	13912 KB	Output is correct
10	Correct	412 ms	14028 KB	Output is correct
11	Correct	208 ms	10196 KB	Output is correct
12	Correct	401 ms	13864 KB	Output is correct

Subtask #3

24.0 / 24.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	9 ms	1132 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	18 ms	1772 KB	Output is correct
5	Correct	8 ms	1004 KB	Output is correct
6	Correct	1 ms	364 KB	Output is correct
7	Correct	2 ms	492 KB	Output is correct
8	Correct	2 ms	492 KB	Output is correct
9	Correct	1 ms	492 KB	Output is correct
10	Correct	8 ms	1388 KB	Output is correct
11	Correct	1 ms	364 KB	Output is correct
12	Correct	1 ms	364 KB	Output is correct
13	Correct	1 ms	364 KB	Output is correct
14	Correct	2 ms	364 KB	Output is correct
15	Correct	2 ms	364 KB	Output is correct

Subtask #4

45.0 / 45.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	417 ms	15304 KB	Output is correct
2	Correct	372 ms	14424 KB	Output is correct
3	Correct	452 ms	13832 KB	Output is correct
4	Correct	364 ms	15268 KB	Output is correct
5	Correct	374 ms	13976 KB	Output is correct
6	Correct	448 ms	15284 KB	Output is correct
7	Correct	388 ms	13856 KB	Output is correct
8	Correct	390 ms	14036 KB	Output is correct
9	Correct	373 ms	13928 KB	Output is correct
10	Correct	328 ms	13784 KB	Output is correct
11	Correct	184 ms	10092 KB	Output is correct
12	Correct	438 ms	13828 KB	Output is correct
13	Correct	403 ms	14036 KB	Output is correct
14	Correct	408 ms	14148 KB	Output is correct
15	Correct	418 ms	14096 KB	Output is correct
16	Correct	397 ms	14200 KB	Output is correct
17	Correct	399 ms	14032 KB	Output is correct
18	Correct	396 ms	13880 KB	Output is correct
19	Correct	414 ms	13904 KB	Output is correct
20	Correct	425 ms	14184 KB	Output is correct
21	Correct	397 ms	13912 KB	Output is correct
22	Correct	412 ms	14028 KB	Output is correct
23	Correct	208 ms	10196 KB	Output is correct
24	Correct	401 ms	13864 KB	Output is correct
25	Correct	9 ms	1132 KB	Output is correct
26	Correct	1 ms	364 KB	Output is correct
27	Correct	1 ms	364 KB	Output is correct
28	Correct	18 ms	1772 KB	Output is correct
29	Correct	8 ms	1004 KB	Output is correct
30	Correct	1 ms	364 KB	Output is correct
31	Correct	2 ms	492 KB	Output is correct
32	Correct	2 ms	492 KB	Output is correct
33	Correct	1 ms	492 KB	Output is correct
34	Correct	8 ms	1388 KB	Output is correct
35	Correct	1 ms	364 KB	Output is correct
36	Correct	1 ms	364 KB	Output is correct
37	Correct	1 ms	364 KB	Output is correct
38	Correct	2 ms	364 KB	Output is correct
39	Correct	2 ms	364 KB	Output is correct
40	Correct	370 ms	17276 KB	Output is correct
41	Correct	405 ms	16016 KB	Output is correct
42	Correct	409 ms	15980 KB	Output is correct
43	Correct	182 ms	12012 KB	Output is correct
44	Correct	211 ms	12116 KB	Output is correct
45	Correct	366 ms	15144 KB	Output is correct
46	Correct	395 ms	15776 KB	Output is correct
47	Correct	368 ms	17172 KB	Output is correct
48	Correct	186 ms	11756 KB	Output is correct
49	Correct	318 ms	17152 KB	Output is correct
50	Correct	372 ms	15612 KB	Output is correct
51	Correct	350 ms	15172 KB	Output is correct