oj.uz

답안 #1065775

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1065775 2024-08-19T11:38:22 Z alexdd 은하철도 (APIO24_train) C++17
10 / 100
 1000 ms 64480 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] + (long long)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);
    }
    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)

*/

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 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 3 ms 7516 KB Correct.
5 Correct 1 ms 7260 KB Correct.
6 Correct 1 ms 7260 KB Correct.
7 Correct 1 ms 7260 KB Correct.

Subtask #2
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 167 ms 34644 KB Correct.
2 Correct 172 ms 36836 KB Correct.
3 Correct 1 ms 7256 KB Correct.
4 Correct 8 ms 8536 KB Correct.
5 Correct 1 ms 7260 KB Correct.
6 Correct 137 ms 33860 KB Correct.
7 Correct 1 ms 7260 KB Correct.
8 Correct 93 ms 25796 KB Correct.
9 Correct 171 ms 36552 KB Correct.

Subtask #3
0.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 167 ms 34644 KB Correct.
2 Correct 172 ms 36836 KB Correct.
3 Correct 1 ms 7256 KB Correct.
4 Correct 8 ms 8536 KB Correct.
5 Correct 1 ms 7260 KB Correct.
6 Correct 137 ms 33860 KB Correct.
7 Correct 1 ms 7260 KB Correct.
8 Correct 93 ms 25796 KB Correct.
9 Correct 171 ms 36552 KB Correct.
10 Correct 311 ms 55352 KB Correct.
11 Correct 281 ms 64480 KB Correct.
12 Correct 9 ms 9052 KB Correct.
13 Correct 1 ms 7260 KB Correct.
14 Execution timed out 1070 ms 59360 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #4
0.0 / 60.0

# 결과 실행 시간 메모리 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 3 ms 7516 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 167 ms 34644 KB Correct.
9 Correct 172 ms 36836 KB Correct.
10 Correct 1 ms 7256 KB Correct.
11 Correct 8 ms 8536 KB Correct.
12 Correct 1 ms 7260 KB Correct.
13 Correct 137 ms 33860 KB Correct.
14 Correct 1 ms 7260 KB Correct.
15 Correct 93 ms 25796 KB Correct.
16 Correct 171 ms 36552 KB Correct.
17 Correct 311 ms 55352 KB Correct.
18 Correct 281 ms 64480 KB Correct.
19 Correct 9 ms 9052 KB Correct.
20 Correct 1 ms 7260 KB Correct.
21 Execution timed out 1070 ms 59360 KB Time limit exceeded
22 Halted 0 ms 0 KB -