oj.uz

Submission #544705

# Submission time Handle Problem Language Result Execution time Memory
544705 2022-04-02T15:35:37 Z blue Robot (JOI21_ho_t4) C++17
100 / 100
 1811 ms 112260 KB 
#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

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.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 2 ms 464 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 6 ms 1360 KB Output is correct
10 Correct 5 ms 1236 KB Output is correct
11 Correct 3 ms 980 KB Output is correct
12 Correct 3 ms 968 KB Output is correct
13 Correct 4 ms 1048 KB Output is correct
14 Correct 3 ms 972 KB Output is correct
15 Correct 3 ms 848 KB Output is correct
16 Correct 4 ms 980 KB Output is correct
17 Correct 4 ms 980 KB Output is correct
18 Correct 2 ms 852 KB Output is correct
19 Correct 3 ms 596 KB Output is correct
20 Correct 3 ms 852 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 420 ms 29092 KB Output is correct
2 Correct 148 ms 15992 KB Output is correct
3 Correct 356 ms 21700 KB Output is correct
4 Correct 215 ms 21636 KB Output is correct
5 Correct 1726 ms 110768 KB Output is correct
6 Correct 1320 ms 97448 KB Output is correct
7 Correct 651 ms 73756 KB Output is correct
8 Correct 886 ms 68700 KB Output is correct
9 Correct 940 ms 68696 KB Output is correct
10 Correct 695 ms 54684 KB Output is correct
11 Correct 361 ms 51104 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 2 ms 464 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 6 ms 1360 KB Output is correct
10 Correct 5 ms 1236 KB Output is correct
11 Correct 3 ms 980 KB Output is correct
12 Correct 3 ms 968 KB Output is correct
13 Correct 4 ms 1048 KB Output is correct
14 Correct 3 ms 972 KB Output is correct
15 Correct 3 ms 848 KB Output is correct
16 Correct 4 ms 980 KB Output is correct
17 Correct 4 ms 980 KB Output is correct
18 Correct 2 ms 852 KB Output is correct
19 Correct 3 ms 596 KB Output is correct
20 Correct 3 ms 852 KB Output is correct
21 Correct 420 ms 29092 KB Output is correct
22 Correct 148 ms 15992 KB Output is correct
23 Correct 356 ms 21700 KB Output is correct
24 Correct 215 ms 21636 KB Output is correct
25 Correct 1726 ms 110768 KB Output is correct
26 Correct 1320 ms 97448 KB Output is correct
27 Correct 651 ms 73756 KB Output is correct
28 Correct 886 ms 68700 KB Output is correct
29 Correct 940 ms 68696 KB Output is correct
30 Correct 695 ms 54684 KB Output is correct
31 Correct 361 ms 51104 KB Output is correct
32 Correct 205 ms 13048 KB Output is correct
33 Correct 300 ms 19888 KB Output is correct
34 Correct 773 ms 50148 KB Output is correct
35 Correct 607 ms 40228 KB Output is correct
36 Correct 768 ms 65696 KB Output is correct
37 Correct 787 ms 72892 KB Output is correct
38 Correct 752 ms 74444 KB Output is correct
39 Correct 218 ms 18140 KB Output is correct
40 Correct 902 ms 69824 KB Output is correct
41 Correct 998 ms 70132 KB Output is correct
42 Correct 1139 ms 79128 KB Output is correct
43 Correct 418 ms 33296 KB Output is correct
44 Correct 650 ms 31304 KB Output is correct
45 Correct 834 ms 66764 KB Output is correct
46 Correct 740 ms 65344 KB Output is correct
47 Correct 721 ms 68308 KB Output is correct
48 Correct 1811 ms 112260 KB Output is correct