oj.uz

Submission #805573

# Submission time Handle Problem Language Result Execution time Memory
805573 2023-08-03T17:58:30 Z denniskim Robot (JOI21_ho_t4) C++17
100 / 100
 1187 ms 154904 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef __int128 lll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pld;
#define MAX 9223372036854775807LL
#define MIN -9223372036854775807LL
#define INF 0x3f3f3f3f3f3f3f3f
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cout << fixed; cout.precision(10);
#define sp << " "
#define en << "\n"
#define compress(v) sort(v.begin(), v.end()), v.erase(unique(v.begin(), v.end()), v.end())

struct edge
{
	ll v, col, cost, num;
};

ll n, m;
vector<edge> vec[500010];
pair<pll, pll> edg[500010];
pair<pll, pll> edg2[500010];
ll all, bll, cll, dll;
ll nu[500010];
map<pll, vector<pll> > vv;
map<pll, ll> sum;
ll cc;
vector<pll> vec2[500010];
ll dist[500010];
priority_queue<pll> pq;
ll ans = INF;

ll bun(ll X, ll Y)
{
	ll gap = 0;
	
	if(!Y)
		return nu[X - 1] + 1;
	
	if(edg2[Y].fi.fi == X)
		gap = edg2[Y].fi.se;
	else
		gap = edg2[Y].se.se;
	
	return nu[X - 1] + gap + 1;
}

int main(void)
{
	fastio
	
	cin >> n >> m;
	
	for(ll i = 1 ; i <= m ; ++i)
	{
		cin >> all >> bll >> cll >> dll;
		
		vec[all].push_back({bll, cll, dll, i});
		vec[bll].push_back({all, cll, dll, i});
		edg[i] = {{all, bll}, {cll, dll}};
	}
	
	for(ll i = 1 ; i <= n ; i++)
	{
		ll cou = 1;
		
		nu[i] = nu[i - 1] + (ll)vec[i].size() + 1;
		
		for(auto &j : vec[i])
		{
			if(edg2[j.num].fi.fi)
				edg2[j.num].se = {i, cou};
			else
				edg2[j.num].fi = {i, cou};
			
			cou++;
		}
	}
	
	for(ll i = 1 ; i <= n ; ++i)
	{
		for(auto &j : vec[i])
		{
			if((ll)vv[{i, j.col}].size() < 2)
			{
				vv[{i, j.col}].push_back({j.cost, j.num});
				sort(vv[{i, j.col}].begin(), vv[{i, j.col}].end());
				reverse(vv[{i, j.col}].begin(), vv[{i, j.col}].end());
			}
			
			else
			{
				if(vv[{i, j.col}][0].fi < j.cost)
				{
					vv[{i, j.col}][1] = vv[{i, j.col}][0];
					vv[{i, j.col}][0] = {j.cost, j.num};
				}
				
				else if(vv[{i, j.col}][1].fi < j.cost)
					vv[{i, j.col}][1] = {j.cost, j.num};
			}
			
			sum[{i, j.col}] += j.cost;
			vec2[bun(i, j.num)].push_back({bun(i, 0), 0});
		}
	}
	
	for(ll i = 1 ; i <= n ; ++i)
	{
		for(auto &j : vec[i])
		{
			ll C = sum[{i, j.col}] - j.cost;
			
			vec2[bun(i, 0)].push_back({bun(j.v, 0), C});
			vec2[bun(i, 0)].push_back({bun(j.v, j.num), j.cost});
			
			if((ll)vv[{i, j.col}].size() <= 1)
				continue;
			
			if((ll)vv[{i, j.col}][0].se != j.num)
			{
				ll numm = vv[{i, j.col}][0].se;
				vec2[bun(i, j.num)].push_back({bun(edg[numm].fi.fi + edg[numm].fi.se - i, 0), C - edg[numm].se.se});
			}
			
			else
			{
				ll numm = vv[{i, j.col}][1].se;
				vec2[bun(i, j.num)].push_back({bun(edg[numm].fi.fi + edg[numm].fi.se - i, 0), C - edg[numm].se.se});
			}
		}
	}
	
	cc = nu[n];
	
	for(ll i = 1 ; i <= cc ; ++i)
		dist[i] = INF;
	
	dist[bun(1, 0)] = 0;
	pq.push({0, bun(1, 0)});
	
	while(!pq.empty())
	{
		pll qq = pq.top();
		pq.pop();
		
		if(-qq.fi > dist[qq.se])
			continue;
		
		for(auto &i : vec2[qq.se])
		{
			if(dist[i.fi] > dist[qq.se] + i.se)
			{
				dist[i.fi] = dist[qq.se] + i.se;
				pq.push({-dist[i.fi], i.fi});
			}
		}
	}
	
	ans = min(ans, dist[bun(n, 0)]);
	
	for(auto &i : vec[n])
		ans = min(ans, dist[bun(n, i.num)]);
	
	if(ans == INF)
		cout << -1;
	else
		cout << ans;
	
	return 0;
}

Subtask #1
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23764 KB Output is correct
2 Correct 12 ms 23764 KB Output is correct
3 Correct 11 ms 23848 KB Output is correct
4 Correct 11 ms 23764 KB Output is correct
5 Correct 12 ms 23892 KB Output is correct
6 Correct 11 ms 23780 KB Output is correct
7 Correct 13 ms 24248 KB Output is correct
8 Correct 12 ms 24020 KB Output is correct
9 Correct 16 ms 25044 KB Output is correct
10 Correct 19 ms 25168 KB Output is correct
11 Correct 15 ms 24788 KB Output is correct
12 Correct 15 ms 24644 KB Output is correct
13 Correct 19 ms 24832 KB Output is correct
14 Correct 15 ms 24848 KB Output is correct
15 Correct 14 ms 24360 KB Output is correct
16 Correct 15 ms 24804 KB Output is correct
17 Correct 14 ms 24660 KB Output is correct
18 Correct 13 ms 24124 KB Output is correct
19 Correct 15 ms 24808 KB Output is correct
20 Correct 15 ms 24496 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 276 ms 69184 KB Output is correct
2 Correct 103 ms 44928 KB Output is correct
3 Correct 315 ms 84496 KB Output is correct
4 Correct 160 ms 54500 KB Output is correct
5 Correct 941 ms 149836 KB Output is correct
6 Correct 804 ms 140852 KB Output is correct
7 Correct 607 ms 121444 KB Output is correct
8 Correct 625 ms 121220 KB Output is correct
9 Correct 624 ms 121420 KB Output is correct
10 Correct 410 ms 97028 KB Output is correct
11 Correct 257 ms 75820 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23764 KB Output is correct
2 Correct 12 ms 23764 KB Output is correct
3 Correct 11 ms 23848 KB Output is correct
4 Correct 11 ms 23764 KB Output is correct
5 Correct 12 ms 23892 KB Output is correct
6 Correct 11 ms 23780 KB Output is correct
7 Correct 13 ms 24248 KB Output is correct
8 Correct 12 ms 24020 KB Output is correct
9 Correct 16 ms 25044 KB Output is correct
10 Correct 19 ms 25168 KB Output is correct
11 Correct 15 ms 24788 KB Output is correct
12 Correct 15 ms 24644 KB Output is correct
13 Correct 19 ms 24832 KB Output is correct
14 Correct 15 ms 24848 KB Output is correct
15 Correct 14 ms 24360 KB Output is correct
16 Correct 15 ms 24804 KB Output is correct
17 Correct 14 ms 24660 KB Output is correct
18 Correct 13 ms 24124 KB Output is correct
19 Correct 15 ms 24808 KB Output is correct
20 Correct 15 ms 24496 KB Output is correct
21 Correct 276 ms 69184 KB Output is correct
22 Correct 103 ms 44928 KB Output is correct
23 Correct 315 ms 84496 KB Output is correct
24 Correct 160 ms 54500 KB Output is correct
25 Correct 941 ms 149836 KB Output is correct
26 Correct 804 ms 140852 KB Output is correct
27 Correct 607 ms 121444 KB Output is correct
28 Correct 625 ms 121220 KB Output is correct
29 Correct 624 ms 121420 KB Output is correct
30 Correct 410 ms 97028 KB Output is correct
31 Correct 257 ms 75820 KB Output is correct
32 Correct 295 ms 83700 KB Output is correct
33 Correct 361 ms 73320 KB Output is correct
34 Correct 512 ms 102984 KB Output is correct
35 Correct 422 ms 87516 KB Output is correct
36 Correct 488 ms 95192 KB Output is correct
37 Correct 568 ms 109484 KB Output is correct
38 Correct 618 ms 121392 KB Output is correct
39 Correct 392 ms 92784 KB Output is correct
40 Correct 609 ms 121120 KB Output is correct
41 Correct 688 ms 121424 KB Output is correct
42 Correct 667 ms 126176 KB Output is correct
43 Correct 333 ms 77876 KB Output is correct
44 Correct 547 ms 116172 KB Output is correct
45 Correct 489 ms 101700 KB Output is correct
46 Correct 428 ms 99420 KB Output is correct
47 Correct 634 ms 106808 KB Output is correct
48 Correct 1187 ms 154904 KB Output is correct