제출 #992260

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
992260		ASGA_RedSea	은하철도 (APIO24_train)	C++17	10 / 100	1039 ms	13920 KiB

train

/**

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

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

*/

/// 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 / 5
• Subtask 2: 5 / 5
• Subtask 3: 0 / 30
• Subtask 4: 0 / 60