oj.uz

Submission #961664

# Submission time Handle Problem Language Result Execution time Memory
961664 2024-04-12T09:51:05 Z happy_node Robot (JOI21_ho_t4) C++17
24 / 100
 910 ms 111752 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<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});
					}
				}	
			}
			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 22 ms 49500 KB Output is correct
2 Correct 11 ms 49500 KB Output is correct
3 Correct 11 ms 49648 KB Output is correct
4 Correct 11 ms 49500 KB Output is correct
5 Correct 10 ms 49752 KB Output is correct
6 Correct 10 ms 49500 KB Output is correct
7 Correct 11 ms 49896 KB Output is correct
8 Correct 11 ms 49756 KB Output is correct
9 Correct 14 ms 50268 KB Output is correct
10 Correct 15 ms 50264 KB Output is correct
11 Correct 12 ms 50144 KB Output is correct
12 Correct 12 ms 49896 KB Output is correct
13 Correct 13 ms 50012 KB Output is correct
14 Incorrect 12 ms 50012 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 146 ms 68992 KB Output is correct
2 Correct 59 ms 59084 KB Output is correct
3 Correct 148 ms 75256 KB Output is correct
4 Correct 106 ms 62192 KB Output is correct
5 Correct 910 ms 111752 KB Output is correct
6 Correct 714 ms 108224 KB Output is correct
7 Correct 283 ms 92080 KB Output is correct
8 Correct 352 ms 92252 KB Output is correct
9 Correct 356 ms 92056 KB Output is correct
10 Correct 258 ms 83672 KB Output is correct
11 Correct 130 ms 73040 KB Output is correct

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 49500 KB Output is correct
2 Correct 11 ms 49500 KB Output is correct
3 Correct 11 ms 49648 KB Output is correct
4 Correct 11 ms 49500 KB Output is correct
5 Correct 10 ms 49752 KB Output is correct
6 Correct 10 ms 49500 KB Output is correct
7 Correct 11 ms 49896 KB Output is correct
8 Correct 11 ms 49756 KB Output is correct
9 Correct 14 ms 50268 KB Output is correct
10 Correct 15 ms 50264 KB Output is correct
11 Correct 12 ms 50144 KB Output is correct
12 Correct 12 ms 49896 KB Output is correct
13 Correct 13 ms 50012 KB Output is correct
14 Incorrect 12 ms 50012 KB Output isn't correct
15 Halted 0 ms 0 KB -