oj.uz

Submission #806702

# Submission time Handle Problem Language Result Execution time Memory
806702 2023-08-04T09:00:50 Z vjudge1 Robot (JOI21_ho_t4) C++17
0 / 100
 173 ms 22824 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] = {} , a[N] = {}, dp[N] = {}, b[N] , c[N];

struct edge{
    ll a , b , c , d;
};

vector<edge>v[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;
        if(m == 1 && min(x , y) == 1 && max(x , y) == n)
            s = 1;
        v[x].pb({y , l , r , 1000000000000000000});
        v[y].pb({x , l , r , 1000000000000000000});
    }
    if(m == 1){
        if(s == 1)
            cout<<0;
        else
            cout<<-1;
        return;
    }
    for(i = 1; i <= n; i++){
        set<pair<ll,ll>>st;
        for(auto to : v[i])
            b[to.b] += to.c;
        for(auto to : v[i])
            st.insert({b[to.b] , to.b});
        j = 0;
        for(auto to : v[i]){
            v[i][j].d = to.d;
            v[i][j].d = b[to.b] - to.c;
            if(st.size() != m)
                v[i][j].d = min(v[i][j].d , to.c);
            else {
                st.erase({b[to.b] , to.b});
                if(st.size())
                    v[i][j].d = min(v[i][j].d , st.begin()->fi);
                st.insert({b[to.b] , to.b});
            }
            j++;
        }
        for(auto to : v[i])
            b[to.b] = 0;
    }
    set<pair<ll,ll>>st;
    for(i = 1; i <= n; i++)
        d[i] = 1e18;
    st.insert({0 , 1});
    d[1] = 0;
    while(!st.empty()){
        auto it = st.begin();
        x = it->fi , y = it->se;
        st.erase(it);
        if(d[y] < x)
            continue;
        for(auto to : v[y])
            if(d[y] + to.d < d[to.a]){
                d[to.a] = to.d + d[y];
                st.insert({d[to.a] , to.a});
            }
    }
    if(d[n] > 1e16)
        d[n] = -1;
    cout<<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:60:26: warning: comparison of integer expressions of different signedness: 'std::set<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   60 |             if(st.size() != m)
      |                ~~~~~~~~~~^~~~
Main.cpp:34:8: warning: unused variable 'q' [-Wunused-variable]
   34 |     ll q , i , j , m ,n, z ,s = 0 , f , l , r , k , x , y , mn  = 1e18 , mx = 0;
      |        ^
Main.cpp:34:26: warning: unused variable 'z' [-Wunused-variable]
   34 |     ll q , i , j , m ,n, z ,s = 0 , f , l , r , k , x , y , mn  = 1e18 , mx = 0;
      |                          ^
Main.cpp:34:37: warning: unused variable 'f' [-Wunused-variable]
   34 |     ll q , i , j , m ,n, z ,s = 0 , f , l , r , k , x , y , mn  = 1e18 , mx = 0;
      |                                     ^
Main.cpp:34:49: warning: unused variable 'k' [-Wunused-variable]
   34 |     ll q , i , j , m ,n, z ,s = 0 , f , l , r , k , x , y , mn  = 1e18 , mx = 0;
      |                                                 ^
Main.cpp:34:61: warning: unused variable 'mn' [-Wunused-variable]
   34 |     ll q , i , j , m ,n, z ,s = 0 , f , l , r , k , x , y , mn  = 1e18 , mx = 0;
      |                                                             ^~
Main.cpp:34:74: warning: unused variable 'mx' [-Wunused-variable]
   34 |     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 2 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Correct 1 ms 2644 KB Output is correct
5 Correct 1 ms 2644 KB Output is correct
6 Correct 1 ms 2644 KB Output is correct
7 Correct 2 ms 2772 KB Output is correct
8 Correct 1 ms 2644 KB Output is correct
9 Incorrect 2 ms 2900 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 10816 KB Output is correct
2 Correct 20 ms 6404 KB Output is correct
3 Correct 71 ms 16712 KB Output is correct
4 Correct 29 ms 8172 KB Output is correct
5 Incorrect 173 ms 22824 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Correct 1 ms 2644 KB Output is correct
5 Correct 1 ms 2644 KB Output is correct
6 Correct 1 ms 2644 KB Output is correct
7 Correct 2 ms 2772 KB Output is correct
8 Correct 1 ms 2644 KB Output is correct
9 Incorrect 2 ms 2900 KB Output isn't correct
10 Halted 0 ms 0 KB -