제출 #429642

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
429642		Mounir	Ideal city (IOI12_city)	C++14	32 / 100	1092 ms	3916 KiB

city

#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 / 11
• Subtask 2: 21 / 21
• Subtask 3: 0 / 23
• Subtask 4: 0 / 45