# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1240168 | luvlorndev | Ideal city (IOI12_city) | C++20 | 0 ms | 0 KiB |
#include <bits/stdcc++.h>
using namespace std;
int coorX[2010];
int coorY[2010];
int dx[4] = {1,-1,0,0};
int dy[4] = {0,0,1,-1};
map<pair<int, int>, int> mp;
int bfs(int idx, int n) {
queue <int> q;
vector<bool> visited(2010,0);
vector<int> dist(2010, 0);
q.push(idx);
visited[idx]=True;
while (q.size() != 0) {
int fr = q.front();
int cx = coorX[fr];
int cy = coorY[fr];
for (int i = 0; i < 4; i++) {
int nx = cx+dx[i];
int ny = cy+dy[i];
if (mp.count(make_pair(nx, ny))) {
int nxt = mp[make_pair(nx, ny)];
if (visited[nxt] == False) {
q.push(nxt);
dist[nxt] = dist[fr]+1;
}
}
}
}
int sum = 0;
for (int i = 0; i < dist.size(); i++) {
sum += dist[i];
}
return sum;
}
int DistanceSum(int N, int *X, int *Y) {
for (int i = 0; i < N; i++) {
mp[make_pair(X[i], Y[i])] = i;
}
int sumtot = 0;
for (int i = 0; i < n; i++) {
sumtot += bfs(i, N);
}
return sumtot;
}