Submission #1243761

#	Time	Username	Problem	Language	Result	Execution time	Memory
1243761		santi3223	Ideal city (IOI12_city)	C++20	11 / 100	1095 ms	3772 KiB

city

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define vb vector<bool>
#define pb push_back
#define ff(aa, bb, cc) for(ll aa = bb; aa < cc; aa++)
#define vl vector<ll>
#define pll pair<ll, ll>
#define fi first
#define se second
#define ed "\n"
#define all(aaa) aaa.begin(), aaa.end()
#define rall(aaa) aaa.rbegin(), aaa.rend()
ll MOD = 1000000000;

map<pll, ll> dist;
map<pll, bool> exists;

void flood(int x, int y, int sum){
	//cout << x << " "<< y << ed;
	if(!exists[{x, y}]){
		return;
	}
	if(sum >= dist[{x, y}]){
		//cout << "SUM MORE " <<  sum << " " << dist[{x, y}] << ed;
		return;
	}
	dist[{x, y}] = sum;
	if(exists[{x-1, y}]){
		flood(x-1, y, sum+1);
	}
	if(exists[{x+1, y}]){
		flood(x+1, y, sum+1);
	}
	if(exists[{x, y+1}]){
		flood(x, y+1, sum+1);
	}
	if(exists[{x, y-1}]){
		flood(x, y-1, sum+1);
	}
}

int DistanceSum(int n, int *X, int *Y){
	vector<pll> coords;
	ff(i, 0, n){
		coords.pb({X[i], Y[i]});
		exists[{X[i], Y[i]}] = true;
	}
	ll c = 0;
	ff(i, 0, n){
		ll curx = coords[i].fi, cury = coords[i].se;
		dist.clear();
		for(auto &p : exists){
			dist[{p.fi.fi, p.fi.se}] = INT_MAX;
		}
		flood(curx, cury, 0);
		//cout << "===========" << ed;
		ff(j, i+1, n){
			//cout << dist[{X[j], Y[j]}] << ed;
			c += dist[{X[j], Y[j]}] % MOD;
		}
		//cout << "===========" << ed;
		c %= MOD;
	}
	return c%MOD;

}
/*
int main() {
	ll n;
	cin >> n;
	int *x, *y;
	x = (int*) malloc(n * sizeof(int));
	y = (int*) malloc(n * sizeof(int));
	ff(i, 0, n){
		cin >> x[i] >> y[i];
	}
	ll res = DistanceSum(n, x, y);
	cout << res << ed;
	return 0;

}
*/

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