oj.uz

Submission #806420

# Submission time Handle Problem Language Result Execution time Memory
806420 2023-08-04T06:39:19 Z vjudge1 Robot (JOI21_ho_t4) C++17
0 / 100
 166 ms 26556 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;
    set<pair<int,int>>st;
    for(i = 1; i <= m; i++){
        cin>>x>>y>>l>>r;
        v[x].pb({y , l , r , 1000000000});
        v[y].pb({x , l , r , 1000000000});
    }
    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]){
            to.d = b[to.b] - to.c;
            if(st.size() != m)
                to.d = min(to.d , to.c);
            else {
                st.erase({b[to.b] , to.b});
                if(st.size())
                    to.d = min(to.d , st.begin()->fi);
                st.insert({to.d , to.c});
            }
            v[i][j].d = to.d;
            j++;
        }
        for(auto to : v[i])
            b[to.b] = 0;
    }
    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;
        vector<pair<int,int>>vc;
        if(m == 1 && v[y].size() > 1)
            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] == 1e18)
        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:51: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]
   51 |             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:29: warning: unused variable 's' [-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 1 ms 2644 KB Output is correct
2 Correct 2 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 2 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2772 KB Output is correct
8 Correct 2 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 12056 KB Output is correct
2 Correct 19 ms 6760 KB Output is correct
3 Correct 56 ms 19192 KB Output is correct
4 Correct 28 ms 8840 KB Output is correct
5 Incorrect 166 ms 26556 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 2 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 2 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2772 KB Output is correct
8 Correct 2 ms 2644 KB Output is correct
9 Incorrect 2 ms 2900 KB Output isn't correct
10 Halted 0 ms 0 KB -