/**
* بسم الله الرحمن الرحيم *
﴾ رَبِّ اشْرَحْ لِي صَدْرِي * وَيَسِّرْ لِي أَمْرِي * وَاحْلُلْ عُقْدَةً مِّن لِّسَانِي * يَفْقَهُوا قَوْلِي ﴿
*/
/// 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;
}
# |
결과 |
실행 시간 |
메모리 |
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. |
# |
결과 |
실행 시간 |
메모리 |
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. |
# |
결과 |
실행 시간 |
메모리 |
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 |
- |
# |
결과 |
실행 시간 |
메모리 |
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 |
- |