oj.uz

Submission #846997

# Submission time Handle Problem Language Result Execution time Memory
846997 2023-09-08T23:35:50 Z smirichto Robot (JOI21_ho_t4) C++17
0 / 100
 150 ms 27496 KB 
#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef long double ld;
#define pb push_back
#define pi pair<ll,ll>
#define F first
#define S second
#define all(x) (x).begin(), (x).end()
#define alll(x) ((x).begin()+1), (x).end()
#define clean(v) (v).resize(distance((v).begin(), unique(all(v))));
#define yes cout<<"Yes"<<endl;
#define no cout<<"No"<<endl;
#define mod mod
#define endl '\n'
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll mod = 998244353;

void io() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
}

template<class T>
bool ckmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }

template<class T>
bool ckmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }

void nop() {
    cout << -1 << endl;
    return;
}

const ll N = 2e5+5 ;
vector<array<ll,4>> adj[N] ;

void solve() {
    ll n , m ;
    cin>>n>>m ;
    for(ll i = 1 ; i<=m ; i++){
        ll u , v , c , p ;
        cin>>u>>v>>c>>p ;
        adj[u].pb({v , c , p}) ;
        adj[v].pb({u , c, p}) ;
    }
    priority_queue<array<ll , 2> , vector<array<ll,2>> , greater<>> pq ;
    pq.push({ 0 , 1}) ;
    vector<ll> dist(n+1 , 1e17) ;
    vector<ll> sum(m+1) ;
    dist[1] = 0 ;
    while(!pq.empty()){
        auto a = pq.top() ; pq.pop() ;
        ll node = a[1] , w = a[0] ;
        if(dist[node]!=w) continue;
        for(auto p : adj[node]){
            ll col = p[1] , cost = p[2] ;
            sum[col] += cost ;
        }
        set<pi> s ;
        for(auto p : adj[node]){
            ll col = p[1];
            s.insert({sum[col] , col}) ;
        }

        for(auto p : adj[node]){
            ll to = p[0] , col = p[1] , cost = p[2] ;
            ll d = sum[col] - cost ;
            auto it = s.begin() ;
            if(it->second != col) ckmin(d , it->first + cost) ;
            if(s.size()>1){
                ++it ;
                if(it->second != col) ckmin(d , it->first + cost) ;
            }
            if(s.size()<m) ckmin(d , (ll)cost) ;
            if(ckmin(dist[to] , d + w)){
                pq.push({dist[to] , to}) ;
            }
        }

        for(auto p : adj[node]){
            ll col = p[1] , cost = p[2] ;
            sum[col] -= cost ;
        }
    }
    ll ans = dist[n] ;
    if(ans>=1e17) ans = -1 ;
    cout<<ans<<endl;
}

int main() {
//#ifndef ONLINE_JUDGE
//    freopen("input.in", "r", stdin);
//    freopen("output.out", "w", stdout);
//#endif
    io();
    ll tt = 1;
    //cin>>tt ;
    while (tt--) {
        solve();
    }

    return 0;
}

Compilation message

Main.cpp: In function 'void solve()':
Main.cpp:76:24: 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 'll' {aka 'long long int'} [-Wsign-compare]
   76 |             if(s.size()<m) ckmin(d , (ll)cost) ;
      |                ~~~~~~~~^~

Subtask #1
0 / 34.0

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

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 13936 KB Output is correct
2 Correct 18 ms 9048 KB Output is correct
3 Correct 55 ms 20688 KB Output is correct
4 Correct 25 ms 11088 KB Output is correct
5 Incorrect 150 ms 27496 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 4952 KB Output is correct
2 Correct 1 ms 4956 KB Output is correct
3 Correct 2 ms 4952 KB Output is correct
4 Correct 1 ms 4952 KB Output is correct
5 Correct 1 ms 4952 KB Output is correct
6 Correct 1 ms 4956 KB Output is correct
7 Correct 2 ms 5208 KB Output is correct
8 Correct 1 ms 5208 KB Output is correct
9 Incorrect 2 ms 5208 KB Output isn't correct
10 Halted 0 ms 0 KB -