# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
1065771 |
2024-08-19T11:35:59 Z |
alexdd |
Train (APIO24_train) |
C++17 |
|
316 ms |
55420 KB |
#include "train.h"
#include <bits/stdc++.h>
using namespace std;
const long long LIM = 100;
const long long INF = 1e14;
struct train
{
int from,to;
int tin,tout;
int cost;
};
bool cmp_trains(train x, train y)
{
return x.tin < y.tin;
}
bool cmp_meals(pair<int,int> x, pair<int,int> y)
{
return x.second < y.second;
}
vector<train> trains;
bool cmp_tout(int x, int y)
{
return trains[x].tout < trains[y].tout;
}
vector<pair<int,int>> meals;
long long dp[100005];
vector<int> meal_cost;
vector<int> train_ends[100005];
bool isbig[100005];
int cntin[100005],cntout[100005];
vector<int> big_nodes;
long long prec[100005];
long long calced[100005],inplus[100005];
vector<int> ids_tout;
int poz_meals=-1,cate;
int aib[400005];
int qry_aib(int poz)
{
int aux=0;
for(int i=poz;i<=cate;i+=(i&(-i)))
aux += aib[i];
return aux;
}
void upd_aib(int poz, int newv)
{
for(int i=poz;i>0;i-=(i&(-i)))
aib[i] += newv;
}
void solve_small(int i)
{
for(int j:train_ends[trains[i].from])
{
if(trains[j].tout <= trains[i].tin)
{
if(dp[j] < dp[i]) dp[i] = min(dp[i], dp[j] + qry_aib(trains[j].tout+1)*meal_cost[trains[i].from] + trains[i].cost);
}
}
}
void solve_big(int i)
{
assert(isbig[trains[i].from]);
dp[i] = min(dp[i], prec[trains[i].from] + trains[i].cost);
}
void baga_big(int id)
{
for(int x:big_nodes)
{
prec[x]=INF;
for(int y:train_ends[x])
{
if(meals[id].first > trains[y].tout)
{
inplus[y] = min(INF, inplus[y] + meal_cost[x]);
calced[y] = min(INF, calced[y] + meal_cost[x]);
}
prec[x] = min(prec[x], calced[y]);
}
}
}
void update_big(int i, int W)
{
while(poz_meals+1 < W && meals[poz_meals+1].second < trains[i].tin)
{
poz_meals++;
baga_big(poz_meals);
upd_aib(meals[poz_meals].first,+1);
}
}
map<int,int> mp,nrm;
void normalizeaza(int M, int W)
{
for(int i=0;i<M;i++)
{
mp[trains[i].tin]++;
mp[trains[i].tout]++;
}
for(int i=0;i<W;i++)
{
mp[meals[i].first]++;
mp[meals[i].second]++;
}
for(auto it:mp)
if(it.second)
nrm[it.first]=++cate;
assert(cate<=400000);
for(int i=0;i<M;i++)
{
trains[i].tin = nrm[trains[i].tin];
trains[i].tout = nrm[trains[i].tout];
}
for(int i=0;i<W;i++)
{
meals[i].first = nrm[meals[i].first];
meals[i].second = nrm[meals[i].second];
}
}
long long solve(int N, int M, int W, std::vector<int> T, std::vector<int> X, std::vector<int> Y,
std::vector<int> A, std::vector<int> B, std::vector<int> C, std::vector<int> L,
std::vector<int> R)
{
meal_cost = T;
for(int i=0;i<M;i++)
{
trains.push_back({X[i],Y[i],A[i],B[i],C[i]});
cntin[trains[i].to]++;
cntout[trains[i].from]++;
calced[i]=INF;
ids_tout.push_back(i);
}
for(int i=0;i<W;i++)
{
meals.push_back({L[i],R[i]});
}
sort(trains.begin(),trains.end(),cmp_trains);
sort(meals.begin(),meals.end(),cmp_meals);
sort(ids_tout.begin(),ids_tout.end(),cmp_tout);
for(int i=0;i<M;i++)
train_ends[trains[i].to].push_back(i);
normalizeaza(M,W);
for(int i=0;i<N;i++)
{
if(cntin[i]+cntout[i] > LIM)
{
isbig[i]=1;
big_nodes.push_back(i);
prec[i]=INF;
}
}
int poz_tout=-1;
for(int i=0;i<M;i++)
{
while(poz_tout+1 < (int)ids_tout.size() && trains[ids_tout[poz_tout+1]].tout <= trains[i].tin)
{
poz_tout++;
int aux = ids_tout[poz_tout];
calced[aux] = dp[aux]+inplus[aux];
if(isbig[trains[aux].to]) prec[trains[aux].to] = min(prec[trains[aux].to], calced[aux]);
}
update_big(i,W);
dp[i]=INF;
if(trains[i].from==0)
{
dp[i] = min(dp[i], (long long)(poz_meals+1)*meal_cost[trains[i].from] + trains[i].cost);
}
if(isbig[trains[i].from])
solve_big(i);
else
solve_small(i);
}
long long rez=INF;
for(int i=0;i<M;i++)
{
if(trains[i].to==N-1)
{
long long cnt=0;
for(auto [x,y]:meals)
if(x > trains[i].tout)
cnt++;
rez = min(rez, dp[i] + cnt*meal_cost[N-1]);
}
}
if(rez==INF)
return -1;
else
return rez;
}
/**
dp[i] = costul minim de a parcurge o ruta care incepe la nodul 0, a.i. ultimul tren luat sa fie i (cumparam un meal doar daca e obligatoriu)
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
7516 KB |
Correct. |
2 |
Correct |
2 ms |
7516 KB |
Correct. |
3 |
Correct |
2 ms |
7516 KB |
Correct. |
4 |
Correct |
2 ms |
7512 KB |
Correct. |
5 |
Correct |
1 ms |
7260 KB |
Correct. |
6 |
Correct |
1 ms |
7260 KB |
Correct. |
7 |
Correct |
1 ms |
7260 KB |
Correct. |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
182 ms |
34176 KB |
Correct. |
2 |
Correct |
175 ms |
36808 KB |
Correct. |
3 |
Correct |
1 ms |
7256 KB |
Correct. |
4 |
Correct |
7 ms |
8596 KB |
Correct. |
5 |
Correct |
1 ms |
7512 KB |
Correct. |
6 |
Correct |
148 ms |
33676 KB |
Correct. |
7 |
Correct |
1 ms |
7256 KB |
Correct. |
8 |
Correct |
96 ms |
25828 KB |
Correct. |
9 |
Correct |
169 ms |
36044 KB |
Correct. |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
182 ms |
34176 KB |
Correct. |
2 |
Correct |
175 ms |
36808 KB |
Correct. |
3 |
Correct |
1 ms |
7256 KB |
Correct. |
4 |
Correct |
7 ms |
8596 KB |
Correct. |
5 |
Correct |
1 ms |
7512 KB |
Correct. |
6 |
Correct |
148 ms |
33676 KB |
Correct. |
7 |
Correct |
1 ms |
7256 KB |
Correct. |
8 |
Correct |
96 ms |
25828 KB |
Correct. |
9 |
Correct |
169 ms |
36044 KB |
Correct. |
10 |
Incorrect |
316 ms |
55420 KB |
Integer -72951945841 violates the range [-1, 10^18] |
11 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
7516 KB |
Correct. |
2 |
Correct |
2 ms |
7516 KB |
Correct. |
3 |
Correct |
2 ms |
7516 KB |
Correct. |
4 |
Correct |
2 ms |
7512 KB |
Correct. |
5 |
Correct |
1 ms |
7260 KB |
Correct. |
6 |
Correct |
1 ms |
7260 KB |
Correct. |
7 |
Correct |
1 ms |
7260 KB |
Correct. |
8 |
Correct |
182 ms |
34176 KB |
Correct. |
9 |
Correct |
175 ms |
36808 KB |
Correct. |
10 |
Correct |
1 ms |
7256 KB |
Correct. |
11 |
Correct |
7 ms |
8596 KB |
Correct. |
12 |
Correct |
1 ms |
7512 KB |
Correct. |
13 |
Correct |
148 ms |
33676 KB |
Correct. |
14 |
Correct |
1 ms |
7256 KB |
Correct. |
15 |
Correct |
96 ms |
25828 KB |
Correct. |
16 |
Correct |
169 ms |
36044 KB |
Correct. |
17 |
Incorrect |
316 ms |
55420 KB |
Integer -72951945841 violates the range [-1, 10^18] |
18 |
Halted |
0 ms |
0 KB |
- |