oj.uz

Submission #961648

# Submission time Handle Problem Language Result Execution time Memory
961648 2024-04-12T09:33:49 Z happy_node Robot (JOI21_ho_t4) C++17
24 / 100
 762 ms 111436 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) {
					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 10 ms 49500 KB Output is correct
2 Correct 10 ms 49752 KB Output is correct
3 Correct 11 ms 49500 KB Output is correct
4 Correct 11 ms 49656 KB Output is correct
5 Correct 12 ms 49756 KB Output is correct
6 Correct 13 ms 49496 KB Output is correct
7 Correct 14 ms 49756 KB Output is correct
8 Correct 11 ms 49752 KB Output is correct
9 Correct 13 ms 50264 KB Output is correct
10 Correct 13 ms 50276 KB Output is correct
11 Correct 12 ms 50012 KB Output is correct
12 Incorrect 12 ms 50012 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 125 ms 68984 KB Output is correct
2 Correct 64 ms 59004 KB Output is correct
3 Correct 145 ms 75424 KB Output is correct
4 Correct 81 ms 62160 KB Output is correct
5 Correct 762 ms 111436 KB Output is correct
6 Correct 652 ms 107288 KB Output is correct
7 Correct 254 ms 91600 KB Output is correct
8 Correct 387 ms 92496 KB Output is correct
9 Correct 393 ms 92240 KB Output is correct
10 Correct 251 ms 83708 KB Output is correct
11 Correct 127 ms 73044 KB Output is correct

Subtask #3
0 / 42.0

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