oj.uz

Submission #992260

# Submission time Handle Problem Language Result Execution time Memory
992260 2024-06-04T07:49:33 Z ASGA_RedSea Train (APIO24_train) C++17
10 / 100
 1000 ms 13920 KB 
/**

                                    * بسم الله الرحمن الرحيم *

                ﴾ رَبِّ اشْرَحْ لِي صَدْرِي * وَيَسِّرْ لِي أَمْرِي * وَاحْلُلْ عُقْدَةً مِّن لِّسَانِي * يَفْقَهُوا قَوْلِي ﴿

*/

/// author : "ASGA"

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const ll inf = 1e18;

ll solve(int n,int m,int w,vector <int> TT,vector <int> x,vector <int> y,vector <int> A,vector <int> B,vector <int> C,vector <int> l,vector <int> r){
    vector <ll> T;for(auto& i : TT)T.push_back(i);
    if(w <= 60){
        vector <vector <array <ll,4>>> a(n);
        for(int i = 0;i < m;i++){
            a[x[i]].push_back({y[i],A[i],B[i],C[i]});
        }

        vector <ll> d(n,inf);
        vector <int> v(n,0);

        priority_queue <array <ll,4>,vector <array <ll,4>>,greater <array <ll,4>>> q;
        v[0] = 1;
        d[0] = 0;
        q.push({0,0,0,0});

        ll ans = inf;

        while(!q.empty()){
            ll i = q.top()[3];
            ll t = q.top()[1];
            ll tm = q.top()[2];
            ll cost,ntm;

            q.pop();

            for(auto& j : a[i]){
                if(t <= j[1]){
                    ntm = tm;cost = 0;
                    for(int k = 0;k < w;k++){
                        if(((ntm >> k) & 1) == 0){
                            if(r[k] >= j[1] && l[k] <= j[2]){
                                ntm += (1 << k);
                            }
                            else if(t <= l[k] && r[k] < j[1]){
                                ntm += (1 << k);
                                cost += T[i];
                            }
                        }
                    }

                    if(j[0] == n - 1){
                        ll sum = 0;
                        for(int k = 0;k < w;k++){
                            if(((ntm >> k) & 1) == 0)sum += ll(T.back());
                        }
                        ans = min(ans,cost + d[i] + j[3] + sum);
                    }

                    d[j[0]] = min(d[j[0]],d[i] + j[3] + cost);

                    if(v[j[0]] == 0){
                        v[j[0]] = 1;
                        q.push({d[j[0]],j[2],ntm,j[0]});
                    }
                }
            }
        }

        return (ans == inf ? -1 : ans);
    }
    else{
        vector <vector <array <ll,4>>> a(n);
        for(int i = 0;i < m;i++){
            a[x[i]].push_back({y[i],A[i],B[i],C[i]});
        }

        vector <pair <int,int>> meal(w);
        for(int i = 0;i < w;i++)meal[i] = {l[i],r[i]};

        sort(meal.begin(),meal.end());

        vector <ll> d(n,inf);
        vector <int> v(n,0);

        priority_queue <array <ll,4>,vector <array <ll,4>>,greater <array <ll,4>>> q;
        v[0] = 1;
        d[0] = 0;
        q.push({0,0,0,0});

        ll ans = inf;

        while(!q.empty()){
            ll i = q.top()[3];
			ll cur = -q.top()[1];
            ll t = q.top()[2];
            
            ll cost,cur_1;

            q.pop();

            for(auto& j : a[i]){
                if(t <= j[1]){
                    cur_1 = cur;cost = 0;
                    while(cur_1 < w && t <= meal[cur_1].first && meal[cur_1].second < j[1]){cur_1++;cost += T[i];}
                    while(cur_1 < w && meal[cur_1].second >= j[1] && meal[cur_1].first <= j[2]){cur_1++;}

                    if(j[0] == n - 1){
                        ans = min(ans,cost + d[i] + j[3] + ((ll(w) - cur_1) * T[n-1]));
                    }

                    d[j[0]] = min(d[j[0]],d[i] + j[3] + cost);

                    if(v[j[0]] == 0){
                        v[j[0]] = 1;
                        q.push({d[j[0]],-cur_1,j[2],j[0]});
                    }
                }
            }
        }

        return (ans == inf ? -1 : ans);
    }

    return -1;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Correct.
2 Correct 1 ms 348 KB Correct.
3 Correct 1 ms 536 KB Correct.
4 Correct 0 ms 348 KB Correct.
5 Correct 0 ms 348 KB Correct.
6 Correct 0 ms 348 KB Correct.
7 Correct 0 ms 344 KB Correct.

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 9592 KB Correct.
2 Correct 74 ms 13836 KB Correct.
3 Correct 0 ms 344 KB Correct.
4 Correct 9 ms 5304 KB Correct.
5 Correct 0 ms 348 KB Correct.
6 Correct 33 ms 10080 KB Correct.
7 Correct 0 ms 348 KB Correct.
8 Correct 39 ms 12748 KB Correct.
9 Correct 61 ms 13920 KB Correct.

Subtask #3
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 9592 KB Correct.
2 Correct 74 ms 13836 KB Correct.
3 Correct 0 ms 344 KB Correct.
4 Correct 9 ms 5304 KB Correct.
5 Correct 0 ms 348 KB Correct.
6 Correct 33 ms 10080 KB Correct.
7 Correct 0 ms 348 KB Correct.
8 Correct 39 ms 12748 KB Correct.
9 Correct 61 ms 13920 KB Correct.
10 Execution timed out 1039 ms 12444 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Correct.
2 Correct 1 ms 348 KB Correct.
3 Correct 1 ms 536 KB Correct.
4 Correct 0 ms 348 KB Correct.
5 Correct 0 ms 348 KB Correct.
6 Correct 0 ms 348 KB Correct.
7 Correct 0 ms 344 KB Correct.
8 Correct 40 ms 9592 KB Correct.
9 Correct 74 ms 13836 KB Correct.
10 Correct 0 ms 344 KB Correct.
11 Correct 9 ms 5304 KB Correct.
12 Correct 0 ms 348 KB Correct.
13 Correct 33 ms 10080 KB Correct.
14 Correct 0 ms 348 KB Correct.
15 Correct 39 ms 12748 KB Correct.
16 Correct 61 ms 13920 KB Correct.
17 Execution timed out 1039 ms 12444 KB Time limit exceeded
18 Halted 0 ms 0 KB -