# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
118427 | 2019-06-19T02:59:15 Z | E869120 | Ideal city (IOI12_city) | C++14 | 128 ms | 4472 KB |
#include <iostream> #include <algorithm> #include <vector> #include <queue> using namespace std; vector<int>vec[2009]; int dist[2009]; int DistanceSum(int N, int *X, int *Y) { if (N <= 2000) { for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { if (abs(X[i] - X[j]) + abs(Y[i] - Y[j]) == 1) { vec[i].push_back(j); } } } long long sum = 0; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) dist[j] = (1 << 30); queue<int>Q; Q.push(i); dist[i] = 0; while (!Q.empty()) { int pos = Q.front(); Q.pop(); for (int j = 0; j < vec[pos].size(); j++) { if (dist[vec[pos][j]] > dist[pos] + 1) { dist[vec[pos][j]] = dist[pos] + 1; Q.push(vec[pos][j]); } } } for (int j = 0; j < N; j++) sum += dist[j]; } return (int)((sum / 2LL) % 1000000000LL); } else { vector<long long>CX, CY; for (int i = 0; i < N; i++) CX.push_back(X[i]); for (int i = 0; i < N; i++) CY.push_back(Y[i]); sort(CX.begin(), CX.end()); sort(CY.begin(), CY.end()); long long sum = 0; for (int i = 0; i < N; i++) sum += CX[i] * (2LL * i - 1LL * N + 1LL); for (int i = 0; i < N; i++) sum += CY[i] * (2LL * i - 1LL * N + 1LL); return (int)(sum % 1000000000LL); } }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 384 KB | Output is correct |
2 | Correct | 2 ms | 384 KB | Output is correct |
3 | Correct | 2 ms | 384 KB | Output is correct |
4 | Correct | 2 ms | 384 KB | Output is correct |
5 | Correct | 2 ms | 384 KB | Output is correct |
6 | Correct | 2 ms | 384 KB | Output is correct |
7 | Correct | 3 ms | 384 KB | Output is correct |
8 | Correct | 3 ms | 384 KB | Output is correct |
9 | Correct | 3 ms | 384 KB | Output is correct |
10 | Correct | 3 ms | 384 KB | Output is correct |
11 | Correct | 3 ms | 384 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 25 ms | 384 KB | Output is correct |
2 | Correct | 29 ms | 384 KB | Output is correct |
3 | Correct | 64 ms | 608 KB | Output is correct |
4 | Correct | 69 ms | 512 KB | Output is correct |
5 | Correct | 118 ms | 512 KB | Output is correct |
6 | Correct | 121 ms | 536 KB | Output is correct |
7 | Correct | 120 ms | 616 KB | Output is correct |
8 | Correct | 124 ms | 504 KB | Output is correct |
9 | Correct | 128 ms | 540 KB | Output is correct |
10 | Correct | 114 ms | 512 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 7 ms | 1148 KB | Output is correct |
2 | Correct | 8 ms | 1276 KB | Output is correct |
3 | Correct | 17 ms | 2428 KB | Output is correct |
4 | Correct | 17 ms | 2300 KB | Output is correct |
5 | Correct | 32 ms | 4356 KB | Output is correct |
6 | Correct | 31 ms | 4200 KB | Output is correct |
7 | Correct | 34 ms | 4472 KB | Output is correct |
8 | Correct | 30 ms | 4216 KB | Output is correct |
9 | Correct | 33 ms | 4208 KB | Output is correct |
10 | Correct | 30 ms | 4392 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 8 ms | 1148 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |