제출 #429638

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
429638		Mounir	이상적인 도시 (IOI12_city)	C++14	11 / 100	1084 ms	5444 KiB

city

#include <bits/stdc++.h>
#define pii pair<int, int>
#define x first
#define y second
#define pb push_back
using namespace std;

int delta[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

set<pii> vues;
map<pii, vector<pii>> voisins;
map<pii, int> dist;

int DistanceSum(int nVilles, int *X, int *Y) {
	vector<pii> villes(nVilles);
	for (int iVille = 0; iVille < nVilles; ++iVille){
		villes[iVille] = {X[iVille], Y[iVille]};
		vues.insert(villes[iVille]);
	}

	for (pii ville : villes){
		for (int i = 0; i < 4; ++i){
			int ax = ville.x + delta[i][0], ay = ville.y + delta[i][1];
			if (vues.count({ax, ay}) == 1)
				voisins[ville].pb({ax, ay});
		}
	}

	int sum = 0;
	for (pii depart : villes){
		dist = {};
		dist[depart] = 0;
		queue<pii> file;
		file.push(depart);

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

			for (pii voisin : voisins[cur]){
				if (dist.count(voisin) == 0){
					sum += dist[cur] + 1;
					dist[voisin] = dist[cur] + 1;
					file.push(voisin);
				}
			}
		}
	}
	return sum/2;
}

• Subtask 1: 11 / 11
• Subtask 2: 0 / 21
• Subtask 3: 0 / 23
• Subtask 4: 0 / 45