# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
410306 |
2021-05-22T13:10:31 Z |
mat_v |
Robot (JOI21_ho_t4) |
C++14 |
|
974 ms |
84360 KB |
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
#define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
#define fb(i,a,b) for(int (i) = (a); (i) >= (b); --(i))
#define mod 998244353
#define xx first
#define yy second
#define all(a) (a).begin(), (a).end()
#define pb push_back
#define ll long long
#define pii pair<ll,int>
using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>,rb_tree_tag, tree_order_statistics_node_update> ordered_set;/// find_by_order(x)(x+1th) , order_of_key() (strictly less)
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
struct edge{
int x;
int boja;
ll v;
};
ll maks = 1e9;
struct node{
int boja;
int x;
ll v;
};
bool operator < (const node &a, const node &b){
return a.v < b.v;
}
bool operator > (const node &a, const node &b){
return a.v > b.v;
}
int n,m;
map<int, vector<edge>> graf[100005];
map<int, ll> sb[100005];
ll dist[100005];
map<int,ll> dist2[100005];
bool cmp(edge a, edge b){
if(a.boja < b.boja)return 1;
return 0;
}
map<pii,bool>post;
int main()
{
ios_base::sync_with_stdio(false); cin.tie(0);
maks *= maks;
cin >> n >> m;
// n = 1005;
// m = 2005;
ff(i,1,m){
int a,b,c,d;
// a = rnd()%n;
// b = rnd()%n;
// a++;
// b++;
// c = rnd()%m;
// c++;
// d = rnd()%1000000;
// if(post[{a,b}]){
// a = (rnd()%n) + 1;
// b = (rnd()%n) + 1;
// }
// post[{a,b}] = post[{b,a}] = 1;
cin >> a >> b >> c >> d;
graf[a][c].pb({b,c,d});
graf[b][c].pb({a,c,d});
sb[a][c] += d;
sb[b][c] += d;
}
priority_queue<node, vector<node>, greater<node> > pq;
pq.push({0,1,0});
dist[1] = 0;
ff(i,2,n)dist[i] = maks;
while(!pq.empty()){
node sta = pq.top();
int koji = sta.x;
int b = sta.boja;
ll vl = sta.v;
pq.pop();
int len = graf[koji].size();
if(len == 0)continue;
if(b){
if(vl != dist2[koji][b])continue;
}
else{
if(vl != dist[koji])continue;
}
if(b){
for(edge i : graf[koji][b]){
if(dist[i.x] > sb[koji][b] - i.v + vl){
dist[i.x] = sb[koji][b] - i.v + vl;
pq.push({0,i.x,dist[i.x]});
}
}
continue;
}
for(auto& i:graf[koji]){
for(edge j:i.yy){
ll d1 = min(j.v, sb[koji][i.xx] - j.v);
if(dist[j.x] > d1 + vl){
dist[j.x] = d1 + vl;
pq.push({0,j.x,dist[j.x]});
}
if(dist2[j.x].find(j.boja) == dist2[j.x].end() || dist2[j.x][j.boja] > vl){
dist2[j.x][j.boja] = vl;
pq.push({j.boja,j.x,vl});
}
}
}
}
if(dist[n] < maks)cout << dist[n] << "\n";
else cout << -1 << "\n";
return 0;
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:6:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
6 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
| ^
Main.cpp:63:5: note: in expansion of macro 'ff'
63 | ff(i,1,m){
| ^~
Main.cpp:6:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
6 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
| ^
Main.cpp:87:5: note: in expansion of macro 'ff'
87 | ff(i,2,n)dist[i] = maks;
| ^~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
14412 KB |
Output is correct |
2 |
Correct |
10 ms |
14332 KB |
Output is correct |
3 |
Correct |
9 ms |
14412 KB |
Output is correct |
4 |
Correct |
9 ms |
14412 KB |
Output is correct |
5 |
Correct |
10 ms |
14416 KB |
Output is correct |
6 |
Correct |
9 ms |
14412 KB |
Output is correct |
7 |
Correct |
12 ms |
14540 KB |
Output is correct |
8 |
Correct |
10 ms |
14412 KB |
Output is correct |
9 |
Correct |
13 ms |
15048 KB |
Output is correct |
10 |
Correct |
12 ms |
14924 KB |
Output is correct |
11 |
Correct |
11 ms |
14712 KB |
Output is correct |
12 |
Correct |
11 ms |
14680 KB |
Output is correct |
13 |
Correct |
11 ms |
14668 KB |
Output is correct |
14 |
Correct |
11 ms |
14760 KB |
Output is correct |
15 |
Correct |
11 ms |
14668 KB |
Output is correct |
16 |
Correct |
11 ms |
14668 KB |
Output is correct |
17 |
Correct |
13 ms |
14680 KB |
Output is correct |
18 |
Correct |
10 ms |
14540 KB |
Output is correct |
19 |
Correct |
11 ms |
14560 KB |
Output is correct |
20 |
Correct |
11 ms |
14668 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
217 ms |
32740 KB |
Output is correct |
2 |
Correct |
90 ms |
23872 KB |
Output is correct |
3 |
Correct |
222 ms |
28992 KB |
Output is correct |
4 |
Correct |
128 ms |
26712 KB |
Output is correct |
5 |
Correct |
974 ms |
78900 KB |
Output is correct |
6 |
Correct |
769 ms |
71748 KB |
Output is correct |
7 |
Correct |
360 ms |
52048 KB |
Output is correct |
8 |
Correct |
448 ms |
50896 KB |
Output is correct |
9 |
Correct |
464 ms |
50912 KB |
Output is correct |
10 |
Correct |
366 ms |
47620 KB |
Output is correct |
11 |
Correct |
151 ms |
32664 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
14412 KB |
Output is correct |
2 |
Correct |
10 ms |
14332 KB |
Output is correct |
3 |
Correct |
9 ms |
14412 KB |
Output is correct |
4 |
Correct |
9 ms |
14412 KB |
Output is correct |
5 |
Correct |
10 ms |
14416 KB |
Output is correct |
6 |
Correct |
9 ms |
14412 KB |
Output is correct |
7 |
Correct |
12 ms |
14540 KB |
Output is correct |
8 |
Correct |
10 ms |
14412 KB |
Output is correct |
9 |
Correct |
13 ms |
15048 KB |
Output is correct |
10 |
Correct |
12 ms |
14924 KB |
Output is correct |
11 |
Correct |
11 ms |
14712 KB |
Output is correct |
12 |
Correct |
11 ms |
14680 KB |
Output is correct |
13 |
Correct |
11 ms |
14668 KB |
Output is correct |
14 |
Correct |
11 ms |
14760 KB |
Output is correct |
15 |
Correct |
11 ms |
14668 KB |
Output is correct |
16 |
Correct |
11 ms |
14668 KB |
Output is correct |
17 |
Correct |
13 ms |
14680 KB |
Output is correct |
18 |
Correct |
10 ms |
14540 KB |
Output is correct |
19 |
Correct |
11 ms |
14560 KB |
Output is correct |
20 |
Correct |
11 ms |
14668 KB |
Output is correct |
21 |
Correct |
217 ms |
32740 KB |
Output is correct |
22 |
Correct |
90 ms |
23872 KB |
Output is correct |
23 |
Correct |
222 ms |
28992 KB |
Output is correct |
24 |
Correct |
128 ms |
26712 KB |
Output is correct |
25 |
Correct |
974 ms |
78900 KB |
Output is correct |
26 |
Correct |
769 ms |
71748 KB |
Output is correct |
27 |
Correct |
360 ms |
52048 KB |
Output is correct |
28 |
Correct |
448 ms |
50896 KB |
Output is correct |
29 |
Correct |
464 ms |
50912 KB |
Output is correct |
30 |
Correct |
366 ms |
47620 KB |
Output is correct |
31 |
Correct |
151 ms |
32664 KB |
Output is correct |
32 |
Correct |
160 ms |
28380 KB |
Output is correct |
33 |
Correct |
183 ms |
29220 KB |
Output is correct |
34 |
Correct |
451 ms |
50016 KB |
Output is correct |
35 |
Correct |
333 ms |
41256 KB |
Output is correct |
36 |
Correct |
329 ms |
46444 KB |
Output is correct |
37 |
Correct |
385 ms |
48700 KB |
Output is correct |
38 |
Correct |
419 ms |
55604 KB |
Output is correct |
39 |
Correct |
171 ms |
31768 KB |
Output is correct |
40 |
Correct |
521 ms |
52408 KB |
Output is correct |
41 |
Correct |
535 ms |
52384 KB |
Output is correct |
42 |
Correct |
534 ms |
60424 KB |
Output is correct |
43 |
Correct |
249 ms |
36796 KB |
Output is correct |
44 |
Correct |
489 ms |
42796 KB |
Output is correct |
45 |
Correct |
349 ms |
47496 KB |
Output is correct |
46 |
Correct |
326 ms |
47828 KB |
Output is correct |
47 |
Correct |
353 ms |
48308 KB |
Output is correct |
48 |
Correct |
926 ms |
84360 KB |
Output is correct |