#include <bits/stdc++.h>
using namespace std;
using ii = pair<int, int>;
using ll = long long;
using pll = pair<ll, ll>;
const ll INF = 1e18;
#define X first
#define Y second
int n, m;
vector<ii> P;
vector<ii> G[1500007];
ll dist[1500007];
int add_point(int x, int y) {
P.emplace_back(x, y);
return P.size() - 1;
}
void add_edges(vector<int> &F, vector<int> &T) {
if(F.empty() || T.empty())
return ;
for(int f : F)
for(int t : T)
if(P[t].X >= P[f].X && P[t].Y <= P[f].Y)
G[f].emplace_back(t, 0);
}
ll dijkstra() {
ll res = INF;
set<pll> S;
for(int i = 0 ; i < P.size() ; i++) {
if(P[i].Y - P[i].X == 0) {
dist[i] = 0;
S.insert({0, i});
} else
dist[i] = INF;
}
while(!S.empty()) {
auto p = *(S.begin());
S.erase(S.begin());
for(auto p2 : G[p.Y]) {
if(dist[p2.X] > p.X + p2.Y) {
S.erase({dist[p2.X], p2.X});
dist[p2.X] = p.X + p2.Y;
S.insert({dist[p2.X], p2.X});
}
}
}
for(int i = 0 ; i < P.size() ; i++)
if(P[i].Y - P[i].X == n * 2)
res = min(res, dist[i]);
return res;
}
int main() {
scanf("%d%d", &n, &m);
vector<int> F, T;
for(int i = 0 ; i < m ; i++) {
int t, l, r, c;
scanf("%d%d%d%d", &t, &l, &r, &c);
l--;
F.push_back(add_point(t - r, t + r));
T.push_back(add_point(t - l, t + l));
G[T.back()].emplace_back(F.back(), c);
}
sort(F.begin(), F.end());
sort(T.begin(), T.end());
add_edges(F, T);
ll hlp;
printf("%lld\n", (hlp = dijkstra()) == INF ? -1 : hlp);
return 0;
}
Compilation message
treatment.cpp: In function 'll dijkstra()':
treatment.cpp:39:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0 ; i < P.size() ; i++) {
~~^~~~~~~~~~
treatment.cpp:60:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0 ; i < P.size() ; i++)
~~^~~~~~~~~~
treatment.cpp: In function 'int main()':
treatment.cpp:68:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &n, &m);
~~~~~^~~~~~~~~~~~~~~~
treatment.cpp:72:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d%d", &t, &l, &r, &c);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
999 ms |
524292 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
25 ms |
35584 KB |
Output is correct |
2 |
Correct |
26 ms |
35584 KB |
Output is correct |
3 |
Correct |
30 ms |
35584 KB |
Output is correct |
4 |
Correct |
26 ms |
35584 KB |
Output is correct |
5 |
Correct |
33 ms |
35580 KB |
Output is correct |
6 |
Correct |
25 ms |
35584 KB |
Output is correct |
7 |
Correct |
25 ms |
35584 KB |
Output is correct |
8 |
Correct |
25 ms |
35584 KB |
Output is correct |
9 |
Correct |
26 ms |
35576 KB |
Output is correct |
10 |
Correct |
25 ms |
35584 KB |
Output is correct |
11 |
Correct |
29 ms |
35584 KB |
Output is correct |
12 |
Correct |
25 ms |
35584 KB |
Output is correct |
13 |
Correct |
30 ms |
35584 KB |
Output is correct |
14 |
Correct |
25 ms |
35584 KB |
Output is correct |
15 |
Correct |
26 ms |
35584 KB |
Output is correct |
16 |
Correct |
29 ms |
35584 KB |
Output is correct |
17 |
Correct |
27 ms |
35584 KB |
Output is correct |
18 |
Correct |
25 ms |
35584 KB |
Output is correct |
19 |
Correct |
25 ms |
35584 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
25 ms |
35584 KB |
Output is correct |
2 |
Correct |
26 ms |
35584 KB |
Output is correct |
3 |
Correct |
30 ms |
35584 KB |
Output is correct |
4 |
Correct |
26 ms |
35584 KB |
Output is correct |
5 |
Correct |
33 ms |
35580 KB |
Output is correct |
6 |
Correct |
25 ms |
35584 KB |
Output is correct |
7 |
Correct |
25 ms |
35584 KB |
Output is correct |
8 |
Correct |
25 ms |
35584 KB |
Output is correct |
9 |
Correct |
26 ms |
35576 KB |
Output is correct |
10 |
Correct |
25 ms |
35584 KB |
Output is correct |
11 |
Correct |
29 ms |
35584 KB |
Output is correct |
12 |
Correct |
25 ms |
35584 KB |
Output is correct |
13 |
Correct |
30 ms |
35584 KB |
Output is correct |
14 |
Correct |
25 ms |
35584 KB |
Output is correct |
15 |
Correct |
26 ms |
35584 KB |
Output is correct |
16 |
Correct |
29 ms |
35584 KB |
Output is correct |
17 |
Correct |
27 ms |
35584 KB |
Output is correct |
18 |
Correct |
25 ms |
35584 KB |
Output is correct |
19 |
Correct |
25 ms |
35584 KB |
Output is correct |
20 |
Correct |
285 ms |
165016 KB |
Output is correct |
21 |
Correct |
280 ms |
164556 KB |
Output is correct |
22 |
Correct |
143 ms |
38724 KB |
Output is correct |
23 |
Correct |
142 ms |
38904 KB |
Output is correct |
24 |
Correct |
215 ms |
128760 KB |
Output is correct |
25 |
Correct |
141 ms |
99576 KB |
Output is correct |
26 |
Correct |
125 ms |
96376 KB |
Output is correct |
27 |
Correct |
137 ms |
110264 KB |
Output is correct |
28 |
Correct |
218 ms |
127796 KB |
Output is correct |
29 |
Correct |
140 ms |
98680 KB |
Output is correct |
30 |
Correct |
121 ms |
106232 KB |
Output is correct |
31 |
Correct |
140 ms |
111864 KB |
Output is correct |
32 |
Correct |
302 ms |
155896 KB |
Output is correct |
33 |
Correct |
297 ms |
224632 KB |
Output is correct |
34 |
Correct |
256 ms |
155208 KB |
Output is correct |
35 |
Correct |
293 ms |
155896 KB |
Output is correct |
36 |
Correct |
289 ms |
224248 KB |
Output is correct |
37 |
Correct |
249 ms |
155000 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
999 ms |
524292 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |