Submission #686548

#	Time	Username	Problem	Language	Result	Execution time	Memory
686548		ethening	Robot (JOI21_ho_t4)	C++17	100 / 100	759 ms	155880 KiB

Main

#include "bits/stdc++.h"
#include <queue>
#include <unordered_map>
using namespace std;
using ll = long long;
 
#define DEBUG 0
 
const ll INF = 1000'000'000'000'000'000ll;
 
const int MAXN = 100000;
const int MAXM = 200000;
 
int n, m;
 
unordered_map<int, int> s[MAXN + 5];
unordered_map<int, ll> csum[MAXN + 5];
 
int a[MAXM + 5][4];
 
struct edge {
	int fr;
	int to;
	ll weight;
} e[10 * MAXM + 5];
 
vector<int> v[10 * MAXM + 5];
 
int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> n >> m;
	int cnt = 0;
	
	s[1][0] = ++cnt;
	s[n][0] = ++cnt;

	int ecnt = 0;
 
	for (int i = 1; i <= m; i++) {
		cin >> a[i][0] >> a[i][1] >> a[i][2] >> a[i][3];
		if (s[a[i][0]].find(0) == s[a[i][0]].end()) {
			s[a[i][0]][0] = ++cnt;
		}
		if (s[a[i][0]].find(a[i][2]) == s[a[i][0]].end()) {
			s[a[i][0]][a[i][2]] = ++cnt;
			e[++ecnt] = {.fr = s[a[i][0]][0], .to = cnt, .weight = 0};
			v[s[a[i][0]][0]].push_back(ecnt);
		}
		if (csum[a[i][0]].find(a[i][2]) == csum[a[i][0]].end()) {
			csum[a[i][0]][a[i][2]] = a[i][3];
		}
		else csum[a[i][0]][a[i][2]] += a[i][3];
		if (s[a[i][1]].find(0) == s[a[i][1]].end()) {
			s[a[i][1]][0] = ++cnt;
		}
		if (s[a[i][1]].find(a[i][2]) == s[a[i][1]].end()) {
			s[a[i][1]][a[i][2]] = ++cnt;
			e[++ecnt] = {.fr = s[a[i][1]][0], .to = cnt, .weight = 0};
			v[s[a[i][1]][0]].push_back(ecnt);
		}
		if (csum[a[i][1]].find(a[i][2]) == csum[a[i][1]].end()) {
			csum[a[i][1]][a[i][2]] = a[i][3];
		}
		else csum[a[i][1]][a[i][2]] += a[i][3];
	}
 
	if (DEBUG) {
		for (int i = 1; i <= n; i++) {
			for (auto [dex, val] : s[i]) {
				cout << "i: " << i << " col: " << dex << " index: " << val << endl;
			}
		}
	}
 
	for (int i = 1; i <= m; i++) {
		int col = a[i][2];
		int fr = a[i][0];
		int to = a[i][1];
		int node10 = s[fr][0];
		int node1c = s[fr][col];
		int node20 = s[to][0];
		int node2c = s[to][col];
 
		e[++ecnt] = {.fr = node10, .to = node20, .weight = (ll)a[i][3]};
		v[node10].push_back(ecnt);
		e[++ecnt] = {.fr = node20, .to = node10, .weight = (ll)a[i][3]};
		v[node20].push_back(ecnt);
		
		e[++ecnt] = {.fr = node10, .to = node2c, .weight = 0};
		v[node10].push_back(ecnt);
		e[++ecnt] = {.fr = node20, .to = node1c, .weight = 0};
		v[node20].push_back(ecnt);
 
		e[++ecnt] = {.fr = node1c, .to = node20, .weight = csum[fr][col] - a[i][3]};
		v[node1c].push_back(ecnt);
		e[++ecnt] = {.fr = node2c, .to = node10, .weight = csum[to][col] - a[i][3]};
		v[node2c].push_back(ecnt);
		if (DEBUG) cout << ecnt << endl;
	}
 
	if (DEBUG) {
		for (int i = 1; i <= ecnt; i++) {
			cout << "fr: " << e[i].fr << " to: " << e[i].to << " we: " << e[i].weight << endl;
		}
	}
 
	// cout << "!!!" << cnt << " " << ecnt << endl;

	int source = s[1][0];
	int dest = s[n][0];
	vector<ll> dist(cnt + 5, INF);
	typedef pair<ll, int> pli;
	priority_queue<pli, vector<pli>, greater<pli>> Q;
	dist[source] = 0;
	Q.push({0, source});
	while (!Q.empty()) {
		auto [curDist, cur] = Q.top();
		Q.pop();
		if (dist[cur] < curDist) continue;
		if (cur == dest) break;
		for (auto eg: v[cur]) {
			if (dist[cur] + e[eg].weight < dist[e[eg].to]) {
				dist[e[eg].to] = dist[cur] + e[eg].weight;
				Q.push({dist[e[eg].to], e[eg].to});
			}
		}
	}
	if (DEBUG) {
		for (int i = 1; i <= cnt; i++) {
			cout << "dist " << i << " : " << dist[i] << endl;
		}
	}
 
	if (DEBUG) {
		cout << "DEST: " << dest << endl;
	}
 
	if (dist[dest] == INF) dist[dest] = -1;
	cout << dist[dest] << "\n";
}

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