oj.uz

Submission #703637

# Submission time Handle Problem Language Result Execution time Memory
703637 2023-02-28T01:57:43 Z EthanKim8683 Robot (JOI21_ho_t4) C++17
100 / 100
 2084 ms 132668 KB 
#include<bits/stdc++.h>
using namespace std;
using I=int;
using Lli=long long int;
const I N=100000;
const Lli MAX=1e18;
map<pair<I,I>,map<pair<I,I>,Lli>>adjs;
map<I,Lli>tots[N];
priority_queue<tuple<Lli,pair<I,I>>>ques;
map<pair<I,I>,Lli>diss;
void add(Lli dis,I a,I c){
  if(!diss.count({a,c}))diss[{a,c}]=MAX;
  if(dis>=diss[{a,c}])return;
  ques.push({-(diss[{a,c}]=dis),{a,c}});
}
I main(){
  cin.tie(0)->sync_with_stdio(0);
  I n,m;cin>>n>>m;
  for(I i=0;i<m;i++){
    I a,b,c,p;cin>>a>>b>>c>>p,a--,b--,c--;
    adjs[{a,c}][{b,c}]=adjs[{b,c}][{a,c}]=p;
    adjs[{a,m}][{b,c}]=adjs[{b,m}][{a,c}]=p;
    tots[a][c]+=p,tots[b][c]+=p;
  }
  add(0,0,m);
  while(ques.size()){
    auto[dis,stt1]=ques.top();ques.pop();
    if((dis=-dis)!=diss[stt1])continue;
    for(auto[stt2,p]:adjs[stt1]){
      auto[a,c1]=stt1;auto[b,c2]=stt2;
      if(c1==m){
        add(dis,b,c2);
        add(dis+min(p,tots[a][c2]-p),b,m);
      }else{
        add(dis+tots[a][c2]-p,b,m);
      }
    }
  }
  printf("%lli\n",diss.count({n-1,m})?diss[{n-1,m}]:-1);
}

Subtask #1
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 3 ms 5076 KB Output is correct
6 Correct 2 ms 4948 KB Output is correct
7 Correct 5 ms 5288 KB Output is correct
8 Correct 4 ms 5152 KB Output is correct
9 Correct 9 ms 6228 KB Output is correct
10 Correct 9 ms 6136 KB Output is correct
11 Correct 7 ms 5844 KB Output is correct
12 Correct 9 ms 5844 KB Output is correct
13 Correct 7 ms 5928 KB Output is correct
14 Correct 8 ms 5892 KB Output is correct
15 Correct 7 ms 5672 KB Output is correct
16 Correct 8 ms 5844 KB Output is correct
17 Correct 8 ms 5832 KB Output is correct
18 Correct 3 ms 5288 KB Output is correct
19 Correct 9 ms 5724 KB Output is correct
20 Correct 7 ms 5716 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 564 ms 43904 KB Output is correct
2 Correct 223 ms 24984 KB Output is correct
3 Correct 788 ms 50276 KB Output is correct
4 Correct 355 ms 32896 KB Output is correct
5 Correct 2003 ms 128212 KB Output is correct
6 Correct 1693 ms 117208 KB Output is correct
7 Correct 1154 ms 96740 KB Output is correct
8 Correct 1359 ms 93640 KB Output is correct
9 Correct 1424 ms 93756 KB Output is correct
10 Correct 905 ms 69652 KB Output is correct
11 Correct 357 ms 48840 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 3 ms 5076 KB Output is correct
6 Correct 2 ms 4948 KB Output is correct
7 Correct 5 ms 5288 KB Output is correct
8 Correct 4 ms 5152 KB Output is correct
9 Correct 9 ms 6228 KB Output is correct
10 Correct 9 ms 6136 KB Output is correct
11 Correct 7 ms 5844 KB Output is correct
12 Correct 9 ms 5844 KB Output is correct
13 Correct 7 ms 5928 KB Output is correct
14 Correct 8 ms 5892 KB Output is correct
15 Correct 7 ms 5672 KB Output is correct
16 Correct 8 ms 5844 KB Output is correct
17 Correct 8 ms 5832 KB Output is correct
18 Correct 3 ms 5288 KB Output is correct
19 Correct 9 ms 5724 KB Output is correct
20 Correct 7 ms 5716 KB Output is correct
21 Correct 564 ms 43904 KB Output is correct
22 Correct 223 ms 24984 KB Output is correct
23 Correct 788 ms 50276 KB Output is correct
24 Correct 355 ms 32896 KB Output is correct
25 Correct 2003 ms 128212 KB Output is correct
26 Correct 1693 ms 117208 KB Output is correct
27 Correct 1154 ms 96740 KB Output is correct
28 Correct 1359 ms 93640 KB Output is correct
29 Correct 1424 ms 93756 KB Output is correct
30 Correct 905 ms 69652 KB Output is correct
31 Correct 357 ms 48840 KB Output is correct
32 Correct 952 ms 48292 KB Output is correct
33 Correct 690 ms 45796 KB Output is correct
34 Correct 1200 ms 75828 KB Output is correct
35 Correct 955 ms 61744 KB Output is correct
36 Correct 988 ms 77548 KB Output is correct
37 Correct 1159 ms 89256 KB Output is correct
38 Correct 1103 ms 103460 KB Output is correct
39 Correct 836 ms 59700 KB Output is correct
40 Correct 1380 ms 98008 KB Output is correct
41 Correct 1551 ms 98384 KB Output is correct
42 Correct 1454 ms 100620 KB Output is correct
43 Correct 532 ms 50216 KB Output is correct
44 Correct 1415 ms 75284 KB Output is correct
45 Correct 1160 ms 84208 KB Output is correct
46 Correct 928 ms 79756 KB Output is correct
47 Correct 1140 ms 85168 KB Output is correct
48 Correct 2084 ms 132668 KB Output is correct