# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
430300 | 2021-06-16T12:47:14 Z | Nicholas_Patrick | Treatment Project (JOI20_treatment) | C++17 | 3000 ms | 2620 KB |
#include <cstdio> #include <queue> using namespace std; template <typename T> using eueuq_ytiroirp = priority_queue<T, vector<T>, greater<T>>; struct node{ int l, r, t, c; // node(int l, int r, int t, int c):l(l-1), r(r), t(t), c(c){} bool connect(node rhs)const{ return t<rhs.t? rhs.l<=r-rhs.t+t: rhs.l<=r-t+rhs.t; } }; int main(){ int n, m; scanf("%d%d", &n, &m); long long ans=1000000000000000; vector<node> nodes(m); for(auto& i : nodes) scanf("%d%d%d%d", &i.t, &i.l, &i.r, &i.c), i.l--; vector<long long> dist(m, ans); vector<bool> explored(m, false); for(int i=0; i<m; i++){ if(nodes[i].l==0) dist[i]=nodes[i].c; } for(int i=0; i<m; i++){ int from=-1; for(int j=0; j<m; j++){ if(explored[j]) continue; if(from==-1 or dist[from]>dist[j]) from=j; } explored[from]=true; for(int j=0; j<m; j++){ if(explored[j]) continue; if(nodes[from].connect(nodes[j])) dist[j]=min(dist[j], dist[from]+nodes[j].c); } } for(int i=0; i<m; i++){ if(nodes[i].r==n) ans=min(ans, dist[i]); } if(ans==1000000000000000) ans=-1; printf("%lld\n", ans); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 3067 ms | 2620 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 204 KB | Output is correct |
2 | Correct | 0 ms | 204 KB | Output is correct |
3 | Correct | 1 ms | 204 KB | Output is correct |
4 | Correct | 1 ms | 316 KB | Output is correct |
5 | Correct | 1 ms | 204 KB | Output is correct |
6 | Correct | 0 ms | 204 KB | Output is correct |
7 | Correct | 0 ms | 204 KB | Output is correct |
8 | Correct | 0 ms | 204 KB | Output is correct |
9 | Correct | 0 ms | 204 KB | Output is correct |
10 | Correct | 1 ms | 204 KB | Output is correct |
11 | Correct | 1 ms | 204 KB | Output is correct |
12 | Correct | 0 ms | 204 KB | Output is correct |
13 | Correct | 0 ms | 204 KB | Output is correct |
14 | Correct | 0 ms | 204 KB | Output is correct |
15 | Correct | 0 ms | 204 KB | Output is correct |
16 | Correct | 0 ms | 204 KB | Output is correct |
17 | Correct | 0 ms | 204 KB | Output is correct |
18 | Correct | 0 ms | 204 KB | Output is correct |
19 | Correct | 0 ms | 204 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 204 KB | Output is correct |
2 | Correct | 0 ms | 204 KB | Output is correct |
3 | Correct | 1 ms | 204 KB | Output is correct |
4 | Correct | 1 ms | 316 KB | Output is correct |
5 | Correct | 1 ms | 204 KB | Output is correct |
6 | Correct | 0 ms | 204 KB | Output is correct |
7 | Correct | 0 ms | 204 KB | Output is correct |
8 | Correct | 0 ms | 204 KB | Output is correct |
9 | Correct | 0 ms | 204 KB | Output is correct |
10 | Correct | 1 ms | 204 KB | Output is correct |
11 | Correct | 1 ms | 204 KB | Output is correct |
12 | Correct | 0 ms | 204 KB | Output is correct |
13 | Correct | 0 ms | 204 KB | Output is correct |
14 | Correct | 0 ms | 204 KB | Output is correct |
15 | Correct | 0 ms | 204 KB | Output is correct |
16 | Correct | 0 ms | 204 KB | Output is correct |
17 | Correct | 0 ms | 204 KB | Output is correct |
18 | Correct | 0 ms | 204 KB | Output is correct |
19 | Correct | 0 ms | 204 KB | Output is correct |
20 | Correct | 177 ms | 368 KB | Output is correct |
21 | Correct | 206 ms | 368 KB | Output is correct |
22 | Correct | 174 ms | 388 KB | Output is correct |
23 | Correct | 181 ms | 368 KB | Output is correct |
24 | Correct | 255 ms | 332 KB | Output is correct |
25 | Correct | 116 ms | 372 KB | Output is correct |
26 | Correct | 94 ms | 368 KB | Output is correct |
27 | Correct | 96 ms | 372 KB | Output is correct |
28 | Correct | 215 ms | 368 KB | Output is correct |
29 | Correct | 112 ms | 332 KB | Output is correct |
30 | Correct | 95 ms | 332 KB | Output is correct |
31 | Correct | 93 ms | 332 KB | Output is correct |
32 | Correct | 250 ms | 452 KB | Output is correct |
33 | Correct | 272 ms | 456 KB | Output is correct |
34 | Correct | 218 ms | 380 KB | Output is correct |
35 | Correct | 249 ms | 372 KB | Output is correct |
36 | Correct | 259 ms | 332 KB | Output is correct |
37 | Correct | 207 ms | 388 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 3067 ms | 2620 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |