# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
692512 |
2023-02-01T17:27:29 Z |
prairie2022 |
Robot (JOI21_ho_t4) |
C++14 |
|
214 ms |
35692 KB |
#include <bits/stdc++.h>
#define int long long
#define inf 1ll<<62
#define fastio cin.tie(0), cout.tie(0), ios::sync_with_stdio(0);
#define pii pair<int, int>
#define C first
#define nb second.first
#define sum second.first
#define yen second.second
#define sp <<' '<<
using namespace std;
signed main(){
fastio
int n, m, a, b, c, p;
cin >> n >> m;
bitset<100001> vst;
vector<vector<pair<int, pii>>> e(n+1); //color, neighbor, cost
vector<vector<pair<int, pii>>> s(n+1, vector<pair<int, pii>> (1, {0ll, {0ll, inf}}));
auto it=s[0].begin();
priority_queue<pii, vector<pii>, greater<pii>> pq;
pq.push({0ll, 1ll});
// color, sum of cost, needed cost
for(; m; m--){
cin >> a >> b >> c >> p;
e[a].push_back({c, {b, p}});
e[b].push_back({c, {a, p}});
}
for(int i=1; i<=n; i++){
if(e[i].empty()) continue;
sort(e[i].begin(), e[i].end());
c = 0;
for(const auto &x: e[i]){
if(x.C!=c){
c = x.C;
s[i].push_back({c, {0ll, inf}});
}
s[i].back().sum += x.yen;
}
}
/*for(int i=1; i<=n; i++){
cout << i << ":\n";
for(const auto &x: e[i])
cout << x.C sp x.nb sp x.yen << '\n';
}
for(int i=1; i<=n; i++){
cout << i << ":\n";
for(const auto &x: s[i])
cout << x.C sp x.sum sp x.yen << '\n';
}*/
s[1][0].yen = 0;
while(!pq.empty()){
m = pq.top().second;
pq.pop();
if(m==n) break;
if(vst[m]) continue;
vst[m] = 1;
c = 0; //index of s
for(const auto &x: e[m]){
if(x.C!=s[m][c].C) c++;
if(vst[x.nb]) continue;
p = min(s[m][0].yen+min(x.yen, s[m][c].sum-x.yen), s[m][c].yen-x.yen);
//cout << m sp x.nb sp p;
if(p<s[x.nb][0].yen){
s[x.nb][0].yen = p;
pq.push({p, x.nb});
}
it = lower_bound(s[x.nb].begin(), s[x.nb].end(), make_pair(s[m][c].C, make_pair(0ll, 0ll)));
it->yen = min(s[m][0].yen+(it->sum), it->yen);
//cout sp (it->C) sp (it->yen) sp (it->sum) << '\n';
}
}
if(s[n][0].yen==inf) cout << "-1\n";
else cout << s[n][0].yen << '\n';
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
324 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
336 KB |
Output is correct |
9 |
Correct |
2 ms |
596 KB |
Output is correct |
10 |
Correct |
2 ms |
604 KB |
Output is correct |
11 |
Correct |
2 ms |
596 KB |
Output is correct |
12 |
Correct |
2 ms |
596 KB |
Output is correct |
13 |
Correct |
2 ms |
596 KB |
Output is correct |
14 |
Correct |
1 ms |
600 KB |
Output is correct |
15 |
Correct |
1 ms |
468 KB |
Output is correct |
16 |
Correct |
2 ms |
596 KB |
Output is correct |
17 |
Correct |
1 ms |
596 KB |
Output is correct |
18 |
Correct |
1 ms |
476 KB |
Output is correct |
19 |
Correct |
1 ms |
468 KB |
Output is correct |
20 |
Correct |
1 ms |
468 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
56 ms |
11496 KB |
Output is correct |
2 |
Correct |
24 ms |
5836 KB |
Output is correct |
3 |
Correct |
72 ms |
15224 KB |
Output is correct |
4 |
Correct |
40 ms |
8832 KB |
Output is correct |
5 |
Correct |
175 ms |
31584 KB |
Output is correct |
6 |
Correct |
163 ms |
30296 KB |
Output is correct |
7 |
Correct |
158 ms |
30172 KB |
Output is correct |
8 |
Correct |
214 ms |
29156 KB |
Output is correct |
9 |
Correct |
190 ms |
29104 KB |
Output is correct |
10 |
Correct |
100 ms |
19564 KB |
Output is correct |
11 |
Correct |
74 ms |
17672 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
324 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
336 KB |
Output is correct |
9 |
Correct |
2 ms |
596 KB |
Output is correct |
10 |
Correct |
2 ms |
604 KB |
Output is correct |
11 |
Correct |
2 ms |
596 KB |
Output is correct |
12 |
Correct |
2 ms |
596 KB |
Output is correct |
13 |
Correct |
2 ms |
596 KB |
Output is correct |
14 |
Correct |
1 ms |
600 KB |
Output is correct |
15 |
Correct |
1 ms |
468 KB |
Output is correct |
16 |
Correct |
2 ms |
596 KB |
Output is correct |
17 |
Correct |
1 ms |
596 KB |
Output is correct |
18 |
Correct |
1 ms |
476 KB |
Output is correct |
19 |
Correct |
1 ms |
468 KB |
Output is correct |
20 |
Correct |
1 ms |
468 KB |
Output is correct |
21 |
Correct |
56 ms |
11496 KB |
Output is correct |
22 |
Correct |
24 ms |
5836 KB |
Output is correct |
23 |
Correct |
72 ms |
15224 KB |
Output is correct |
24 |
Correct |
40 ms |
8832 KB |
Output is correct |
25 |
Correct |
175 ms |
31584 KB |
Output is correct |
26 |
Correct |
163 ms |
30296 KB |
Output is correct |
27 |
Correct |
158 ms |
30172 KB |
Output is correct |
28 |
Correct |
214 ms |
29156 KB |
Output is correct |
29 |
Correct |
190 ms |
29104 KB |
Output is correct |
30 |
Correct |
100 ms |
19564 KB |
Output is correct |
31 |
Correct |
74 ms |
17672 KB |
Output is correct |
32 |
Correct |
81 ms |
14720 KB |
Output is correct |
33 |
Correct |
76 ms |
13912 KB |
Output is correct |
34 |
Correct |
107 ms |
21184 KB |
Output is correct |
35 |
Correct |
95 ms |
18680 KB |
Output is correct |
36 |
Correct |
140 ms |
22736 KB |
Output is correct |
37 |
Correct |
140 ms |
25720 KB |
Output is correct |
38 |
Correct |
159 ms |
29788 KB |
Output is correct |
39 |
Correct |
101 ms |
19860 KB |
Output is correct |
40 |
Correct |
205 ms |
30376 KB |
Output is correct |
41 |
Correct |
210 ms |
30508 KB |
Output is correct |
42 |
Correct |
187 ms |
31516 KB |
Output is correct |
43 |
Correct |
74 ms |
14792 KB |
Output is correct |
44 |
Correct |
115 ms |
22732 KB |
Output is correct |
45 |
Correct |
148 ms |
25572 KB |
Output is correct |
46 |
Correct |
142 ms |
24652 KB |
Output is correct |
47 |
Correct |
149 ms |
25516 KB |
Output is correct |
48 |
Correct |
211 ms |
35692 KB |
Output is correct |