Submission #831710

#	Time	Username	Problem	Language	Result	Execution time	Memory
831710		green_gold_dog	Robot (JOI21_ho_t4)	C++17	100 / 100	546 ms	79896 KiB

Main

//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,sse,sse2,sse3,ssse3,sse4,abm,popcnt,mmx")
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef double db;
typedef long double ldb;
typedef complex<double> cd;

constexpr ll INF64 = 9000000000000000000, INF32 = 2000000000, MOD = 1000000007;
constexpr db PI = acos(-1);
constexpr bool IS_FILE = false, IS_TEST_CASES = false;

random_device rd;
mt19937 rnd32(rd());
mt19937_64 rnd64(rd());

template<typename T>
bool assign_max(T& a, T b) {
	if (b > a) {
		a = b;
		return true;
	}
	return false;
}

template<typename T>
bool assign_min(T& a, T b) {
	if (b < a) {
		a = b;
		return true;
	}
	return false;
}

template<typename T>
T square(T a) {
	return a * a;
}

template<>
struct std::hash<pair<ll, ll>> {
	ll operator() (pair<ll, ll> p) {
		return ((__int128)p.first * MOD + p.second) % INF64;
	}
};

void solve() {
	ll n, m;
	cin >> n >> m;
	vector<ll> nc(m, 0);
	vector<vector<tuple<ll, ll, ll>>> go(n);
	bool f = true;
	for (ll i = 0; i < m; i++) {
		ll a, b, c, p;
		cin >> a >> b >> c >> p;
		a--;
		b--;
		c--;
		if (p != 1) {
			f = false;
		}
		go[a].emplace_back(b, c, p);
		go[b].emplace_back(a, c, p);
	}
	if (true) {
		vector<map<ll, vector<pair<ll, ll>>>> g(n);
		vector<map<ll, ll>> sum(n);
		for (ll i = 0; i < n; i++) {
			for (auto[b, c, p] : go[i]) {
				g[i][c].push_back(make_pair(p, b));
				sum[i][c] += p;
			}
		}
		for (ll i = 0; i < n; i++) {
			for (auto&[c, _] : g[i]) {
				sort(g[i][c].begin(), g[i][c].end());
				reverse(g[i][c].begin(), g[i][c].end());
			}
		}
		vector<ll> dist(n, INF64);
		priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> pq;
		pq.push(make_pair(0, 0));
		dist[0] = 0;
		while (!pq.empty()) {
			auto[d, x] = pq.top();
			pq.pop();
			if (d != dist[x]) {
				continue;
			}
			for (auto&[c, go] : g[x]) {
				if (go.size() == 1) {
					if (assign_min(dist[go[0].second], d)) {
						pq.push(make_pair(d, go[0].second));
					}
					continue;
				}
				for (auto[p, i] : go) {
					if (assign_min(dist[i], d + min(p, sum[x][c] - p))) {
						pq.push(make_pair(dist[i], i));
					}
					if (g[i][c].size() > 1) {
						ll j = g[i][c][0].second;
						ll np = g[i][c][0].first;
						if (assign_min(dist[j], d + sum[i][c] - np)) {
							pq.push(make_pair(dist[j], j));
						}
						j = g[i][c][1].second;
						np = g[i][c][1].first;
						if (assign_min(dist[j], d + sum[i][c] - np)) {
							pq.push(make_pair(dist[j], j));
						}
					}
				}
			}
		}
		cout << (dist.back() == INF64 ? -1 : dist.back()) << '\n';
		return;
	}
	vector<vector<ll>> dist(n, vector<ll>(n, INF64));
	priority_queue<tuple<ll, ll, ll>, vector<tuple<ll, ll, ll>>, greater<tuple<ll, ll, ll>>> pq;
	pq.push(make_tuple(0, 0, 0));
	dist[0][0] = 0;
	while (!pq.empty()) {
		auto[d, x, pp] = pq.top();
		pq.pop();
		if (d != dist[x][pp]) {
			continue;
		}
		for (auto[b, c, p] : go[x]) {
			if (b != pp) {
				nc[c] += p;
			}
		}
		for (auto[b, c, p] : go[x]) {
			if (b == pp) {
				continue;
			}
			nc[c] -= p;
			if (assign_min(dist[b][b], d + nc[c])) {
				pq.push(make_tuple(dist[b][b], b, b));
			}
			if (assign_min(dist[b][x], d + p)) {
				pq.push(make_tuple(dist[b][x], b, x));
			}
			nc[c] += p;
		}
		for (auto[b, c, p] : go[x]) {
			if (b != pp) {
				nc[c] -= p;
			}
		}
	}
	ll ans = INF64;
	for (auto i : dist.back()) {
		assign_min(ans, i);
	}
	cout << (ans == INF64 ? -1 : ans) << '\n';
}

int main() {
	if (IS_FILE) {
		freopen("", "r", stdin);
		freopen("", "w", stdout);
	}
    	ios_base::sync_with_stdio(false);
    	cin.tie(0);
    	cout.tie(0);
	ll t = 1;
	if (IS_TEST_CASES) {
		cin >> t;
	}
	for (ll i = 0; i < t; i++) {
		solve();
	}
}

Compilation message (stderr)

Main.cpp: In function 'void solve()':
Main.cpp:55:7: warning: variable 'f' set but not used [-Wunused-but-set-variable]
   55 |  bool f = true;
      |       ^
Main.cpp: In function 'int main()':
Main.cpp:165:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  165 |   freopen("", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~
Main.cpp:166:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  166 |   freopen("", "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~

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