Submission #1162660

#	Time	Username	Problem	Language	Result	Execution time	Memory
1162660		Der_Vlapos	Robot (JOI21_ho_t4)	C++20	100 / 100	2552 ms	152544 KiB

Main

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

#define ll long long
#define pii pair<int, int>
#define f first
#define s second
#define all(v) v.begin(), v.end()
#define pb push_back

struct segTree
{
	vector<int> tree;
	int sz = 0;

	void init(int n)
	{
		sz = n;
		tree.resize(2 * sz, 0);
	}

	void set(int pos, int val)
	{
		pos += sz;
		tree[pos] = val;
		pos >>= 1;
		while (pos)
		{
			tree[pos] = tree[pos << 1] + tree[(pos << 1) | 1];
			pos >>= 1;
		}
	}

	int get(int l, int r)
	{
		int res = 0;
		l += sz;
		r += sz;
		while (l < r)
		{
			if (l & 1)
				res += tree[l++];
			if (r & 1)
				res += tree[--r];
			l >>= 1;
			r >>= 1;
		}
		return res;
	}
};

#define int ll
const ll INF = 1e18 + 10;

struct test
{
	vector<pii> E;
	vector<int> C, P;
	vector<vector<int>> graph;
	vector<set<int>> ngraph;
	void solve()
	{
		int n, m;
		cin >> n >> m;
		vector<pii> edges;
		vector<map<int, ll>> cost(n);
		map<pii, vector<int>> edgesVCol;
		graph.resize(n);
		ngraph.resize(n);
		for (int i = 0; i < m; ++i)
		{
			int v, tov, c, p;
			cin >> v >> tov >> c >> p;
			--v, --tov, --c;
			E.pb({v, tov});
			C.pb(c);
			P.pb(p);
			cost[v][c] += p;
			cost[tov][c] += p;
			graph[v].pb(i);
			graph[tov].pb(i);
			ngraph[v].insert(i);
			ngraph[tov].insert(i);
			edgesVCol[{v, c}].pb(i);
			edgesVCol[{tov, c}].pb(i);
		}

		int res = INF;
		priority_queue<pair<int, pair<pii, int>>> els;
		map<pii, int> costs;
		map<pii, int> OUT;
		for (int i = 0; i <= m; ++i)
		{
			costs[{0, i}] = 0;
			OUT[{0, i}] = 0;
		}
		els.push({-0, {{0, m}, 0}});

		while (els.size())
		{
			auto [c, WTF] = els.top();
			auto [inf, t] = WTF;
			els.pop();
			c = -c;
			auto [v, col] = inf;
			if (!t)
			{
				if (v == n - 1)
					res = min(res, c);
				if (costs[inf] != c)
					continue;
				auto it = ngraph[v].begin();
				while (it != ngraph[v].end())
				{
					int tov = E[*it].f == v ? E[*it].s : E[*it].f;
					if (col != C[*it])
					{
						if (costs.find({tov, C[*it]}) == costs.end() or costs[{tov, C[*it]}] > c + min(P[*it], cost[v][C[*it]] - P[*it]))
						{
							costs[{tov, C[*it]}] = c + min(P[*it], cost[v][C[*it]] - P[*it]);
							els.push({-costs[{tov, C[*it]}], {{tov, C[*it]}, 0}});
						}
					}
					if (costs.find({tov, m}) == costs.end() or costs[{tov, m}] > c + P[*it])
					{
						costs[{tov, m}] = c + P[*it];
						els.push({-costs[{tov, m}], {{tov, m}, 0}});
					}
					if (OUT.find({tov, C[*it]}) == OUT.end() or OUT[{tov, C[*it]}] > c)
					{
						OUT[{tov, C[*it]}] = c;
						els.push({-OUT[{tov, C[*it]}], {{tov, C[*it]}, 1}});
					}
					if (col != C[*it])
						it = ngraph[v].erase(it);
					else
					{
						it = next(it);
					}
				}
			}
			else
			{
				if (OUT[{v, col}] != c)
					continue;
				for (auto id : edgesVCol[{v, col}])
				{
					int tov = E[id].f == v ? E[id].s : E[id].f;
					if (costs.find({tov, col}) == costs.end() or costs[{tov, col}] > c + cost[v][col] - P[id])
					{
						costs[{tov, col}] = c + cost[v][col] - P[id];
						els.push({-costs[{tov, col}], {{tov, col}, 0}});
					}
				}
			}
		}

		cout << (res == INF ? -1 : res) << "\n";
	}
};

main()
{
	test t;
	t.solve();
}

Compilation message (stderr)

Main.cpp:162:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  162 | main()
      | ^~~~

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