oj.uz

Submission #812045

# Submission time Handle Problem Language Result Execution time Memory
812045 2023-08-07T06:57:33 Z vjudge1 Olympic Bus (JOI20_ho_t4) C++17
26 / 100
 1000 ms 11612 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 = 5e4 + 9 , mod = 1e9 + 7;
ll  d[209][209] ,us[N][209] ,  a[N] = {}, dp[N] ,  b[N] , c[N] , p[N];

vector<int>v[N][2];

void dijkstra(int x , int k,int p , int o , int n){
    ll i , j , m , s , f ,l , r , y;
    for(i = 1; i <= n; i++){
        d[i][p] = 1e15;
        ::p[i] = 0;
    }
    set<pair<ll,int>>st;
    d[x][p] = 0;
    st.insert({0 , x});
    while(!st.empty()){
        x = st.begin()->se  , f = st.begin()->fi;
        st.erase(st.begin());
        if(d[x][p] != f)
            continue;
         for(auto to : v[x][k]){
            if(to == o)
                continue;
            if(k == 0)
                y = b[to];
            else
                y = a[to];
            if(d[x][p] + c[to] < d[y][p]){
                if(st.find({d[y][p] , y}) != st.end())
                    st.erase({d[y][p] , y});
                ::p[y]=  to;
                d[y][p] = d[x][p] + c[to];

                st.insert({d[y][p] , y});
            }
         }
    }
    for(i = 1; i <= n; i++)
        us[::p[i]][p] = 1;
}

ll check[4] = {};
void get(int i , int x, int n){
    check[x] = us[i][x];
    if(us[i][x]){
        if(x == 0)
            dijkstra(1 , 0 , 0 , i,  n);
        if(x == 1)
            dijkstra(1 , 1 , 1 , i,  n);
        if(x == 2)
            dijkstra(n , 0 , 2 , i ,  n);
        if(x == 3)
            dijkstra(n , 1 , 3 , i ,  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>>a[i]>>b[i]>>c[i]>>dp[i];
        v[a[i]][0].pb(i);
        v[b[i]][1].pb(i);
    }
    dijkstra(1 , 0 , 0 , -1,  n);
    dijkstra(1 , 1 , 1 , -1,  n);
    dijkstra(n , 0 , 2 , -1 ,  n);
    dijkstra(n , 1 , 3 , -1 ,  n);
    //cout<<d[1][2]<<"\n";
    mn = d[n][0] + d[1][2];
    //cout<<mn<<"\n";
    for(i = 1; i <= m; i++){
        for(j = 0; j < 4; j++)
            check[j] = 0;
        get(i , 0 , n);
        get(i , 1 , n);
        get(i , 2 , n);
        get(i , 3 , n);
        //if(i == 3){
        //    cout<<a[i]<<" "<<b[i]<<" "<<"\n";
        //    cout<<b[i]<<" "<<d[b[i]][0]<<" "<<"\n";
        //    cout<<a[i]<<" "<<d[a[i]][3]<<" "<<"\n";
        //}
        x = min(d[n][0] , d[b[i]][0] + d[a[i]][3] + c[i]);
        y= min(d[1][2] , d[b[i]][2] + d[a[i]][1] + c[i]);
        //cout<<x<<" "<<y<<"\n";
        mn = min(mn , x + y + dp[i]);
        if(check[0])
            dijkstra(1 , 0 , 0 , -1,  n);
        if(check[1])
            dijkstra(1 , 1 , 1 , -1,  n);
        if(check[2])
            dijkstra(n , 0 , 2 , -1 ,  n);
        if(check[3])
            dijkstra(n , 1 , 3 , -1 ,  n);
    }
    if(mn >= 1e15)
        mn = -1;
    cout<<mn<<"\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

ho_t4.cpp: In function 'void dijkstra(int, int, int, int, int)':
ho_t4.cpp:31:12: warning: unused variable 'j' [-Wunused-variable]
   31 |     ll i , j , m , s , f ,l , r , y;
      |            ^
ho_t4.cpp:31:16: warning: unused variable 'm' [-Wunused-variable]
   31 |     ll i , j , m , s , f ,l , r , y;
      |                ^
ho_t4.cpp:31:20: warning: unused variable 's' [-Wunused-variable]
   31 |     ll i , j , m , s , f ,l , r , y;
      |                    ^
ho_t4.cpp:31:27: warning: unused variable 'l' [-Wunused-variable]
   31 |     ll i , j , m , s , f ,l , r , y;
      |                           ^
ho_t4.cpp:31:31: warning: unused variable 'r' [-Wunused-variable]
   31 |     ll i , j , m , s , f ,l , r , y;
      |                               ^
ho_t4.cpp: In function 'void solve()':
ho_t4.cpp:82:8: warning: unused variable 'q' [-Wunused-variable]
   82 |     ll q , i , j , m ,n, z ,s = 0 , f , l , r , k , x , y , mn  = 1e18 , mx = 0;
      |        ^
ho_t4.cpp:82:26: warning: unused variable 'z' [-Wunused-variable]
   82 |     ll q , i , j , m ,n, z ,s = 0 , f , l , r , k , x , y , mn  = 1e18 , mx = 0;
      |                          ^
ho_t4.cpp:82:29: warning: unused variable 's' [-Wunused-variable]
   82 |     ll q , i , j , m ,n, z ,s = 0 , f , l , r , k , x , y , mn  = 1e18 , mx = 0;
      |                             ^
ho_t4.cpp:82:37: warning: unused variable 'f' [-Wunused-variable]
   82 |     ll q , i , j , m ,n, z ,s = 0 , f , l , r , k , x , y , mn  = 1e18 , mx = 0;
      |                                     ^
ho_t4.cpp:82:41: warning: unused variable 'l' [-Wunused-variable]
   82 |     ll q , i , j , m ,n, z ,s = 0 , f , l , r , k , x , y , mn  = 1e18 , mx = 0;
      |                                         ^
ho_t4.cpp:82:45: warning: unused variable 'r' [-Wunused-variable]
   82 |     ll q , i , j , m ,n, z ,s = 0 , f , l , r , k , x , y , mn  = 1e18 , mx = 0;
      |                                             ^
ho_t4.cpp:82:49: warning: unused variable 'k' [-Wunused-variable]
   82 |     ll q , i , j , m ,n, z ,s = 0 , f , l , r , k , x , y , mn  = 1e18 , mx = 0;
      |                                                 ^
ho_t4.cpp:82:74: warning: unused variable 'mx' [-Wunused-variable]
   82 |     ll q , i , j , m ,n, z ,s = 0 , f , l , r , k , x , y , mn  = 1e18 , mx = 0;
      |                                                                          ^~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 4552 KB Output is correct
2 Correct 2 ms 3284 KB Output is correct
3 Correct 109 ms 4620 KB Output is correct
4 Correct 122 ms 4632 KB Output is correct
5 Correct 7 ms 3284 KB Output is correct
6 Correct 4 ms 3412 KB Output is correct
7 Correct 1 ms 2644 KB Output is correct
8 Correct 1 ms 2644 KB Output is correct
9 Correct 2 ms 2680 KB Output is correct
10 Correct 144 ms 4584 KB Output is correct
11 Correct 146 ms 4544 KB Output is correct
12 Correct 151 ms 4608 KB Output is correct
13 Correct 15 ms 4300 KB Output is correct
14 Correct 63 ms 4588 KB Output is correct
15 Correct 66 ms 4548 KB Output is correct
16 Correct 64 ms 4604 KB Output is correct

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1080 ms 9048 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 4564 KB Output is correct
2 Correct 5 ms 3360 KB Output is correct
3 Correct 421 ms 10784 KB Output is correct
4 Correct 4 ms 3332 KB Output is correct
5 Correct 604 ms 11604 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 1 ms 2684 KB Output is correct
8 Correct 126 ms 9368 KB Output is correct
9 Correct 138 ms 9244 KB Output is correct
10 Correct 395 ms 10780 KB Output is correct
11 Correct 366 ms 10944 KB Output is correct
12 Correct 418 ms 10860 KB Output is correct
13 Correct 1 ms 2656 KB Output is correct
14 Correct 2 ms 2644 KB Output is correct
15 Correct 1 ms 2644 KB Output is correct
16 Correct 1 ms 2644 KB Output is correct
17 Correct 1 ms 2644 KB Output is correct
18 Correct 1 ms 2644 KB Output is correct
19 Correct 429 ms 11612 KB Output is correct
20 Correct 381 ms 11420 KB Output is correct
21 Correct 485 ms 11464 KB Output is correct
22 Correct 389 ms 11396 KB Output is correct

Subtask #4
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 4552 KB Output is correct
2 Correct 2 ms 3284 KB Output is correct
3 Correct 109 ms 4620 KB Output is correct
4 Correct 122 ms 4632 KB Output is correct
5 Correct 7 ms 3284 KB Output is correct
6 Correct 4 ms 3412 KB Output is correct
7 Correct 1 ms 2644 KB Output is correct
8 Correct 1 ms 2644 KB Output is correct
9 Correct 2 ms 2680 KB Output is correct
10 Correct 144 ms 4584 KB Output is correct
11 Correct 146 ms 4544 KB Output is correct
12 Correct 151 ms 4608 KB Output is correct
13 Correct 15 ms 4300 KB Output is correct
14 Correct 63 ms 4588 KB Output is correct
15 Correct 66 ms 4548 KB Output is correct
16 Correct 64 ms 4604 KB Output is correct
17 Execution timed out 1080 ms 9048 KB Time limit exceeded
18 Halted 0 ms 0 KB -