oj.uz

Submission #807485

# Submission time Handle Problem Language Result Execution time Memory
807485 2023-08-04T18:04:16 Z vjudge1 Robot (JOI21_ho_t4) C++17
58 / 100
 3000 ms 99204 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 = 1e5 + 9 , mod = 1e9 + 7;
ll  d[N] = {} , dp[N] = {} , a[N] = {},  b[N] , c[N];


struct edge{
int 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 = to.cost;
                    if(z >  sum[y][it] - to.cost)
                        z = 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:41:21: warning: narrowing conversion of 'y' from 'long long int' to 'int' [-Wnarrowing]
   41 |         v[x][l].pb({y , r});
      |                     ^
Main.cpp:41:25: warning: narrowing conversion of 'r' from 'long long int' to 'int' [-Wnarrowing]
   41 |         v[x][l].pb({y , r});
      |                         ^
Main.cpp:42:21: warning: narrowing conversion of 'x' from 'long long int' to 'int' [-Wnarrowing]
   42 |         v[y][l].pb({x , r});
      |                     ^
Main.cpp:42:25: warning: narrowing conversion of 'r' from 'long long int' to 'int' [-Wnarrowing]
   42 |         v[y][l].pb({x , r});
      |                         ^
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:35:8: warning: unused variable 'q' [-Wunused-variable]
   35 |     ll q , i , j , m ,n, z ,s = 0 , f , l , r , k , x , y , mn  = 1e18 , mx = 0;
      |        ^
Main.cpp:35:16: warning: unused variable 'j' [-Wunused-variable]
   35 |     ll q , i , j , m ,n, z ,s = 0 , f , l , r , k , x , y , mn  = 1e18 , mx = 0;
      |                ^
Main.cpp:35:29: warning: unused variable 's' [-Wunused-variable]
   35 |     ll q , i , j , m ,n, z ,s = 0 , f , l , r , k , x , y , mn  = 1e18 , mx = 0;
      |                             ^
Main.cpp:35:37: warning: unused variable 'f' [-Wunused-variable]
   35 |     ll q , i , j , m ,n, z ,s = 0 , f , l , r , k , x , y , mn  = 1e18 , mx = 0;
      |                                     ^
Main.cpp:35:61: warning: unused variable 'mn' [-Wunused-variable]
   35 |     ll q , i , j , m ,n, z ,s = 0 , f , l , r , k , x , y , mn  = 1e18 , mx = 0;
      |                                                             ^~
Main.cpp:35:74: warning: unused variable 'mx' [-Wunused-variable]
   35 |     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 11 ms 19032 KB Output is correct
2 Correct 9 ms 19028 KB Output is correct
3 Correct 10 ms 19028 KB Output is correct
4 Correct 9 ms 19028 KB Output is correct
5 Correct 9 ms 19156 KB Output is correct
6 Correct 9 ms 19112 KB Output is correct
7 Correct 9 ms 19284 KB Output is correct
8 Correct 9 ms 19156 KB Output is correct
9 Correct 13 ms 19860 KB Output is correct
10 Correct 15 ms 19760 KB Output is correct
11 Correct 11 ms 19540 KB Output is correct
12 Correct 16 ms 19500 KB Output is correct
13 Correct 13 ms 19556 KB Output is correct
14 Correct 15 ms 19612 KB Output is correct
15 Correct 10 ms 19368 KB Output is correct
16 Correct 11 ms 19412 KB Output is correct
17 Correct 11 ms 19540 KB Output is correct
18 Correct 15 ms 19348 KB Output is correct
19 Correct 11 ms 19244 KB Output is correct
20 Correct 10 ms 19436 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 266 ms 41652 KB Output is correct
2 Correct 82 ms 31308 KB Output is correct
3 Correct 212 ms 34100 KB Output is correct
4 Correct 115 ms 34032 KB Output is correct
5 Correct 1150 ms 99204 KB Output is correct
6 Correct 974 ms 85140 KB Output is correct
7 Correct 513 ms 62560 KB Output is correct
8 Correct 462 ms 52280 KB Output is correct
9 Correct 426 ms 52324 KB Output is correct
10 Correct 470 ms 58288 KB Output is correct
11 Correct 141 ms 37728 KB Output is correct

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 19032 KB Output is correct
2 Correct 9 ms 19028 KB Output is correct
3 Correct 10 ms 19028 KB Output is correct
4 Correct 9 ms 19028 KB Output is correct
5 Correct 9 ms 19156 KB Output is correct
6 Correct 9 ms 19112 KB Output is correct
7 Correct 9 ms 19284 KB Output is correct
8 Correct 9 ms 19156 KB Output is correct
9 Correct 13 ms 19860 KB Output is correct
10 Correct 15 ms 19760 KB Output is correct
11 Correct 11 ms 19540 KB Output is correct
12 Correct 16 ms 19500 KB Output is correct
13 Correct 13 ms 19556 KB Output is correct
14 Correct 15 ms 19612 KB Output is correct
15 Correct 10 ms 19368 KB Output is correct
16 Correct 11 ms 19412 KB Output is correct
17 Correct 11 ms 19540 KB Output is correct
18 Correct 15 ms 19348 KB Output is correct
19 Correct 11 ms 19244 KB Output is correct
20 Correct 10 ms 19436 KB Output is correct
21 Correct 266 ms 41652 KB Output is correct
22 Correct 82 ms 31308 KB Output is correct
23 Correct 212 ms 34100 KB Output is correct
24 Correct 115 ms 34032 KB Output is correct
25 Correct 1150 ms 99204 KB Output is correct
26 Correct 974 ms 85140 KB Output is correct
27 Correct 513 ms 62560 KB Output is correct
28 Correct 462 ms 52280 KB Output is correct
29 Correct 426 ms 52324 KB Output is correct
30 Correct 470 ms 58288 KB Output is correct
31 Correct 141 ms 37728 KB Output is correct
32 Correct 228 ms 26652 KB Output is correct
33 Correct 289 ms 33008 KB Output is correct
34 Correct 540 ms 56984 KB Output is correct
35 Correct 439 ms 47696 KB Output is correct
36 Correct 2842 ms 51984 KB Output is correct
37 Execution timed out 3015 ms 51608 KB Time limit exceeded
38 Halted 0 ms 0 KB -