oj.uz

답안 #993190

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
993190 2024-06-05T12:27:20 Z boris_mihov 은하철도 (APIO24_train) C++17
5 / 100
 229 ms 39172 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;
};
 
int father[MAXN];
int father2[MAXN];
std::vector <std::pair <int,int>> intervals;
std::vector <std::pair <int,llong>> g[3 * MAXN];
std::vector <int> begining[MAXN];
std::vector <int> ending[MAXN];
llong dist[3 * MAXN];
bool vis[3 * MAXN];
int t[MAXN];
 
int intervalsToMeBeg(int value)
{
    int l = -1, r = intervals.size(), mid;
    while (l < r - 1)
    {
        mid = l + r >> 1;
        if (intervals[mid].second < value) l = mid;
        else r = mid;
    }
 
    return r;
}
 
int intervalsToMeEnd(int value)
{
    int l = -1, r = intervals.size(), mid;
    while (l < r - 1)
    {
        mid = l + r >> 1;
        if (intervals[mid].first <= value) l = mid;
        else r = mid;
    }
 
    return r;
}
 
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];
    }
 
    std::sort(L.begin(), L.end());
    std::sort(R.begin(), R.end());
    intervals.push_back({0, 0});
    for (int i = 0 ; i < w ; ++i)
    {
        intervals.push_back({L[i], R[i]});
    }
    
    int cnt = m;
    int cnt2 = 2 * m;
    for (int i = 1 ; i <= n ; ++i)
    {
        std::sort(ending[i].begin(), ending[i].end(), [&](int x, int y)
        {
            return edges[x].endTime < edges[y].endTime;
        });
 
        std::sort(begining[i].begin(), begining[i].end(), [&](int x, int y)
        {
            return edges[x].begTime < edges[y].begTime;
        });
 
        for (int j = 0 ; j < begining[i].size() ; ++j)
        {
            father[begining[i][j]] = ++cnt;
            g[father[begining[i][j]]].push_back({begining[i][j], edges[begining[i][j]].cost + 1LL * intervalsToMeBeg(edges[begining[i][j]].begTime) * t[i]});
        }
 
        for (int j = 0 ; j + 1 < begining[i].size() ; ++j)
        {
            g[father[begining[i][j]]].push_back({father[begining[i][j + 1]], 0});
        }
 
        for (int j = 0 ; j < begining[i].size() ; ++j)
        {
            father2[begining[i][j]] = ++cnt2;
            g[father2[begining[i][j]]].push_back({begining[i][j], edges[begining[i][j]].cost});
        }
 
        for (int j = 0 ; j + 1 < begining[i].size() ; ++j)
        {
            g[father2[begining[i][j]]].push_back({father2[begining[i][j + 1]], 0});
        }
 
        int ptr = begining[i].size();
        for (int j = (int)ending[i].size() - 1 ; j >= 0 ; --j)
        {
            while (ptr > 0 && edges[begining[i][ptr - 1]].begTime >= edges[ending[i][j]].endTime)
            {
                ptr--;
            }
 
            if (ptr < begining[i].size()) 
            {
                int l = ptr - 1, r = begining[i].size(), mid;
                while (l < r - 1)
                {
                    mid = l + r >> 1;
                    if (intervalsToMeBeg(edges[begining[i][mid]].begTime) < intervalsToMeEnd(edges[ending[i][j]].endTime)) l = mid;
                    else r = mid;
                }
 
                if (l != ptr - 1) g[ending[i][j]].push_back({father2[begining[i][ptr]], 0});
                if (r != begining[i].size()) g[ending[i][j]].push_back({father[begining[i][r]], -1LL * intervalsToMeEnd(edges[ending[i][j]].endTime) * t[i]});
            }
        }
    }
 
    std::fill(dist + 1, dist + 1 + 3 * m, INF);
    std::priority_queue <std::pair <llong,int>> pq;
    for (const int &idx : begining[1])
    {
        int count = -1;
        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])
        {
            // std::cout << "cost: " << node << ' ' << u << " = " << ed << '\n';
            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 * count * t[n]);
    }
 
	if (min == INF) return -1;
    return min;
}

Compilation message

train.cpp: In function 'int intervalsToMeBeg(int)':
train.cpp:45:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   45 |         mid = l + r >> 1;
      |               ~~^~~
train.cpp: In function 'int intervalsToMeEnd(int)':
train.cpp:58:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   58 |         mid = l + r >> 1;
      |               ~~^~~
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:108:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |         for (int j = 0 ; j < begining[i].size() ; ++j)
      |                          ~~^~~~~~~~~~~~~~~~~~~~
train.cpp:114:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |         for (int j = 0 ; j + 1 < begining[i].size() ; ++j)
      |                          ~~~~~~^~~~~~~~~~~~~~~~~~~~
train.cpp:119:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  119 |         for (int j = 0 ; j < begining[i].size() ; ++j)
      |                          ~~^~~~~~~~~~~~~~~~~~~~
train.cpp:125:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  125 |         for (int j = 0 ; j + 1 < begining[i].size() ; ++j)
      |                          ~~~~~~^~~~~~~~~~~~~~~~~~~~
train.cpp:138:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  138 |             if (ptr < begining[i].size())
      |                 ~~~~^~~~~~~~~~~~~~~~~~~~
train.cpp:143:29: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  143 |                     mid = l + r >> 1;
      |                           ~~^~~
train.cpp:149:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  149 |                 if (r != begining[i].size()) g[ending[i][j]].push_back({father[begining[i][r]], -1LL * intervalsToMeEnd(edges[ending[i][j]].endTime) * t[i]});
      |                     ~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
0.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 16984 KB Correct.
2 Correct 3 ms 17240 KB Correct.
3 Correct 3 ms 16844 KB Correct.
4 Incorrect 3 ms 16988 KB Wrong Answer.
5 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 107 ms 36044 KB Correct.
2 Correct 137 ms 36944 KB Correct.
3 Correct 3 ms 14680 KB Correct.
4 Correct 10 ms 17764 KB Correct.
5 Correct 3 ms 16732 KB Correct.
6 Correct 105 ms 36552 KB Correct.
7 Correct 2 ms 16732 KB Correct.
8 Correct 105 ms 36528 KB Correct.
9 Correct 122 ms 37200 KB Correct.

Subtask #3
0.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 107 ms 36044 KB Correct.
2 Correct 137 ms 36944 KB Correct.
3 Correct 3 ms 14680 KB Correct.
4 Correct 10 ms 17764 KB Correct.
5 Correct 3 ms 16732 KB Correct.
6 Correct 105 ms 36552 KB Correct.
7 Correct 2 ms 16732 KB Correct.
8 Correct 105 ms 36528 KB Correct.
9 Correct 122 ms 37200 KB Correct.
10 Incorrect 229 ms 39172 KB Wrong Answer.
11 Halted 0 ms 0 KB -

Subtask #4
0.0 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 16984 KB Correct.
2 Correct 3 ms 17240 KB Correct.
3 Correct 3 ms 16844 KB Correct.
4 Incorrect 3 ms 16988 KB Wrong Answer.
5 Halted 0 ms 0 KB -