Submission #806692

#	Time	Username	Problem	Language	Result	Execution time	Memory
806692		vjudge1	Event Hopping 2 (JOI21_event2)	C++17	0 / 100	4 ms	5204 KiB

event2

#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;
            if(m != 1)
                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 (stderr)

event2.cpp: In function 'void solve()':
event2.cpp:61: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]
   61 |             if(st.size() != m)
      |                ~~~~~~~~~~^~~~
event2.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;
      |        ^
event2.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;
      |                          ^
event2.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;
      |                                     ^
event2.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;
      |                                                 ^
event2.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;
      |                                                             ^~
event2.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 / 7
• Subtask 2: 0 / 1
• Subtask 3: 0 / 31
• Subtask 4: 0 / 61