oj.uz

Submission #961647

# Submission time Handle Problem Language Result Execution time Memory
961647 2024-04-12T09:33:00 Z happy_node Robot (JOI21_ho_t4) C++17
24 / 100
 732 ms 111964 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MX=4e5+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<int,int>> 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) {
					if(dist[u]>dist[v]+p) {
						dist[u]=dist[v]+p;
						pq.push({-dist[u],u});
					}
				} else {
					if(adj[v].size()<=4&&dist[u]>dist[v]) {
						dist[u]=dist[v];
						pq.push({-dist[u],u});
					}
				}	
			}
			if(dist[rev[v]]>dist[v]) {
				dist[rev[v]]=dist[v];
				pq.push({-dist[rev[v]],rev[v]});
			}
		} 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 11 ms 49496 KB Output is correct
2 Correct 11 ms 49712 KB Output is correct
3 Correct 11 ms 49500 KB Output is correct
4 Correct 10 ms 49588 KB Output is correct
5 Correct 13 ms 49500 KB Output is correct
6 Correct 12 ms 49600 KB Output is correct
7 Correct 11 ms 49756 KB Output is correct
8 Correct 11 ms 49756 KB Output is correct
9 Correct 17 ms 50264 KB Output is correct
10 Correct 13 ms 50268 KB Output is correct
11 Correct 13 ms 50008 KB Output is correct
12 Incorrect 14 ms 50008 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 69816 KB Output is correct
2 Correct 57 ms 59340 KB Output is correct
3 Correct 138 ms 77168 KB Output is correct
4 Correct 102 ms 63188 KB Output is correct
5 Correct 732 ms 111964 KB Output is correct
6 Correct 691 ms 107004 KB Output is correct
7 Correct 245 ms 92348 KB Output is correct
8 Correct 397 ms 96288 KB Output is correct
9 Correct 388 ms 96308 KB Output is correct
10 Correct 243 ms 84844 KB Output is correct
11 Correct 121 ms 74672 KB Output is correct

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 49496 KB Output is correct
2 Correct 11 ms 49712 KB Output is correct
3 Correct 11 ms 49500 KB Output is correct
4 Correct 10 ms 49588 KB Output is correct
5 Correct 13 ms 49500 KB Output is correct
6 Correct 12 ms 49600 KB Output is correct
7 Correct 11 ms 49756 KB Output is correct
8 Correct 11 ms 49756 KB Output is correct
9 Correct 17 ms 50264 KB Output is correct
10 Correct 13 ms 50268 KB Output is correct
11 Correct 13 ms 50008 KB Output is correct
12 Incorrect 14 ms 50008 KB Output isn't correct
13 Halted 0 ms 0 KB -