oj.uz

Submission #493853

# Submission time Handle Problem Language Result Execution time Memory
493853 2021-12-13T07:47:26 Z PixelCat Robot (JOI21_ho_t4) C++14
100 / 100
 633 ms 102460 KB 
#include <bits/stdc++.h>
#define For(i,a,b) for(int i=a;i<=b;i++)
#define Forr(i,a,b) for(int i=a;i>=b;i--)
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define sz(x) ((int)x.size())
#define eb emplace_back
#define INF (1000000000000000ll);
#define int ll
using namespace std;
using ll=long long;
using pii=pair<int,int>;

// color -> vector( (to,cost) )
map<int,vector<pii>> adj[100010];
map<int,int> cnt[100010];

vector<pii> g[100010];
int dist[100010];

int32_t main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	// nachoneko sama & miku sama bless me >/////<
	int n,m; cin>>n>>m;
	For(i,1,m){
		int a,b,c,p; cin>>a>>b>>c>>p;
		adj[a][c].eb(b,p);
		adj[b][c].eb(a,p);
		cnt[a][c]++;
		cnt[b][c]++;
	}
	For(i,1,n){
		for(auto &item:adj[i]){
			auto &ad=item.S;
			if(sz(ad)==1){
				g[i].eb(ad[0].F,0ll);
				continue;
			}
			
			sort(all(ad),[](const pii &a,const pii &b){
				return a.S>b.S;
			});
			int tot=0;
			for(auto &j:ad) tot+=j.S;

			for(auto &j:ad){
				g[i].eb(j.F,j.S);
			}
			
			// leave the biggest edge, change the rest
			g[i].eb(ad[0].F,tot-ad[0].S);
			For(iter,1,sz(ad)-1){
				g[ad[iter].F].eb(ad[0].F,tot-ad[0].S);
			}

			// leave the 2nd biggest edge, change the rest
			g[i].eb(ad[1].F,tot-ad[1].S);
			For(iter,0,sz(ad)-1) if(iter!=1){
				g[ad[iter].F].eb(ad[1].F,tot-ad[1].S);
			}
		}
	}
	// dijkstra on g[]
	memset(dist,-1,sizeof(dist));
	priority_queue<pii,vector<pii>,greater<pii>> pq;
	pq.emplace(0,1);
	while(!pq.empty()){
		int d=pq.top().F;
		int now=pq.top().S;
		pq.pop();
		if(dist[now]!=-1) continue;
		dist[now]=d;
		for(auto &e:g[now]) if(dist[e.F]==-1){
			pq.emplace(d+e.S,e.F);
		}
	}
	cout<<dist[n]<<"\n";
	return 0;
}

Subtask #1
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12748 KB Output is correct
2 Correct 8 ms 12772 KB Output is correct
3 Correct 6 ms 12748 KB Output is correct
4 Correct 6 ms 12748 KB Output is correct
5 Correct 6 ms 12876 KB Output is correct
6 Correct 6 ms 12748 KB Output is correct
7 Correct 8 ms 13132 KB Output is correct
8 Correct 7 ms 13004 KB Output is correct
9 Correct 9 ms 13644 KB Output is correct
10 Correct 9 ms 13644 KB Output is correct
11 Correct 9 ms 13516 KB Output is correct
12 Correct 8 ms 13388 KB Output is correct
13 Correct 9 ms 13516 KB Output is correct
14 Correct 8 ms 13488 KB Output is correct
15 Correct 8 ms 13132 KB Output is correct
16 Correct 10 ms 13368 KB Output is correct
17 Correct 9 ms 13388 KB Output is correct
18 Correct 7 ms 12984 KB Output is correct
19 Correct 9 ms 13516 KB Output is correct
20 Correct 8 ms 13260 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 173 ms 41404 KB Output is correct
2 Correct 68 ms 25200 KB Output is correct
3 Correct 255 ms 52916 KB Output is correct
4 Correct 114 ms 31164 KB Output is correct
5 Correct 613 ms 94924 KB Output is correct
6 Correct 518 ms 83860 KB Output is correct
7 Correct 373 ms 68552 KB Output is correct
8 Correct 458 ms 69792 KB Output is correct
9 Correct 477 ms 69980 KB Output is correct
10 Correct 327 ms 57980 KB Output is correct
11 Correct 182 ms 43100 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12748 KB Output is correct
2 Correct 8 ms 12772 KB Output is correct
3 Correct 6 ms 12748 KB Output is correct
4 Correct 6 ms 12748 KB Output is correct
5 Correct 6 ms 12876 KB Output is correct
6 Correct 6 ms 12748 KB Output is correct
7 Correct 8 ms 13132 KB Output is correct
8 Correct 7 ms 13004 KB Output is correct
9 Correct 9 ms 13644 KB Output is correct
10 Correct 9 ms 13644 KB Output is correct
11 Correct 9 ms 13516 KB Output is correct
12 Correct 8 ms 13388 KB Output is correct
13 Correct 9 ms 13516 KB Output is correct
14 Correct 8 ms 13488 KB Output is correct
15 Correct 8 ms 13132 KB Output is correct
16 Correct 10 ms 13368 KB Output is correct
17 Correct 9 ms 13388 KB Output is correct
18 Correct 7 ms 12984 KB Output is correct
19 Correct 9 ms 13516 KB Output is correct
20 Correct 8 ms 13260 KB Output is correct
21 Correct 173 ms 41404 KB Output is correct
22 Correct 68 ms 25200 KB Output is correct
23 Correct 255 ms 52916 KB Output is correct
24 Correct 114 ms 31164 KB Output is correct
25 Correct 613 ms 94924 KB Output is correct
26 Correct 518 ms 83860 KB Output is correct
27 Correct 373 ms 68552 KB Output is correct
28 Correct 458 ms 69792 KB Output is correct
29 Correct 477 ms 69980 KB Output is correct
30 Correct 327 ms 57980 KB Output is correct
31 Correct 182 ms 43100 KB Output is correct
32 Correct 211 ms 55740 KB Output is correct
33 Correct 206 ms 50808 KB Output is correct
34 Correct 347 ms 67252 KB Output is correct
35 Correct 270 ms 53628 KB Output is correct
36 Correct 314 ms 57256 KB Output is correct
37 Correct 411 ms 70980 KB Output is correct
38 Correct 382 ms 70096 KB Output is correct
39 Correct 240 ms 62804 KB Output is correct
40 Correct 504 ms 73072 KB Output is correct
41 Correct 507 ms 73636 KB Output is correct
42 Correct 462 ms 80684 KB Output is correct
43 Correct 208 ms 48752 KB Output is correct
44 Correct 445 ms 75640 KB Output is correct
45 Correct 372 ms 59604 KB Output is correct
46 Correct 315 ms 59492 KB Output is correct
47 Correct 341 ms 64640 KB Output is correct
48 Correct 633 ms 102460 KB Output is correct