# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
91509 | 2018-12-28T01:06:06 Z | tincamatei | Shortcut (IOI16_shortcut) | C++14 | 2 ms | 748 KB |
#include <bits/stdc++.h> using namespace std; const int MAX_N = 500; vector<pair<int, int> > graph[1+2*MAX_N]; long long dist[1+2*MAX_N]; void dijkstra(int nod, int n) { for(int i = 0; i < 2 * n; ++i) dist[i] = 1LL<<60; deque<int> q; dist[nod] = 0; q.push_back(nod); while(!q.empty()) { int nod = q.front(); q.pop_front(); for(auto it: graph[nod]) if(dist[nod] + it.second < dist[it.first]) { dist[it.first] = dist[nod] + it.second; q.push_back(it.first); } } } long long getDiam(int n) { long long rez = 0LL; for(int i = 0; i < 2 * n; ++i) if(!graph[i].empty()) { dijkstra(i, n); for(int j = 0; j < 2 * n; ++j) if(!graph[j].empty()) rez = max(rez, dist[j]); } return rez; } long long f(int n, int x, int c) { long long rez = 1LL<<60; for(int i = 0; i + x < n; ++i) { graph[i].push_back(make_pair(i + x, c)); graph[i + x].push_back(make_pair(i, c)); rez = min(rez, getDiam(n)); graph[i].pop_back(); graph[i + x].pop_back(); } return rez; } long long asdf[1+MAX_N]; long long find_shortcut(int n, std::vector<int> l, std::vector<int> d, int c) { for(int i = 0; i < n - 1; ++i) { graph[i].push_back(make_pair(i + 1, l[i])); graph[i + 1].push_back(make_pair(i, l[i])); } for(int i = 0; i < n; ++i) if(d[i] != 0) { graph[i].push_back(make_pair(i + n, d[i])); graph[i + n].push_back(make_pair(i, d[i])); } for(int i = 1; i < n; ++i) { asdf[i] = f(n, i, c); } for(int i = 1; i < n - 1; ++i) { if(asdf[i] < asdf[i + 1]) return asdf[i]; } return asdf[n - 1]; }
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | n = 4, 80 is a correct answer |
2 | Correct | 2 ms | 380 KB | n = 9, 110 is a correct answer |
3 | Correct | 2 ms | 440 KB | n = 4, 21 is a correct answer |
4 | Correct | 2 ms | 456 KB | n = 3, 4 is a correct answer |
5 | Correct | 2 ms | 504 KB | n = 2, 62 is a correct answer |
6 | Correct | 2 ms | 564 KB | n = 2, 3 is a correct answer |
7 | Correct | 2 ms | 692 KB | n = 3, 29 is a correct answer |
8 | Correct | 2 ms | 692 KB | n = 2, 3 is a correct answer |
9 | Correct | 2 ms | 692 KB | n = 2, 3 is a correct answer |
10 | Correct | 2 ms | 692 KB | n = 2, 2000000001 is a correct answer |
11 | Correct | 2 ms | 692 KB | n = 2, 3000000000 is a correct answer |
12 | Correct | 2 ms | 692 KB | n = 3, 3000000000 is a correct answer |
13 | Correct | 2 ms | 692 KB | n = 3, 3000000000 is a correct answer |
14 | Correct | 2 ms | 692 KB | n = 4, 3000000001 is a correct answer |
15 | Correct | 2 ms | 692 KB | n = 4, 4000000000 is a correct answer |
16 | Correct | 2 ms | 692 KB | n = 5, 4000000000 is a correct answer |
17 | Correct | 2 ms | 692 KB | n = 10, 1000000343 is a correct answer |
18 | Correct | 2 ms | 692 KB | n = 10, 3189 is a correct answer |
19 | Correct | 2 ms | 692 KB | n = 10, 7000000000 is a correct answer |
20 | Correct | 2 ms | 692 KB | n = 5, 12 is a correct answer |
21 | Correct | 2 ms | 692 KB | n = 5, 25 is a correct answer |
22 | Correct | 2 ms | 692 KB | n = 2, 122 is a correct answer |
23 | Correct | 2 ms | 748 KB | n = 10, 117 is a correct answer |
24 | Correct | 2 ms | 748 KB | n = 10, 336 is a correct answer |
25 | Correct | 2 ms | 748 KB | n = 10, 438 is a correct answer |
26 | Incorrect | 2 ms | 748 KB | n = 10, incorrect answer: jury 206 vs contestant 217 |
27 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | n = 4, 80 is a correct answer |
2 | Correct | 2 ms | 380 KB | n = 9, 110 is a correct answer |
3 | Correct | 2 ms | 440 KB | n = 4, 21 is a correct answer |
4 | Correct | 2 ms | 456 KB | n = 3, 4 is a correct answer |
5 | Correct | 2 ms | 504 KB | n = 2, 62 is a correct answer |
6 | Correct | 2 ms | 564 KB | n = 2, 3 is a correct answer |
7 | Correct | 2 ms | 692 KB | n = 3, 29 is a correct answer |
8 | Correct | 2 ms | 692 KB | n = 2, 3 is a correct answer |
9 | Correct | 2 ms | 692 KB | n = 2, 3 is a correct answer |
10 | Correct | 2 ms | 692 KB | n = 2, 2000000001 is a correct answer |
11 | Correct | 2 ms | 692 KB | n = 2, 3000000000 is a correct answer |
12 | Correct | 2 ms | 692 KB | n = 3, 3000000000 is a correct answer |
13 | Correct | 2 ms | 692 KB | n = 3, 3000000000 is a correct answer |
14 | Correct | 2 ms | 692 KB | n = 4, 3000000001 is a correct answer |
15 | Correct | 2 ms | 692 KB | n = 4, 4000000000 is a correct answer |
16 | Correct | 2 ms | 692 KB | n = 5, 4000000000 is a correct answer |
17 | Correct | 2 ms | 692 KB | n = 10, 1000000343 is a correct answer |
18 | Correct | 2 ms | 692 KB | n = 10, 3189 is a correct answer |
19 | Correct | 2 ms | 692 KB | n = 10, 7000000000 is a correct answer |
20 | Correct | 2 ms | 692 KB | n = 5, 12 is a correct answer |
21 | Correct | 2 ms | 692 KB | n = 5, 25 is a correct answer |
22 | Correct | 2 ms | 692 KB | n = 2, 122 is a correct answer |
23 | Correct | 2 ms | 748 KB | n = 10, 117 is a correct answer |
24 | Correct | 2 ms | 748 KB | n = 10, 336 is a correct answer |
25 | Correct | 2 ms | 748 KB | n = 10, 438 is a correct answer |
26 | Incorrect | 2 ms | 748 KB | n = 10, incorrect answer: jury 206 vs contestant 217 |
27 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | n = 4, 80 is a correct answer |
2 | Correct | 2 ms | 380 KB | n = 9, 110 is a correct answer |
3 | Correct | 2 ms | 440 KB | n = 4, 21 is a correct answer |
4 | Correct | 2 ms | 456 KB | n = 3, 4 is a correct answer |
5 | Correct | 2 ms | 504 KB | n = 2, 62 is a correct answer |
6 | Correct | 2 ms | 564 KB | n = 2, 3 is a correct answer |
7 | Correct | 2 ms | 692 KB | n = 3, 29 is a correct answer |
8 | Correct | 2 ms | 692 KB | n = 2, 3 is a correct answer |
9 | Correct | 2 ms | 692 KB | n = 2, 3 is a correct answer |
10 | Correct | 2 ms | 692 KB | n = 2, 2000000001 is a correct answer |
11 | Correct | 2 ms | 692 KB | n = 2, 3000000000 is a correct answer |
12 | Correct | 2 ms | 692 KB | n = 3, 3000000000 is a correct answer |
13 | Correct | 2 ms | 692 KB | n = 3, 3000000000 is a correct answer |
14 | Correct | 2 ms | 692 KB | n = 4, 3000000001 is a correct answer |
15 | Correct | 2 ms | 692 KB | n = 4, 4000000000 is a correct answer |
16 | Correct | 2 ms | 692 KB | n = 5, 4000000000 is a correct answer |
17 | Correct | 2 ms | 692 KB | n = 10, 1000000343 is a correct answer |
18 | Correct | 2 ms | 692 KB | n = 10, 3189 is a correct answer |
19 | Correct | 2 ms | 692 KB | n = 10, 7000000000 is a correct answer |
20 | Correct | 2 ms | 692 KB | n = 5, 12 is a correct answer |
21 | Correct | 2 ms | 692 KB | n = 5, 25 is a correct answer |
22 | Correct | 2 ms | 692 KB | n = 2, 122 is a correct answer |
23 | Correct | 2 ms | 748 KB | n = 10, 117 is a correct answer |
24 | Correct | 2 ms | 748 KB | n = 10, 336 is a correct answer |
25 | Correct | 2 ms | 748 KB | n = 10, 438 is a correct answer |
26 | Incorrect | 2 ms | 748 KB | n = 10, incorrect answer: jury 206 vs contestant 217 |
27 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | n = 4, 80 is a correct answer |
2 | Correct | 2 ms | 380 KB | n = 9, 110 is a correct answer |
3 | Correct | 2 ms | 440 KB | n = 4, 21 is a correct answer |
4 | Correct | 2 ms | 456 KB | n = 3, 4 is a correct answer |
5 | Correct | 2 ms | 504 KB | n = 2, 62 is a correct answer |
6 | Correct | 2 ms | 564 KB | n = 2, 3 is a correct answer |
7 | Correct | 2 ms | 692 KB | n = 3, 29 is a correct answer |
8 | Correct | 2 ms | 692 KB | n = 2, 3 is a correct answer |
9 | Correct | 2 ms | 692 KB | n = 2, 3 is a correct answer |
10 | Correct | 2 ms | 692 KB | n = 2, 2000000001 is a correct answer |
11 | Correct | 2 ms | 692 KB | n = 2, 3000000000 is a correct answer |
12 | Correct | 2 ms | 692 KB | n = 3, 3000000000 is a correct answer |
13 | Correct | 2 ms | 692 KB | n = 3, 3000000000 is a correct answer |
14 | Correct | 2 ms | 692 KB | n = 4, 3000000001 is a correct answer |
15 | Correct | 2 ms | 692 KB | n = 4, 4000000000 is a correct answer |
16 | Correct | 2 ms | 692 KB | n = 5, 4000000000 is a correct answer |
17 | Correct | 2 ms | 692 KB | n = 10, 1000000343 is a correct answer |
18 | Correct | 2 ms | 692 KB | n = 10, 3189 is a correct answer |
19 | Correct | 2 ms | 692 KB | n = 10, 7000000000 is a correct answer |
20 | Correct | 2 ms | 692 KB | n = 5, 12 is a correct answer |
21 | Correct | 2 ms | 692 KB | n = 5, 25 is a correct answer |
22 | Correct | 2 ms | 692 KB | n = 2, 122 is a correct answer |
23 | Correct | 2 ms | 748 KB | n = 10, 117 is a correct answer |
24 | Correct | 2 ms | 748 KB | n = 10, 336 is a correct answer |
25 | Correct | 2 ms | 748 KB | n = 10, 438 is a correct answer |
26 | Incorrect | 2 ms | 748 KB | n = 10, incorrect answer: jury 206 vs contestant 217 |
27 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | n = 4, 80 is a correct answer |
2 | Correct | 2 ms | 380 KB | n = 9, 110 is a correct answer |
3 | Correct | 2 ms | 440 KB | n = 4, 21 is a correct answer |
4 | Correct | 2 ms | 456 KB | n = 3, 4 is a correct answer |
5 | Correct | 2 ms | 504 KB | n = 2, 62 is a correct answer |
6 | Correct | 2 ms | 564 KB | n = 2, 3 is a correct answer |
7 | Correct | 2 ms | 692 KB | n = 3, 29 is a correct answer |
8 | Correct | 2 ms | 692 KB | n = 2, 3 is a correct answer |
9 | Correct | 2 ms | 692 KB | n = 2, 3 is a correct answer |
10 | Correct | 2 ms | 692 KB | n = 2, 2000000001 is a correct answer |
11 | Correct | 2 ms | 692 KB | n = 2, 3000000000 is a correct answer |
12 | Correct | 2 ms | 692 KB | n = 3, 3000000000 is a correct answer |
13 | Correct | 2 ms | 692 KB | n = 3, 3000000000 is a correct answer |
14 | Correct | 2 ms | 692 KB | n = 4, 3000000001 is a correct answer |
15 | Correct | 2 ms | 692 KB | n = 4, 4000000000 is a correct answer |
16 | Correct | 2 ms | 692 KB | n = 5, 4000000000 is a correct answer |
17 | Correct | 2 ms | 692 KB | n = 10, 1000000343 is a correct answer |
18 | Correct | 2 ms | 692 KB | n = 10, 3189 is a correct answer |
19 | Correct | 2 ms | 692 KB | n = 10, 7000000000 is a correct answer |
20 | Correct | 2 ms | 692 KB | n = 5, 12 is a correct answer |
21 | Correct | 2 ms | 692 KB | n = 5, 25 is a correct answer |
22 | Correct | 2 ms | 692 KB | n = 2, 122 is a correct answer |
23 | Correct | 2 ms | 748 KB | n = 10, 117 is a correct answer |
24 | Correct | 2 ms | 748 KB | n = 10, 336 is a correct answer |
25 | Correct | 2 ms | 748 KB | n = 10, 438 is a correct answer |
26 | Incorrect | 2 ms | 748 KB | n = 10, incorrect answer: jury 206 vs contestant 217 |
27 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | n = 4, 80 is a correct answer |
2 | Correct | 2 ms | 380 KB | n = 9, 110 is a correct answer |
3 | Correct | 2 ms | 440 KB | n = 4, 21 is a correct answer |
4 | Correct | 2 ms | 456 KB | n = 3, 4 is a correct answer |
5 | Correct | 2 ms | 504 KB | n = 2, 62 is a correct answer |
6 | Correct | 2 ms | 564 KB | n = 2, 3 is a correct answer |
7 | Correct | 2 ms | 692 KB | n = 3, 29 is a correct answer |
8 | Correct | 2 ms | 692 KB | n = 2, 3 is a correct answer |
9 | Correct | 2 ms | 692 KB | n = 2, 3 is a correct answer |
10 | Correct | 2 ms | 692 KB | n = 2, 2000000001 is a correct answer |
11 | Correct | 2 ms | 692 KB | n = 2, 3000000000 is a correct answer |
12 | Correct | 2 ms | 692 KB | n = 3, 3000000000 is a correct answer |
13 | Correct | 2 ms | 692 KB | n = 3, 3000000000 is a correct answer |
14 | Correct | 2 ms | 692 KB | n = 4, 3000000001 is a correct answer |
15 | Correct | 2 ms | 692 KB | n = 4, 4000000000 is a correct answer |
16 | Correct | 2 ms | 692 KB | n = 5, 4000000000 is a correct answer |
17 | Correct | 2 ms | 692 KB | n = 10, 1000000343 is a correct answer |
18 | Correct | 2 ms | 692 KB | n = 10, 3189 is a correct answer |
19 | Correct | 2 ms | 692 KB | n = 10, 7000000000 is a correct answer |
20 | Correct | 2 ms | 692 KB | n = 5, 12 is a correct answer |
21 | Correct | 2 ms | 692 KB | n = 5, 25 is a correct answer |
22 | Correct | 2 ms | 692 KB | n = 2, 122 is a correct answer |
23 | Correct | 2 ms | 748 KB | n = 10, 117 is a correct answer |
24 | Correct | 2 ms | 748 KB | n = 10, 336 is a correct answer |
25 | Correct | 2 ms | 748 KB | n = 10, 438 is a correct answer |
26 | Incorrect | 2 ms | 748 KB | n = 10, incorrect answer: jury 206 vs contestant 217 |
27 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | n = 4, 80 is a correct answer |
2 | Correct | 2 ms | 380 KB | n = 9, 110 is a correct answer |
3 | Correct | 2 ms | 440 KB | n = 4, 21 is a correct answer |
4 | Correct | 2 ms | 456 KB | n = 3, 4 is a correct answer |
5 | Correct | 2 ms | 504 KB | n = 2, 62 is a correct answer |
6 | Correct | 2 ms | 564 KB | n = 2, 3 is a correct answer |
7 | Correct | 2 ms | 692 KB | n = 3, 29 is a correct answer |
8 | Correct | 2 ms | 692 KB | n = 2, 3 is a correct answer |
9 | Correct | 2 ms | 692 KB | n = 2, 3 is a correct answer |
10 | Correct | 2 ms | 692 KB | n = 2, 2000000001 is a correct answer |
11 | Correct | 2 ms | 692 KB | n = 2, 3000000000 is a correct answer |
12 | Correct | 2 ms | 692 KB | n = 3, 3000000000 is a correct answer |
13 | Correct | 2 ms | 692 KB | n = 3, 3000000000 is a correct answer |
14 | Correct | 2 ms | 692 KB | n = 4, 3000000001 is a correct answer |
15 | Correct | 2 ms | 692 KB | n = 4, 4000000000 is a correct answer |
16 | Correct | 2 ms | 692 KB | n = 5, 4000000000 is a correct answer |
17 | Correct | 2 ms | 692 KB | n = 10, 1000000343 is a correct answer |
18 | Correct | 2 ms | 692 KB | n = 10, 3189 is a correct answer |
19 | Correct | 2 ms | 692 KB | n = 10, 7000000000 is a correct answer |
20 | Correct | 2 ms | 692 KB | n = 5, 12 is a correct answer |
21 | Correct | 2 ms | 692 KB | n = 5, 25 is a correct answer |
22 | Correct | 2 ms | 692 KB | n = 2, 122 is a correct answer |
23 | Correct | 2 ms | 748 KB | n = 10, 117 is a correct answer |
24 | Correct | 2 ms | 748 KB | n = 10, 336 is a correct answer |
25 | Correct | 2 ms | 748 KB | n = 10, 438 is a correct answer |
26 | Incorrect | 2 ms | 748 KB | n = 10, incorrect answer: jury 206 vs contestant 217 |
27 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | n = 4, 80 is a correct answer |
2 | Correct | 2 ms | 380 KB | n = 9, 110 is a correct answer |
3 | Correct | 2 ms | 440 KB | n = 4, 21 is a correct answer |
4 | Correct | 2 ms | 456 KB | n = 3, 4 is a correct answer |
5 | Correct | 2 ms | 504 KB | n = 2, 62 is a correct answer |
6 | Correct | 2 ms | 564 KB | n = 2, 3 is a correct answer |
7 | Correct | 2 ms | 692 KB | n = 3, 29 is a correct answer |
8 | Correct | 2 ms | 692 KB | n = 2, 3 is a correct answer |
9 | Correct | 2 ms | 692 KB | n = 2, 3 is a correct answer |
10 | Correct | 2 ms | 692 KB | n = 2, 2000000001 is a correct answer |
11 | Correct | 2 ms | 692 KB | n = 2, 3000000000 is a correct answer |
12 | Correct | 2 ms | 692 KB | n = 3, 3000000000 is a correct answer |
13 | Correct | 2 ms | 692 KB | n = 3, 3000000000 is a correct answer |
14 | Correct | 2 ms | 692 KB | n = 4, 3000000001 is a correct answer |
15 | Correct | 2 ms | 692 KB | n = 4, 4000000000 is a correct answer |
16 | Correct | 2 ms | 692 KB | n = 5, 4000000000 is a correct answer |
17 | Correct | 2 ms | 692 KB | n = 10, 1000000343 is a correct answer |
18 | Correct | 2 ms | 692 KB | n = 10, 3189 is a correct answer |
19 | Correct | 2 ms | 692 KB | n = 10, 7000000000 is a correct answer |
20 | Correct | 2 ms | 692 KB | n = 5, 12 is a correct answer |
21 | Correct | 2 ms | 692 KB | n = 5, 25 is a correct answer |
22 | Correct | 2 ms | 692 KB | n = 2, 122 is a correct answer |
23 | Correct | 2 ms | 748 KB | n = 10, 117 is a correct answer |
24 | Correct | 2 ms | 748 KB | n = 10, 336 is a correct answer |
25 | Correct | 2 ms | 748 KB | n = 10, 438 is a correct answer |
26 | Incorrect | 2 ms | 748 KB | n = 10, incorrect answer: jury 206 vs contestant 217 |
27 | Halted | 0 ms | 0 KB | - |