oj.uz

Submission #807445

# Submission time Handle Problem Language Result Execution time Memory
807445 2023-08-04T17:41:49 Z vjudge1 Robot (JOI21_ho_t4) C++17
58 / 100
 3000 ms 121436 KB 

#include <bits/stdc++.h>



using namespace std;

#define TL ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define rall(s) s.rbegin(),s.rend()
#define all(s) s.begin(),s.end()
#define pb push_back
#define fi first
#define se second
#define ll long long
#define ld long double
#define YES cout<<"YES\n"
#define Yes cout<<"Yes\n"
#define yes cout<<"yes\n"
#define NO cout<<"NO\n"
#define No cout<<"No\n"
#define no cout<<"no\n"


const int N = 2e5 + 9 , mod = 1e9 + 7;
ll  d[N] = {} , dp[N] = {} , a[N] = {},  b[N] , c[N];


struct edge{
ll to , cost;
};
set<int>st[N];
map<int,vector<edge>>v[N];
map<int,ll>sum[N] , d1[N];

void solve(){
    ll q , i , j , m ,n, z ,s = 0 , f , l , r , k , x , y , mn  = 1e18 , mx = 0;
    cin>>n>>m;
    for(i = 1; i <= m; i++){
        cin>>x>>y>>l>>r;
        st[x].insert(l);
        st[y].insert(l);
        v[x][l].pb({y , r});
        v[y][l].pb({x , r});
        sum[x][l] += r;
        sum[y][l] += r;
    }
    for(i = 1; i <= n; i++)
        d[i] = 1e18;
    set<pair<ll,pair<ll,ll>>>st;
    st.insert({0 , {0 , 1}});
    d[1] = 0;
    while(!st.empty()){
        auto it = st.begin();
        x = it->fi , y = it->se.se , k = it->se.fi;
        st.erase(it);
        if(k){
            if(d1[y][k] != x)
            continue;
            for(auto to : v[y][k]){
                z = x + sum[y][k] - to.cost;
                if(d[to.to] > z)
                    d[to.to] = z , st.insert({d[to.to] , {0 , to.to }});
            }
        }else {
            if(d[y] != x)
                continue;
            for(auto  it : ::st[y]){
                for(auto to : v[y][it]){
                    z = min(to.cost , sum[y][it] - to.cost);
                    z += x;
                    if(d[to.to] > z)
                    d[to.to] = z , st.insert({d[to.to] , {0 , to.to}});
                    if(!d1[to.to].count(it) || x < d1[to.to][it])
                        d1[to.to][it] = x;
                        st.insert({d1[to.to][it] , {it, to.to}});
                }
            }
        }
    }
    cout<<(d[n] >= 1e18 ? -1 : d[n])<<"\n";
}

int main(){
     TL;
     /*
     #ifndef ONLINE_JUDGE
     freopen("input.txt", "r", stdin);
     freopen("output.txt", "w", stdout);
     #endif
     */
int t = 1;
//cin>>t;

while(t--)
     {
     solve();
     }

}
// Author : حسن

Compilation message

Main.cpp: In function 'void solve()':
Main.cpp:74:21: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   74 |                     if(!d1[to.to].count(it) || x < d1[to.to][it])
      |                     ^~
Main.cpp:76:25: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   76 |                         st.insert({d1[to.to][it] , {it, to.to}});
      |                         ^~
Main.cpp:37:8: warning: unused variable 'q' [-Wunused-variable]
   37 |     ll q , i , j , m ,n, z ,s = 0 , f , l , r , k , x , y , mn  = 1e18 , mx = 0;
      |        ^
Main.cpp:37:16: warning: unused variable 'j' [-Wunused-variable]
   37 |     ll q , i , j , m ,n, z ,s = 0 , f , l , r , k , x , y , mn  = 1e18 , mx = 0;
      |                ^
Main.cpp:37:29: warning: unused variable 's' [-Wunused-variable]
   37 |     ll q , i , j , m ,n, z ,s = 0 , f , l , r , k , x , y , mn  = 1e18 , mx = 0;
      |                             ^
Main.cpp:37:37: warning: unused variable 'f' [-Wunused-variable]
   37 |     ll q , i , j , m ,n, z ,s = 0 , f , l , r , k , x , y , mn  = 1e18 , mx = 0;
      |                                     ^
Main.cpp:37:61: warning: unused variable 'mn' [-Wunused-variable]
   37 |     ll q , i , j , m ,n, z ,s = 0 , f , l , r , k , x , y , mn  = 1e18 , mx = 0;
      |                                                             ^~
Main.cpp:37:74: warning: unused variable 'mx' [-Wunused-variable]
   37 |     ll q , i , j , m ,n, z ,s = 0 , f , l , r , k , x , y , mn  = 1e18 , mx = 0;
      |                                                                          ^~

Subtask #1
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 37844 KB Output is correct
2 Correct 17 ms 37908 KB Output is correct
3 Correct 17 ms 37896 KB Output is correct
4 Correct 16 ms 37836 KB Output is correct
5 Correct 21 ms 37836 KB Output is correct
6 Correct 17 ms 37916 KB Output is correct
7 Correct 18 ms 38136 KB Output is correct
8 Correct 18 ms 37980 KB Output is correct
9 Correct 21 ms 38668 KB Output is correct
10 Correct 20 ms 38616 KB Output is correct
11 Correct 18 ms 38320 KB Output is correct
12 Correct 20 ms 38352 KB Output is correct
13 Correct 21 ms 38448 KB Output is correct
14 Correct 21 ms 38328 KB Output is correct
15 Correct 17 ms 38228 KB Output is correct
16 Correct 19 ms 38228 KB Output is correct
17 Correct 18 ms 38252 KB Output is correct
18 Correct 20 ms 38140 KB Output is correct
19 Correct 20 ms 38100 KB Output is correct
20 Correct 18 ms 38228 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 231 ms 61832 KB Output is correct
2 Correct 85 ms 50508 KB Output is correct
3 Correct 313 ms 55792 KB Output is correct
4 Correct 127 ms 53768 KB Output is correct
5 Correct 1123 ms 121436 KB Output is correct
6 Correct 885 ms 107676 KB Output is correct
7 Correct 426 ms 89544 KB Output is correct
8 Correct 404 ms 79016 KB Output is correct
9 Correct 454 ms 78964 KB Output is correct
10 Correct 366 ms 80868 KB Output is correct
11 Correct 125 ms 59696 KB Output is correct

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 37844 KB Output is correct
2 Correct 17 ms 37908 KB Output is correct
3 Correct 17 ms 37896 KB Output is correct
4 Correct 16 ms 37836 KB Output is correct
5 Correct 21 ms 37836 KB Output is correct
6 Correct 17 ms 37916 KB Output is correct
7 Correct 18 ms 38136 KB Output is correct
8 Correct 18 ms 37980 KB Output is correct
9 Correct 21 ms 38668 KB Output is correct
10 Correct 20 ms 38616 KB Output is correct
11 Correct 18 ms 38320 KB Output is correct
12 Correct 20 ms 38352 KB Output is correct
13 Correct 21 ms 38448 KB Output is correct
14 Correct 21 ms 38328 KB Output is correct
15 Correct 17 ms 38228 KB Output is correct
16 Correct 19 ms 38228 KB Output is correct
17 Correct 18 ms 38252 KB Output is correct
18 Correct 20 ms 38140 KB Output is correct
19 Correct 20 ms 38100 KB Output is correct
20 Correct 18 ms 38228 KB Output is correct
21 Correct 231 ms 61832 KB Output is correct
22 Correct 85 ms 50508 KB Output is correct
23 Correct 313 ms 55792 KB Output is correct
24 Correct 127 ms 53768 KB Output is correct
25 Correct 1123 ms 121436 KB Output is correct
26 Correct 885 ms 107676 KB Output is correct
27 Correct 426 ms 89544 KB Output is correct
28 Correct 404 ms 79016 KB Output is correct
29 Correct 454 ms 78964 KB Output is correct
30 Correct 366 ms 80868 KB Output is correct
31 Correct 125 ms 59696 KB Output is correct
32 Correct 219 ms 51964 KB Output is correct
33 Correct 199 ms 56700 KB Output is correct
34 Correct 521 ms 81648 KB Output is correct
35 Correct 363 ms 71372 KB Output is correct
36 Correct 2240 ms 76680 KB Output is correct
37 Execution timed out 3089 ms 77420 KB Time limit exceeded
38 Halted 0 ms 0 KB -