Submission #577136

#	Time	Username	Problem	Language	Result	Execution time	Memory
577136		Justin1	Ideal city (IOI12_city)	C++14	32 / 100	1077 ms	1620 KiB

city

#include <bits/stdc++.h>
#define f first
#define s second
#define ll long long
#define pii pair<int,int>
using namespace std;

vector<pii> dir = {{0,1},{1,0},{-1,0},{0,-1}};
bool ar[2005][2005], v[2005][2005];

ll bfs(int sx, int sy) {
	ll ans = 0;
	queue<pair<pii,int>> nxt;
	nxt.push({{sx,sy},0});
	while (!nxt.empty()) {
		auto tmp = nxt.front();
		nxt.pop();
		if (v[tmp.f.f][tmp.f.s]) continue;
		v[tmp.f.f][tmp.f.s] = 1;
		ans += tmp.s;
		for (auto i : dir) {
			if (!v[tmp.f.f+i.f][tmp.f.s+i.s] && ar[tmp.f.f+i.f][ tmp.f.s+i.s]) {
				nxt.push({{tmp.f.f+i.f, tmp.f.s+i.s}, tmp.s+1});
			}
		}
	}  
	return ans;
}

int DistanceSum(int N, int *X, int *Y) {
	int mnX = INT_MAX, mnY = INT_MAX;
	for (int i = 0; i < N; i++) mnX = min(mnX, X[i]);
	for (int i = 0; i < N; i++) mnY = min(mnY, Y[i]);
	for (int i = 0; i < N; i++) X[i] -= mnX-1;
	for (int i = 0; i < N; i++) Y[i] -= mnY-1;
	ll ans = 0;
	for (int i = 0; i < N; i++) ar[X[i]][Y[i]] = 1;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) v[X[j]][Y[j]] = 0;
		ans += bfs(X[i],Y[i]);
	}
	return (ans/2) % 1'000'000'000;
}

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