oj.uz

Submission #961672

# Submission time Handle Problem Language Result Execution time Memory
961672 2024-04-12T10:04:48 Z happy_node Robot (JOI21_ho_t4) C++17
24 / 100
 940 ms 123876 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MX=5e5+5;
int N,M;
ll dist[MX];
vector<array<int,3>> adj[MX];

map<int,int> id[MX];
map<int,ll> sum[MX];
int rev[MX];

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

	cin>>N>>M;

	priority_queue<pair<ll,ll>> pq;
	int z=N+1;
	for(int i=1;i<=M;i++) {
		int a,b,c,p;
		cin>>a>>b>>c>>p;
		
		sum[a][c]+=p;
		sum[b][c]+=p;
		
		if(!id[b].count(c)) {
			rev[z]=b;
			id[b][c]=z++;
		}

		if(!id[a].count(c)) {
			rev[z]=a;
			id[a][c]=z++;
		}

		adj[a].push_back({b,c,p});
		adj[b].push_back({a,c,p});

		adj[id[a][c]].push_back({b,c,p});
		adj[b].push_back({id[a][c],c,p});

		adj[id[b][c]].push_back({a,c,p});
		adj[a].push_back({id[b][c],c,p});

		adj[id[a][c]].push_back({id[b][c],c,p});
		adj[id[b][c]].push_back({id[a][c],c,p});
	}

	for(int i=1;i<z;i++) {
		dist[i]=1e18;
	}

	pq.push({0,1});
	dist[1]=0;
	while(!pq.empty()) {
		auto [d,v]=pq.top(); pq.pop();
		d=-d;
		if(d>dist[v]) continue;

		for(auto [u,c,p]:adj[v]) {
			if(dist[u]>dist[v]+p) {
				dist[u]=dist[v]+p;
				pq.push({-dist[u],u});
			}	
		}

		if(v>N) {
			for(auto [u,c,p]:adj[v]) {
				if(u>N) {
					ll cost=sum[rev[v]][c]-p;
					if(dist[u]>dist[v]+cost) {
						dist[u]=dist[v]+cost;
						pq.push({-dist[u],u});
					}
				} else {
					if(adj[v].size()<=4&&dist[u]>dist[v]) {
						dist[u]=dist[v];
						pq.push({-dist[u],u});
					}
				}	
			}
		} else {
			for(auto [u,c,p]:adj[v]) {
				if(u>N) {
					if(dist[u]>dist[v]+p) {
						dist[u]=dist[v]+p;
						pq.push({-dist[u],u});
					}
				} else {
					ll cost=sum[v][c]-p;
					if(dist[u]>dist[v]+cost) {
						dist[u]=dist[v]+cost;
						pq.push({-dist[u],u});
					}
				}	
			}
		}
	}

	cout<<(dist[N]==1e18?-1:dist[N])<<'\n';
}

Subtask #1
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 61788 KB Output is correct
2 Correct 15 ms 61788 KB Output is correct
3 Correct 14 ms 61924 KB Output is correct
4 Correct 14 ms 61972 KB Output is correct
5 Correct 14 ms 62072 KB Output is correct
6 Correct 14 ms 61892 KB Output is correct
7 Correct 14 ms 62144 KB Output is correct
8 Correct 16 ms 62044 KB Output is correct
9 Correct 16 ms 62464 KB Output is correct
10 Correct 16 ms 62492 KB Output is correct
11 Correct 15 ms 62300 KB Output is correct
12 Correct 16 ms 62456 KB Output is correct
13 Correct 16 ms 62300 KB Output is correct
14 Incorrect 15 ms 62468 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 81148 KB Output is correct
2 Correct 63 ms 71332 KB Output is correct
3 Correct 159 ms 87716 KB Output is correct
4 Correct 105 ms 74448 KB Output is correct
5 Correct 940 ms 123876 KB Output is correct
6 Correct 735 ms 120648 KB Output is correct
7 Correct 293 ms 105416 KB Output is correct
8 Correct 358 ms 104572 KB Output is correct
9 Correct 375 ms 104560 KB Output is correct
10 Correct 247 ms 96000 KB Output is correct
11 Correct 136 ms 85192 KB Output is correct

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 61788 KB Output is correct
2 Correct 15 ms 61788 KB Output is correct
3 Correct 14 ms 61924 KB Output is correct
4 Correct 14 ms 61972 KB Output is correct
5 Correct 14 ms 62072 KB Output is correct
6 Correct 14 ms 61892 KB Output is correct
7 Correct 14 ms 62144 KB Output is correct
8 Correct 16 ms 62044 KB Output is correct
9 Correct 16 ms 62464 KB Output is correct
10 Correct 16 ms 62492 KB Output is correct
11 Correct 15 ms 62300 KB Output is correct
12 Correct 16 ms 62456 KB Output is correct
13 Correct 16 ms 62300 KB Output is correct
14 Incorrect 15 ms 62468 KB Output isn't correct
15 Halted 0 ms 0 KB -