# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
493854 |
2021-12-13T08:01:14 Z |
PixelCat |
Robot (JOI21_ho_t4) |
C++14 |
|
467 ms |
66476 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 (ll)(9e18)
#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];
vector<pii> g[100010];
int dist[100010];
bool vis[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);
}
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[]
For(i,1,n) dist[i]=INF;
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(vis[now]) continue;
vis[now]=true;
for(auto &e:g[now]){
if(d+e.S<dist[e.F]){
pq.emplace(d+e.S,e.F);
dist[e.F]=d+e.S;
}
}
}
if(dist[n]==INF) cout<<"-1\n";
else cout<<dist[n]<<"\n";
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
7244 KB |
Output is correct |
2 |
Correct |
3 ms |
7244 KB |
Output is correct |
3 |
Correct |
4 ms |
7372 KB |
Output is correct |
4 |
Correct |
5 ms |
7244 KB |
Output is correct |
5 |
Correct |
4 ms |
7372 KB |
Output is correct |
6 |
Correct |
4 ms |
7372 KB |
Output is correct |
7 |
Correct |
5 ms |
7512 KB |
Output is correct |
8 |
Correct |
4 ms |
7372 KB |
Output is correct |
9 |
Correct |
7 ms |
7884 KB |
Output is correct |
10 |
Correct |
6 ms |
7884 KB |
Output is correct |
11 |
Correct |
5 ms |
7756 KB |
Output is correct |
12 |
Correct |
8 ms |
7740 KB |
Output is correct |
13 |
Correct |
6 ms |
7756 KB |
Output is correct |
14 |
Correct |
5 ms |
7824 KB |
Output is correct |
15 |
Correct |
5 ms |
7628 KB |
Output is correct |
16 |
Correct |
6 ms |
7756 KB |
Output is correct |
17 |
Correct |
5 ms |
7756 KB |
Output is correct |
18 |
Correct |
4 ms |
7500 KB |
Output is correct |
19 |
Correct |
5 ms |
7756 KB |
Output is correct |
20 |
Correct |
4 ms |
7628 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
127 ms |
28352 KB |
Output is correct |
2 |
Correct |
43 ms |
16840 KB |
Output is correct |
3 |
Correct |
140 ms |
37652 KB |
Output is correct |
4 |
Correct |
95 ms |
21416 KB |
Output is correct |
5 |
Correct |
445 ms |
64112 KB |
Output is correct |
6 |
Correct |
385 ms |
58264 KB |
Output is correct |
7 |
Correct |
256 ms |
50876 KB |
Output is correct |
8 |
Correct |
381 ms |
56696 KB |
Output is correct |
9 |
Correct |
425 ms |
56780 KB |
Output is correct |
10 |
Correct |
201 ms |
39508 KB |
Output is correct |
11 |
Correct |
161 ms |
31868 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
7244 KB |
Output is correct |
2 |
Correct |
3 ms |
7244 KB |
Output is correct |
3 |
Correct |
4 ms |
7372 KB |
Output is correct |
4 |
Correct |
5 ms |
7244 KB |
Output is correct |
5 |
Correct |
4 ms |
7372 KB |
Output is correct |
6 |
Correct |
4 ms |
7372 KB |
Output is correct |
7 |
Correct |
5 ms |
7512 KB |
Output is correct |
8 |
Correct |
4 ms |
7372 KB |
Output is correct |
9 |
Correct |
7 ms |
7884 KB |
Output is correct |
10 |
Correct |
6 ms |
7884 KB |
Output is correct |
11 |
Correct |
5 ms |
7756 KB |
Output is correct |
12 |
Correct |
8 ms |
7740 KB |
Output is correct |
13 |
Correct |
6 ms |
7756 KB |
Output is correct |
14 |
Correct |
5 ms |
7824 KB |
Output is correct |
15 |
Correct |
5 ms |
7628 KB |
Output is correct |
16 |
Correct |
6 ms |
7756 KB |
Output is correct |
17 |
Correct |
5 ms |
7756 KB |
Output is correct |
18 |
Correct |
4 ms |
7500 KB |
Output is correct |
19 |
Correct |
5 ms |
7756 KB |
Output is correct |
20 |
Correct |
4 ms |
7628 KB |
Output is correct |
21 |
Correct |
127 ms |
28352 KB |
Output is correct |
22 |
Correct |
43 ms |
16840 KB |
Output is correct |
23 |
Correct |
140 ms |
37652 KB |
Output is correct |
24 |
Correct |
95 ms |
21416 KB |
Output is correct |
25 |
Correct |
445 ms |
64112 KB |
Output is correct |
26 |
Correct |
385 ms |
58264 KB |
Output is correct |
27 |
Correct |
256 ms |
50876 KB |
Output is correct |
28 |
Correct |
381 ms |
56696 KB |
Output is correct |
29 |
Correct |
425 ms |
56780 KB |
Output is correct |
30 |
Correct |
201 ms |
39508 KB |
Output is correct |
31 |
Correct |
161 ms |
31868 KB |
Output is correct |
32 |
Correct |
117 ms |
37848 KB |
Output is correct |
33 |
Correct |
134 ms |
34024 KB |
Output is correct |
34 |
Correct |
266 ms |
45072 KB |
Output is correct |
35 |
Correct |
200 ms |
37416 KB |
Output is correct |
36 |
Correct |
214 ms |
40784 KB |
Output is correct |
37 |
Correct |
288 ms |
47588 KB |
Output is correct |
38 |
Correct |
242 ms |
50852 KB |
Output is correct |
39 |
Correct |
150 ms |
43840 KB |
Output is correct |
40 |
Correct |
383 ms |
56640 KB |
Output is correct |
41 |
Correct |
367 ms |
56820 KB |
Output is correct |
42 |
Correct |
348 ms |
55280 KB |
Output is correct |
43 |
Correct |
134 ms |
32448 KB |
Output is correct |
44 |
Correct |
286 ms |
53920 KB |
Output is correct |
45 |
Correct |
286 ms |
44660 KB |
Output is correct |
46 |
Correct |
268 ms |
44792 KB |
Output is correct |
47 |
Correct |
300 ms |
44868 KB |
Output is correct |
48 |
Correct |
467 ms |
66476 KB |
Output is correct |