제출 #543796

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
543796		Asymmetry	Robot (JOI21_ho_t4)	C++17	0 / 100	3058 ms	81912 KiB

Main

//Autor: Bartłomiej Czarkowski
#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
template<class A,class B>auto&operator<<(ostream&o,pair<A,B>p){return o<<'('<<p.first<<", "<<p.second<<')';}
template<class T>auto operator<<(ostream&o,T x)->decltype(x.end(),o){o<<'{';int i=0;for(auto e:x)o<<(", ")+2*!i++<<e;return o<<'}';}
#define debug(x...) cerr<<"["#x"]: ",[](auto...$){((cerr<<$<<"; "),...);}(x),cerr<<'\n'
#else
#define debug(...) {}
#endif

const int N = 101000;
const int M = 401000;
int n, m, a, b, c, p, l;
int kr[M];
int cost[M];
int color[M];
int odw[N]; // czy odwiedziliśmy nie zmieniając krawędzi
int wyp[N]; // czy już wypychaliśmy ze zmianą krawędzi
int wy[N]; // czy wypychaliśmy bez zmiany krawędzi sami nie zmieniając wcześniej
vector<int> v[N];
map<int, vector<int>> mp[N];
map<int, long long> sm[N];
long long odl[M][2]; // którą krawędzią przyszliśmy | czy zmieniliśmy jej kolor
priority_queue<pair<long long, pair<int, int>>> pq;

long long sum(int x, int y) {
	if (!sm[x].count(y)) {
		long long w = 0;
		for (int i : mp[x][y]) {
			w += cost[i];
		}
		sm[x][y] = w;
	}
	return sm[x][y];
}

int main() {
	l = 1;
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= m; ++i) {
		scanf("%d%d%d%d", &a, &b, &c, &p);
		++l;
		kr[l] = b;
		cost[l] = p;
		color[l] = c;
		v[a].push_back(l);
		mp[a][c].push_back(l);
		odl[l][0] = 1e18;
		odl[l][1] = 1e18;
		++l;
		kr[l] = a;
		cost[l] = p;
		color[l] = c;
		v[b].push_back(l);
		mp[b][c].push_back(l);
		odl[l][0] = 1e18;
		odl[l][1] = 1e18;
	}
	kr[0] = 1;
	pq.push({0, {0, 0}});
	while (!pq.empty()) {
		long long w = -pq.top().first;
		int x = pq.top().second.first;
		int y = pq.top().second.second;
		pq.pop();
		
		debug(w, x, y, kr[x]);
		// wypchnięcie bez zmiany krawędzi jeśli my zmieniliśmy
		if (y == 2) {
			if (odl[x][y] != w) { // już wypchnięto
				continue;
			}
			int g = 0;
			for (int i : mp[kr[x]][color[x]]) {
				if ((x ^ 1) != i) {
					g = max(g, cost[i]);
				}
			}
			w += g;
			debug(2, mp[kr[x]][color[x]]);
			for (int i : mp[kr[x]][color[x]]) {
				if (odl[i][0] > w - cost[i]) {
					odl[i][0] = w - cost[i];
					pq.push({-odl[i][0], {i, 0}});
				}
			}
			continue;
		}
		
		// podstawowa obsługa
		if (kr[x] == n) {
			printf("%lld\n", odl[x][y]);
			return 0;
		}
		if (odl[x][y] != w || (y == 0 && odw[kr[x]])) {
			continue;
		}
		if (y == 0) {
			odw[kr[x]] = 1;
		}
		
		// wypchnięcie z zmianą krawędzi
		if (!wyp[kr[x]]) { // czy już wypychaliśmy
			wyp[kr[x]] = 1;
			debug(1, v[kr[x]]);
			for (int i : v[kr[x]]) {
				if (odl[i][1] > w + cost[i]) {
					odl[i][1] = w + cost[i];
					pq.push({-odl[i][1], {i, 1}});
				}
			}
		}
		
		// nie korzystamy z tego że zmieniliśmy nawet jeśli zmieniliśmy
		// wypchnięcie bez zmiany krawędzi jeśli sami nie zmieniliśmy
		if (!wy[kr[x]]) {
			wy[kr[x]] = 1;
			for (auto i : mp[kr[x]]) {
				debug(3, i);
				long long s = sum(kr[x], i.first);
				for (int j : i.second) {
					if (odl[j][0] > w + s - cost[j]) {
						odl[j][0] = w + s - cost[j];
						pq.push({-odl[j][0], {j, 0}});
					}
				}
			}
		}
		// przygotowanie do wypchnięcia bez zmiany krawędzi jeśli my zmieniliśmy
		if (y == 1 && (int)mp[kr[x]][color[x]].size() > 1) {
			long long s = sum(kr[x], color[x]);
			int g = 0;
			for (int i : mp[kr[x]][color[x]]) {
				if ((x ^ 1) != i) {
					g = max(g, cost[i]);
				}
			}
			if (odl[x][2] > w + s - cost[x] - g) {
				odl[x][2] = w + s - cost[x] - g;
				pq.push({-odl[x][2], {x, 2}});
			}
			debug("prep", w + s - cost[x] - g);
		}
	}
	printf("-1\n");
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

Main.cpp: In function 'int main()':
Main.cpp:40:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |  scanf("%d%d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~
Main.cpp:42:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |   scanf("%d%d%d%d", &a, &b, &c, &p);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:139:16: warning: array subscript 2 is above array bounds of 'long long int [2]' [-Warray-bounds]
  139 |    if (odl[x][2] > w + s - cost[x] - g) {
      |        ~~~~~~~~^
Main.cpp:140:13: warning: array subscript 2 is above array bounds of 'long long int [2]' [-Warray-bounds]
  140 |     odl[x][2] = w + s - cost[x] - g;
      |     ~~~~~~~~^
Main.cpp:71:16: warning: array subscript 2 is above array bounds of 'long long int [2]' [-Warray-bounds]
   71 |    if (odl[x][y] != w) { // już wypchnięto
      |        ~~~~~~~~^

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