Submission #381318

#	Time	Username	Problem	Language	Result	Execution time	Memory
381318		randomjohnnyh	Robot (JOI21_ho_t4)	C++14	0 / 100	358 ms	15724 KiB

Main

#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 = (ll)1e18 + 7;

void solve()
{

	int n, m;
	read(n, m);
	vector<vector<array<int,3> > > adj(n);
	map<pii, ll> totcost;
	range(m) {
		int a, b, c, p;
		read(a, b, c, p);
		a--; b--;
		adj[a].pb({b, c, p});
		totcost[{a, c}] += p;
		adj[b].pb({a, c, p});
		totcost[{b, c}] += p;
	}
	typedef pair<ll, pii> point;
	map<pii, ll> dist;
	priority_queue<point, vector<point>, greater<point> > pq;
	auto getColor = [&](int b, int c) -> ll& {
		return dist.insert({{b, c}, inf}).first->second;
	};
	pq.push({0, {0, 0}});
	vi freq(n);
	while (not pq.empty()) {
		auto [d, cur] = pq.top(); pq.pop();
		if (d != dist[cur]) continue;
		auto [a, prevc] = cur;
		print(a, prevc, d);
		if (a == n-1) {
			print(d);
			return;
		}
		if (++freq[a] >= 2) continue;
		for (auto [b, c, p] : adj[a]) {
			if (prevc != c) {
				// use c outgoing
				ll ndist = d + totcost[{a, c}] - p;
				ll &bdist = getColor(b, c);
				if (setmin(bdist, ndist)) {
					pq.push({ndist, {b, c}});
				}
			}
			{
				// change c outgoing
				ll ndist = d + p;
				ll &bdist = getColor(b, 0);
				if (setmin(bdist, ndist)) {
					pq.push({ndist, {b, 0}});
				}
			}
		}
	}
	print(-1);
}

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 (stderr)

Main.cpp: In function 'void solve()':
Main.cpp:118:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  118 |   auto [d, cur] = pq.top(); pq.pop();
      |        ^
Main.cpp:120:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  120 |   auto [a, prevc] = cur;
      |        ^
Main.cpp:127:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  127 |   for (auto [b, c, p] : adj[a]) {
      |             ^

• Subtask 1: 0 / 34
• Subtask 2: 0 / 24
• Subtask 3: 0 / 42