oj.uz

Submission #429642

# Submission time Handle Problem Language Result Execution time Memory
429642 2021-06-16T08:15:26 Z Mounir Ideal city (IOI12_city) C++14
32 / 100
 1000 ms 3916 KB 
#include <bits/stdc++.h>
#define pii pair<int, int>
#define x first
#define y second
#define pb push_back
#define chmin(x, v) x = min(x, v)
#define chmax(x, v) x = max(x, v)
using namespace std;

const int MOD =  1000000000, N = 3000;
int delta[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
bool estVille[N][N], vue[N][N];
int dist[N][N];

int DistanceSum(int nVilles, int *X, int *Y) {
	vector<pii> villes(nVilles);
	int xMin = MOD, yMin = MOD;
	for (int iVille = 0; iVille < nVilles; ++iVille){
		villes[iVille] = {X[iVille], Y[iVille]};
		chmin(xMin, X[iVille]);
		chmin(yMin, Y[iVille]);
	}

	for (pii& ville : villes){
		ville.x -= xMin;
		ville.y -= yMin;

		estVille[ville.x][ville.y] = true;
	}

	int sum = 0;
	for (pii depart : villes){
		for (pii ville : villes)
			vue[ville.x][ville.y] = false;

		queue<pii> file;
		vue[depart.x][depart.y] = true;
		dist[depart.x][depart.y] = 0;
		file.push(depart);

		while (!file.empty()){
			pii noeud = file.front();
			file.pop();

			for (int i = 0; i < 4; ++i){
				int ax = noeud.x + delta[i][0], ay = noeud.y + delta[i][1];
				if (estVille[ax][ay] && !vue[ax][ay]){
					vue[ax][ay] = true;
					dist[ax][ay] = dist[noeud.x][noeud.y] + 1;
					sum += dist[ax][ay];
					file.push({ax, ay});
				}
			}
		}
	}
	return sum/2;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 2 ms 460 KB Output is correct
7 Correct 2 ms 460 KB Output is correct
8 Correct 4 ms 588 KB Output is correct
9 Correct 2 ms 460 KB Output is correct
10 Correct 2 ms 460 KB Output is correct
11 Correct 2 ms 472 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 844 KB Output is correct
2 Correct 33 ms 716 KB Output is correct
3 Correct 101 ms 1108 KB Output is correct
4 Correct 79 ms 1096 KB Output is correct
5 Correct 167 ms 1312 KB Output is correct
6 Correct 122 ms 1228 KB Output is correct
7 Correct 177 ms 1704 KB Output is correct
8 Correct 119 ms 1708 KB Output is correct
9 Correct 112 ms 1020 KB Output is correct
10 Correct 104 ms 1092 KB Output is correct

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1092 ms 3660 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1053 ms 3916 KB Time limit exceeded
2 Halted 0 ms 0 KB -