Submission #544705

#	Time	Username	Problem	Language	Result	Execution time	Memory
544705		blue	Robot (JOI21_ho_t4)	C++17	100 / 100	1811 ms	112260 KiB

Main

#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
using namespace std;

using vi = vector<int>;
using vvi = vector<vi>;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;
using pll = pair<ll, ll>;
using pii = pair<int, int>;
using vpll = vector<pll>;
#define sz(x) int(x.size())

const ll INF = 1'000'000'000'000'000'000LL;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int N, M;
	cin >> N >> M;

	vi edge[1+N];

	vi A(1+M), B(1+M), C(1+M);
	vll P(1+M);
	for(int j = 1; j <= M; j++)
	{
		cin >> A[j] >> B[j] >> C[j] >> P[j];
		edge[A[j]].push_back(j);
		edge[B[j]].push_back(j);
	}

	map<int, int> nodeind[1+N];
	map<pii, int> genind;

	vvi nodeact(1+N, vi(1, 0));

	vvll weightsum(1+N);




	vvi edgebycolor[1+N];


	for(int i = 1; i <= N; i++)
	{
		for(int e : edge[i])
		{
			nodeind[i][C[e]] = 0;
			genind[{i, C[e]}] = 0;
		}

		int nct = 0;
		for(auto& z : nodeind[i])
		{
			z.second = ++nct;
			nodeact[i].push_back(z.first);
		}

		weightsum[i] = vll(1 + sz(nodeind[i]), 0);
		edgebycolor[i] = vvi(1 + sz(nodeind[i]));
	}





	for(int j = 1; j <= M; j++)
	{
		int ai = nodeind[A[j]][C[j]];
		int bi = nodeind[B[j]][C[j]];

		weightsum[ A[j] ][ ai ] += P[j];
		weightsum[ B[j] ][ bi ] += P[j];

		edgebycolor[A[j]][ai].push_back(j);
		edgebycolor[B[j]][bi].push_back(j);
	}


	vi genactnode(1, 0);
	vi genactcolor(1, 0);

	int gct = 0;

	for(auto& z : genind)
	{
		z.second = ++gct;
		genactnode.push_back(z.first.first);
		genactcolor.push_back(z.first.second);
	}

	vll dist(1 + N + gct, INF); //first n = nodes, last gct = pairs
	dist[1] = 0;

	set<pll> tbv;
	for(int i = 1; i <= N+gct; i++) tbv.insert({dist[i], i});


	// cerr << "gct = " << gct << '\n';








	while(!tbv.empty())
	{
		int x = tbv.begin()->second;
		tbv.erase(tbv.begin());

		vector<pll> nxt;

		// cerr << "x = " << x << '\n';

		if(x <= N)
		{
			int u = x;
			// cerr << "case 1\n";

			for(int e : edge[u])
			{
				int v = A[e] + B[e] - u;
				int c = C[e];
				ll p = P[e];

				int ui = nodeind[u][c];

				nxt.push_back({v, min(p, weightsum[u][ui] - p)});
				nxt.push_back({N + genind[{v, c}], 0});
			}
		}
		else
		{
			// cerr << "case 2\n";
			int u = genactnode[x - N];
			int c = genactcolor[x - N];
			// cerr << "hello?\n";

			int ui = nodeind[u][c];

			// cerr << "z\n";

			for(int e : edgebycolor[u][ui])
			{
				int v = A[e] + B[e] - u;
				int vi = nodeind[v][c];

				nxt.push_back({v, weightsum[u][ui] - P[e]});
			}
		}
		// cerr << "nxt built\n";

		for(auto& q : nxt)
		{
			int y = q.first;
			ll w = q.second;

			if(dist[y] <= dist[x] + w) continue;

			tbv.erase({dist[y], y});
			dist[y] = dist[x] + w;
			tbv.insert({dist[y], y});
		}
	}


	if(dist[N] >= 1'000'000'000'000'000LL)
		dist[N] = -1;
	cout << dist[N] << '\n';
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:156:9: warning: unused variable 'vi' [-Wunused-variable]
  156 |     int vi = nodeind[v][c];
      |         ^~

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