Submission #1152704

#	Time	Username	Problem	Language	Result	Execution time	Memory
1152704		dubabuba	Robot (JOI21_ho_t4)	C++20	0 / 100	3117 ms	2130508 KiB

Main

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

#define int long long

typedef pair<int, int> pii;
#define ff first
#define ss second
#define MP make_pair

const int sus = 1.1e5;
const int mxn = 2.2e5;
int a[mxn], b[mxn], c[mxn], p[mxn];
vector<pii> adj[mxn];
vector<pair<int, pii>> go[mxn];
int n, m, dis[mxn];

int32_t main() {
	cin >> n >> m;
	for(int i = 0; i < m; i++) {
		cin >> a[i] >> b[i] >> c[i] >> p[i];
		adj[a[i]].push_back(MP(i, 0));
		adj[b[i]].push_back(MP(i, 0));
	}

	for(int i = 1; i <= n; i++) {
		if(adj[i].size() == 0) continue;

		sort(adj[i].begin(), adj[i].end(), [&] (pii pi, pii pj) {
			return c[pi.ff] < c[pj.ff];
		});

		for(pii e : adj[i]) {
			int id = e.ff;
			int j = a[id] + b[id] - i;
		}

		int L = 0;
		int col = c[adj[i][0].ff];
		int cost = p[adj[i][0].ff];

		vector<pair<int, pii>> vec;
		for(int R = 1; R < adj[i].size(); R++) {
			int id = adj[i][R].ff;
			if(col == c[id]) {
				cost += p[id];
			}
			else {
				vec.push_back(MP(cost, MP(L, R - 1)));
				L = R;
				col = c[id];
				cost = p[id];
			}
		}

		vec.push_back(MP(cost, MP(L, adj[i].size() - 1)));

		for(pair<int, pii> e : vec) {
			int cost = e.ff;
			int l = e.ss.ff;
			int r = e.ss.ss;

			for(int t = l; t <= r; t++) {
				int id = adj[i][t].ff;
				int rest = cost - p[id];

				int j = a[id] + b[id] - i;
				go[i].push_back(MP( j, MP(rest, c[id]) ));
				go[i].push_back(MP( j + sus, MP(p[id], c[id]) ));
			}
		}
	}

	priority_queue<pair<pii, pii>> pq;
	pq.push(MP(MP(0, 0), MP(1, -1)));
	memset(dis, -1, sizeof dis);
	set<pair<int, pii>> mp;

	while(pq.size()) {
		int d = -pq.top().ff.ff;
		int las = pq.top().ff.ss;
		int cur = pq.top().ss.ff;
		int col = pq.top().ss.ss;
		pq.pop();

		int u = (cur > sus) ? cur - sus : cur;
		bool change = (cur > sus);

		if(u == n) {
			cout << d << endl;
			return 0;
		}

		if(dis[cur] > -1) {
			if(dis[cur] > d + 1)
				continue;
			if(dis[cur] == d)
				continue;
		}
		else {
			dis[cur] = d;
		}

		// cout << cur << ' ' << d << endl;

		// auto it = mp.find(MP(cur, MP(col, las)));
		// if(mp.end() != it) continue;
		// mp.insert(MP(cur, MP(col, las)));

		// cout << "\nnow: " << cur << " = " << d << endl;

		for(pair<int, pii> e : go[u]) {
			int v = e.ff;
			int w = e.ss.ff;
			int c = e.ss.ss;

			int cost = d + w;
			if(col == c && change && v < sus)
				cost -= las;

			// cout << cur << " -> " << v << " = " << cost << endl;
			pq.push(MP(MP(-cost, w), MP(v, c)));
		}
	}

	cout << -1 << endl;
	return 0;
}

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