oj.uz

Submission #807438

# Submission time Handle Problem Language Result Execution time Memory
807438 2023-08-04T17:35:51 Z vjudge1 Robot (JOI21_ho_t4) C++17
0 / 100
 3000 ms 119964 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<int,pair<int,int>>>st;
    st.insert({0 , {1 , 0}});
    d[1] = 0;
    while(!st.empty()){
        auto it = st.begin();
        x = it->fi , y = it->se.fi , k = it->se.se;
        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] , {to.to , 0}});
            }
        }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] , {to.to , 0}});
                    if(!d1[to.to].count(it) || x < d1[to.to][it])
                        d1[to.to][it] = x;
                        st.insert({d1[to.to][it] , {to.to , it}});
                }
            }
        }
    }
    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] , {to.to , it}});
      |                         ^~
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
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 37876 KB Output is correct
2 Correct 17 ms 37840 KB Output is correct
3 Correct 17 ms 37908 KB Output is correct
4 Correct 17 ms 37904 KB Output is correct
5 Correct 17 ms 37844 KB Output is correct
6 Correct 17 ms 37908 KB Output is correct
7 Correct 21 ms 38044 KB Output is correct
8 Correct 17 ms 37972 KB Output is correct
9 Correct 23 ms 38660 KB Output is correct
10 Correct 20 ms 38544 KB Output is correct
11 Correct 22 ms 38404 KB Output is correct
12 Correct 20 ms 38324 KB Output is correct
13 Correct 22 ms 38356 KB Output is correct
14 Correct 22 ms 38476 KB Output is correct
15 Incorrect 18 ms 38172 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 215 ms 61600 KB Output is correct
2 Correct 84 ms 49868 KB Output is correct
3 Correct 256 ms 57276 KB Output is correct
4 Correct 140 ms 53648 KB Output is correct
5 Correct 1143 ms 119964 KB Output is correct
6 Execution timed out 3065 ms 109504 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 37876 KB Output is correct
2 Correct 17 ms 37840 KB Output is correct
3 Correct 17 ms 37908 KB Output is correct
4 Correct 17 ms 37904 KB Output is correct
5 Correct 17 ms 37844 KB Output is correct
6 Correct 17 ms 37908 KB Output is correct
7 Correct 21 ms 38044 KB Output is correct
8 Correct 17 ms 37972 KB Output is correct
9 Correct 23 ms 38660 KB Output is correct
10 Correct 20 ms 38544 KB Output is correct
11 Correct 22 ms 38404 KB Output is correct
12 Correct 20 ms 38324 KB Output is correct
13 Correct 22 ms 38356 KB Output is correct
14 Correct 22 ms 38476 KB Output is correct
15 Incorrect 18 ms 38172 KB Output isn't correct
16 Halted 0 ms 0 KB -