| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1000753 |
2024-06-18T08:20:52 Z |
Nomio |
Race (IOI11_race) |
C++17 |
|
20 ms |
13404 KB |
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
vector<int> adj[1001];
ll dis[1001][1001] {};
int d[1001][1001], D[1001][1001];
void bfs(int x) {
queue<int> q;
dis[x][x] = 0;
D[x][x] = 0;
q.push(x);
while(!q.empty()) {
int X = q.front();
q.pop();
for(int y : adj[X]) {
if(dis[x][y] == -1) {
q.push(y);
dis[x][y] = dis[x][X] + d[X][y];
D[x][y] = D[x][X] + 1;
}
}
}
}
int best_path(int n, int k, int H[][2], int L[]) {
for(int i = 0; i <= n; i++) {
adj[i].clear();
}
for(int i = 0; i <= n; i++) {
for(int j = 0; j <= n; j++) {
D[i][j] = 0;
d[i][j] = -1;
if(i == j) {
d[i][j] = 0;
}
}
}
for(int i = 0; i < n - 1; i++) {
int a, b;
a = H[i][0];
b = H[i][1];
adj[a].push_back(b);
adj[b].push_back(a);
}
bool w = 1;
for(int i = 0; i < n - 1; i++) {
if(i != H[i][0] || i + 1 != H[i][1]) {
w = 0;
break;
}
}
for(int i = 0; i < n - 1; i++) {
d[H[i][0]][H[i][1]] = L[i];
d[H[i][1]][H[i][0]] = L[i];
}
if(w) {
int S[n + 1] {};
for(int i = 0; i < n - 1; i++) {
S[i + 2] = S[i + 1] + L[i];
}
int mn = n;
for(int i = 2; i <= n; i++) {
for(int j = 1; j <= i - 1; j++) {
if(S[i] - S[j] == k) {
mn = min(mn, i - j);
}
}
}
if(mn == n) mn = -1;
return mn;
} else {
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
if(i == j) continue;
bfs(i);
}
}
int mn = 1e9;
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
if(i == j) continue;
if(dis[i][j] == k) {
mn = min(mn, D[i][j]);
}
}
}
if(mn == 1e9) mn = -1;
return mn;
}
}
//int main() {
// cout << best_path(3, 3, {{0, 1}, {1, 2}}, {1, 1}) << '\n';
// return 0;
//}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 2 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 3 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 4 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 5 |
Correct |
1 ms |
7004 KB |
Output is correct |
| 6 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 7 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 8 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 9 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 10 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 11 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 12 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 13 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 14 |
Correct |
1 ms |
6488 KB |
Output is correct |
| 15 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 16 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 17 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 18 |
Correct |
1 ms |
6492 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 2 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 3 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 4 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 5 |
Correct |
1 ms |
7004 KB |
Output is correct |
| 6 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 7 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 8 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 9 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 10 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 11 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 12 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 13 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 14 |
Correct |
1 ms |
6488 KB |
Output is correct |
| 15 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 16 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 17 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 18 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 19 |
Incorrect |
1 ms |
6492 KB |
Output isn't correct |
| 20 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 2 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 3 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 4 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 5 |
Correct |
1 ms |
7004 KB |
Output is correct |
| 6 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 7 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 8 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 9 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 10 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 11 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 12 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 13 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 14 |
Correct |
1 ms |
6488 KB |
Output is correct |
| 15 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 16 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 17 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 18 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 19 |
Runtime error |
20 ms |
13404 KB |
Execution killed with signal 11 |
| 20 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 2 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 3 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 4 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 5 |
Correct |
1 ms |
7004 KB |
Output is correct |
| 6 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 7 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 8 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 9 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 10 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 11 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 12 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 13 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 14 |
Correct |
1 ms |
6488 KB |
Output is correct |
| 15 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 16 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 17 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 18 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 19 |
Incorrect |
1 ms |
6492 KB |
Output isn't correct |
| 20 |
Halted |
0 ms |
0 KB |
- |
