#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[2 * 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());
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)
{
father[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][l]], 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 = 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])
{
// 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:107:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
107 | for (int j = 0 ; j < begining[i].size() ; ++j)
| ~~^~~~~~~~~~~~~~~~~~~~
train.cpp:113:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
113 | for (int j = 0 ; j + 1 < begining[i].size() ; ++j)
| ~~~~~~^~~~~~~~~~~~~~~~~~~~
train.cpp:118:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
118 | for (int j = 0 ; j < begining[i].size() ; ++j)
| ~~^~~~~~~~~~~~~~~~~~~~
train.cpp:124:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
124 | for (int j = 0 ; j + 1 < begining[i].size() ; ++j)
| ~~~~~~^~~~~~~~~~~~~~~~~~~~
train.cpp:137:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
137 | if (ptr < begining[i].size())
| ~~~~^~~~~~~~~~~~~~~~~~~~
train.cpp:142:29: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
142 | mid = l + r >> 1;
| ~~^~~
train.cpp:148:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
148 | if (r != begining[i].size()) g[ending[i][j]].push_back({father[begining[i][r]], -1LL * intervalsToMeEnd(edges[ending[i][j]].endTime) * t[i]});
| ~~^~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
14936 KB |
Wrong Answer. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
71 ms |
31504 KB |
Wrong Answer. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
71 ms |
31504 KB |
Wrong Answer. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
14936 KB |
Wrong Answer. |
| 2 |
Halted |
0 ms |
0 KB |
- |
