| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1065819 |
2024-08-19T12:01:55 Z |
alexdd |
Train (APIO24_train) |
C++17 |
|
165 ms |
64896 KB |
#include "train.h"
#include <bits/stdc++.h>
using namespace std;
const long long LIM = 0;
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;
vector<int> ids_tout;
int poz_meals=-1,cate;
int unde[100005];
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] + (long long)qry_aib(trains[j].tout+1)*meal_cost[trains[i].from] + trains[i].cost);
}
}
}
vector<pair<long long,long long>> aint[100005];///{val,lazy}
void build(int nod, int st, int dr, int c)
{
aint[c][nod] = {INF,0};
if(st==dr)
return;
int mij=(st+dr)/2;
build(nod*2,st,mij,c);
build(nod*2+1,mij+1,dr,c);
}
void propagate(int nod, int c)
{
if(!aint[c][nod].second)
return;
aint[c][nod*2].second+=aint[c][nod].second;
aint[c][nod*2+1].second+=aint[c][nod].second;
aint[c][nod*2].first+=aint[c][nod].second;
aint[c][nod*2+1].first+=aint[c][nod].second;
aint[c][nod].second=0;
}
void upd(int nod, int st, int dr, int le, int ri, int newv, int c)
{
if(le>ri)
return;
if(le==st && dr==ri)
{
aint[c][nod].first += newv;
aint[c][nod].second += newv;
return;
}
propagate(nod,c);
int mij=(st+dr)/2;
upd(nod*2,st,mij,le,min(mij,ri),newv,c);
upd(nod*2+1,mij+1,dr,max(mij+1,le),ri,newv,c);
aint[c][nod].first = min(aint[c][nod*2].first, aint[c][nod*2+1].first);
}
void upd_poz(int nod, int st, int dr, int poz, int newv, int c)
{
if(st==dr)
{
aint[c][nod].first = newv;
return;
}
propagate(nod,c);
int mij=(st+dr)/2;
if(poz<=mij) upd_poz(nod*2,st,mij,poz,newv,c);
else upd_poz(nod*2+1,mij+1,dr,poz,newv,c);
aint[c][nod].first = min(aint[c][nod*2].first, aint[c][nod*2+1].first);
}
void solve_big(int i)
{
assert(isbig[trains[i].from]);
dp[i] = min(dp[i], aint[trains[i].from][1].first + trains[i].cost);
}
void baga_big(int id)
{
for(int x:big_nodes)
{
for(int i=0;i<train_ends[x].size();i++)
{
int y = train_ends[x][i];
if(trains[y].tout >= meals[id].first)
break;
upd(1,0,cntin[x]-1,i,i,meal_cost[x],x);
//calced[y] = min(INF, calced[y] + meal_cost[x]);
}
}
}
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]++;
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)
{
assert(cntin[i]==(int)train_ends[i].size());
sort(train_ends[i].begin(),train_ends[i].end(),cmp_tout);
for(int j=0;j<train_ends[i].size();j++)
unde[train_ends[i][j]]=j;
isbig[i]=1;
big_nodes.push_back(i);
aint[i].resize(10*cntin[i]+2);
build(1,0,cntin[i]-1,i);
}
}
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];
//if(isbig[trains[aux].to]) prec[trains[aux].to] = min(prec[trains[aux].to], calced[aux]);
if(isbig[trains[aux].to]) upd_poz(1,0,cntin[trains[aux].to]-1,unde[aux],dp[aux],trains[aux].to);
}
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);
}
while(poz_meals+1 < W)
{
poz_meals++;
upd_aib(meals[poz_meals].first,+1);
}
long long rez=INF;
for(int i=0;i<M;i++)
{
if(trains[i].to==N-1)
{
rez = min(rez, dp[i] + (long long)qry_aib(trains[i].tout+1)*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)
*/
Compilation message
train.cpp: In function 'void baga_big(int)':
train.cpp:121:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
121 | for(int i=0;i<train_ends[x].size();i++)
| ~^~~~~~~~~~~~~~~~~~~~~
train.cpp: In function 'long long int solve(int, int, int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
train.cpp:196:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
196 | for(int j=0;j<train_ends[i].size();j++)
| ~^~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
5468 KB |
Correct. |
| 2 |
Runtime error |
6 ms |
10332 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
165 ms |
64896 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
165 ms |
64896 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
5468 KB |
Correct. |
| 2 |
Runtime error |
6 ms |
10332 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
