oj.uz

Submission #98194

# Submission time Handle Problem Language Result Execution time Memory
98194 2019-02-21T12:13:15 Z E869120 Ideal city (IOI12_city) C++14
32 / 100
 173 ms 1260 KB 
#include <bits/stdc++.h>
using namespace std;

vector<int> G[2009]; int dist[2009], mod = 1000000000;

int DistanceSum(int N, int *X, int *Y) {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			int V = abs(X[i] - X[j]) + abs(Y[i] - Y[j]);
			if (V == 1) G[i].push_back(j);
		}
	}
	
	int sum = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) dist[j] = 10000;
		
		queue<int> que; que.push(i); dist[i] = 0;
		while (!que.empty()) {
			int pos = que.front(); que.pop();
			for (int j = 0; j < (int)G[pos].size(); j++) {
				if (dist[G[pos][j]] > dist[pos] + 1) {
					dist[G[pos][j]] = dist[pos] + 1;
					que.push(G[pos][j]);
				}
			}
		}
		for (int j = i + 1; j < N; j++) { sum += dist[j]; sum %= mod; }
	}
	return sum;
}

Subtask #1
11.0 / 11.0

# 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 3 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 4 ms 384 KB Output is correct
9 Correct 4 ms 384 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Correct 0 ms 384 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 384 KB Output is correct
2 Correct 41 ms 384 KB Output is correct
3 Correct 73 ms 384 KB Output is correct
4 Correct 85 ms 512 KB Output is correct
5 Correct 173 ms 632 KB Output is correct
6 Correct 145 ms 632 KB Output is correct
7 Correct 139 ms 504 KB Output is correct
8 Correct 148 ms 504 KB Output is correct
9 Correct 147 ms 504 KB Output is correct
10 Correct 146 ms 468 KB Output is correct

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 129 ms 1260 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Runtime error 136 ms 1144 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -