oj.uz

Submission #993167

# Submission time Handle Problem Language Result Execution time Memory
993167 2024-06-05T11:56:14 Z boris_mihov Train (APIO24_train) C++17
5 / 100
 1000 ms 950628 KB 
#include "train.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <queue>

typedef long long llong;
const int MAXN = 100000 + 10;
const llong INF = 4e18;
const int INTINF = 2e9;

int n, m, w;
struct Edge
{
    int from;
    int to;
    int cost;
    int begTime;
    int endTime;
};

Edge edges[MAXN];
struct Interval
{
    int from, to, cost;
};

std::vector <std::pair <int,int>> intervals;
std::vector <std::pair <int,llong>> g[MAXN];
std::vector <int> begining[MAXN];
std::vector <int> ending[MAXN];
llong dist[MAXN];
bool vis[MAXN];
int t[MAXN];

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)
{
    n = N; m = M; w = W;
    for (int i = 0 ; i < m ; ++i)
    {
        X[i]++;
        Y[i]++;
        edges[i + 1] = {X[i], Y[i], C[i], A[i], B[i]};
        begining[X[i]].push_back(i + 1);
        ending[Y[i]].push_back(i + 1);
    }

    for (int i = 1 ; i <= n ; ++i)
    {
        t[i] = T[i - 1];
    }

    for (int i = 0 ; i < w ; ++i)
    {
        intervals.push_back({L[i], R[i]});
    }
    
    for (int i = 1 ; i <= n ; ++i)
    {
        for (const int &from : ending[i])
        {
            for (const int &to : begining[i])
            {
                if (edges[from].endTime <= edges[to].begTime)
                {
                    int count = 0;
                    for (const auto &[l, r] : intervals)
                    {
                        count += (edges[from].endTime < l && r < edges[to].begTime);
                    }

                    g[from].push_back({to, 1LL * count * t[i] + edges[to].cost});
                }
            }
        }
    }

    std::fill(dist + 1, dist + 1 + m, INF);
    std::priority_queue <std::pair <llong,int>> pq;
    for (const int &idx : begining[1])
    {
        int count = 0;
        for (const auto &[l, r] : intervals)
        {
            count += (r < edges[idx].begTime);
        }

        dist[idx] = edges[idx].cost + 1LL * count * t[1];
        pq.push({-dist[idx], idx});
    }

    while (pq.size())
    {
        auto [d, node] = pq.top();
        pq.pop();


        if (vis[node])
        {
            continue;
        }

        vis[node] = true;
        for (const auto &[u, ed] : g[node])
        {
            if (dist[u] > dist[node] + ed)
            {
                dist[u] = dist[node] + ed;
                pq.push({-dist[u], u});
            }
        }
    }

    llong min = INF;
    for (const auto &idx : ending[n])
    {
        int count = 0;
        for (const auto &[l, r] : intervals)
        {
            count += (edges[idx].endTime < l);
        }

        min = std::min(min, dist[idx] + 1LL * t[n] * count);
    }

	if (min == INF) return -1;
    return min;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 9048 KB Correct.
2 Correct 3 ms 8540 KB Correct.
3 Correct 2 ms 8540 KB Correct.
4 Correct 2 ms 8796 KB Correct.
5 Correct 1 ms 8540 KB Correct.
6 Correct 1 ms 8540 KB Correct.
7 Correct 2 ms 8540 KB Correct.

Subtask #2
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 32464 KB Correct.
2 Correct 74 ms 23380 KB Correct.
3 Correct 1 ms 8540 KB Correct.
4 Correct 8 ms 9564 KB Correct.
5 Correct 1 ms 8536 KB Correct.
6 Correct 207 ms 156772 KB Correct.
7 Correct 1 ms 8536 KB Correct.
8 Execution timed out 1092 ms 950628 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #3
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 32464 KB Correct.
2 Correct 74 ms 23380 KB Correct.
3 Correct 1 ms 8540 KB Correct.
4 Correct 8 ms 9564 KB Correct.
5 Correct 1 ms 8536 KB Correct.
6 Correct 207 ms 156772 KB Correct.
7 Correct 1 ms 8536 KB Correct.
8 Execution timed out 1092 ms 950628 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 9048 KB Correct.
2 Correct 3 ms 8540 KB Correct.
3 Correct 2 ms 8540 KB Correct.
4 Correct 2 ms 8796 KB Correct.
5 Correct 1 ms 8540 KB Correct.
6 Correct 1 ms 8540 KB Correct.
7 Correct 2 ms 8540 KB Correct.
8 Correct 95 ms 32464 KB Correct.
9 Correct 74 ms 23380 KB Correct.
10 Correct 1 ms 8540 KB Correct.
11 Correct 8 ms 9564 KB Correct.
12 Correct 1 ms 8536 KB Correct.
13 Correct 207 ms 156772 KB Correct.
14 Correct 1 ms 8536 KB Correct.
15 Execution timed out 1092 ms 950628 KB Time limit exceeded
16 Halted 0 ms 0 KB -