Submission #638689

#	Time	Username	Problem	Language	Result	Execution time	Memory
638689		KYoA_A	Robot (JOI21_ho_t4)	C++17	0 / 100	3114 ms	1051060 KiB

Main

/*---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---*/

#include "bits/stdc++.h"
using namespace std;

#ifdef LOCAL
#include "algo/debug.h"
#else
#define dbg(x...)
#endif

#define rep(i, a, b)	for(int i = a; i < (b); ++i)
#define rrep(a, b, c)	for(int a = (b); a > c; --a)
#define each(a, b)	for(auto& a : b)

#define sz(x)       (int)(x).size()
#define all(a)      (a).begin(),(a).end()
#define rall(a)     (a).rbegin(), (a).rend()

#define vi vector<int>
#define ar array

template<class T> using V = vector<T>;
template<class T> using pq = priority_queue<T>;
template<class T> using pqg = priority_queue<T, vector<T>, greater<T>>;

#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define eb emplace_back
#define rsz resize
#define bk back()

#define pi pair<int, int>
#define pl pair<ll, ll>
#define mp make_pair
#define f first
#define s second

#define pct(x) __builtin_popcount(x)
constexpr int fsb(int x) {return __builtin_ffs(x) - 1;} // first set bit
constexpr int log2(int x) {return x == 0 ? 0 : 31-__builtin_clz(x);} // floor(log2(x))
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());

template <class T> bool umin(T& a, const T& b){return b<a?a=b, 1:0;}
template <class T> bool umax(T& a, const T& b){return a<b?a=b, 1:0;}

const int d4i[4]={-1, 0, 1, 0}, d4j[4]={0, 1, 0, -1};
const int d8i[8]={-1, -1, 0, 1, 1, 1, 0, -1}, d8j[8]={0, 1, 1, 1, 0, -1, -1, -1};

using ll = long long;
using ld = long double;
using str = string;

const int inf = (int)1e9 + 5;
const ll infl = (ll)1e18 + 5;
const ld PI = acos((ld)-1);
const int MOD = 1e9 + 7;
const int N = 2e5 + 10;

/*---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---*/


// 2022-09-06 19:59
void solve(){
	int n, m; cin >> n >> m;

	V<ar<int, 4>> eg(m);
	V<map<int, vi>> g(n);
	V<map<int, multiset<int>>> M(n);

	rep(i, 0, m){
		int u, v, c, z; cin >> u >> v >> c >> z;
		--u; --v;
		eg[i] = {u, v, c, z};

		for(int x : {u, v}){
			auto &s = M[x][c];
			s.emplace(z);
			g[x][c].eb(i);
		}
	}

	pqg <ar<ll, 4>> pq;
	V<map<int, ll>> md(n);
	pq.push({md[0][0] = 0, 0, 0, 0});

	while(!pq.empty()){
		auto [cd, x, cx, ecc] = pq.top(); pq.pop();
		if(md[x][cx] != cd) continue;

		if(x == n-1){
			cout << cd << '\n';
			return;
		}

		if(cx){
			auto it = md[x].find(0);
			if(it == md[x].end() || umin(md[x][0], cd)){
				pq.push({md[x][0] = cd, x, 0});
			}

			auto &s = M[x][cx];
			s.erase(ecc);

			each(e, g[x][cx]){
				auto [u, v, c, z] = eg[e];
				int y = x^u^v;

				int ec = (sz(s) <= 2 ? (sz(s) == 2 ? *s.begin() : 0) : z);
				int mc = ((sz(s) > 2 || (sz(s) == 2 && *s.begin() == z)) ? c : 0);
				auto it = md[y].find(mc);
				if(it == md[y].end() || umin(md[y][mc], cd + ec)){
					pq.push({md[y][mc] = cd + ec, y, mc, z});
				}
			}

			s.emplace(ecc);
			continue;
		}

		each(cc, g[x]){

			auto &s = M[x][cc.f];
			ll tot = accumulate(all(s), 0);

			each(e, cc.s){
				auto [u, v, c, z] = eg[e];
				int y = x^u^v;


				ll ec = (sz(s) <= 2 ? (sz(s) == 2 ? *s.begin() : 0) : z);
				umin(ec, tot - z);
				int mc = ((sz(s) > 2 || (sz(s) == 2 && *s.begin() == z)) ? c : 0);
				auto it = md[y].find(mc);
				if(it == md[y].end() || umin(md[y][mc], cd + ec)){
					pq.push({md[y][mc] = cd + ec, y, mc, z});
				}
			}
		}
	}
	cout << -1 << '\n';
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
		solve();
}

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