Submission #1243771

#	Time	Username	Problem	Language	Result	Execution time	Memory
1243771		santi3223	Ideal city (IOI12_city)	C++20	32 / 100	1096 ms	3396 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;

int DistanceSum(int n, int *X, int *Y){
	map<pll, ll> mp;
	vector<vl> conexiones(n);
	ff(i, 0, n){
		mp[{X[i], Y[i]}] = i;
	}
	for(auto &p : mp){
		ll a = p.fi.fi, b = p.fi.se, c = p.se;
		if(mp.count({a-1, b})){
			conexiones[c].pb(mp[{a-1, b}]);
		}
		if(mp.count({a+1, b})){
			conexiones[c].pb(mp[{a+1, b}]);
		}
		if(mp.count({a, b-1})){
			conexiones[c].pb(mp[{a, b-1}]);
		}
		if(mp.count({a, b+1})){
			conexiones[c].pb(mp[{a, b+1}]);
		}
	}
	ll c = 0;
	ff(i, 0, n){
		queue<ll> q;
		q.push(i);
		vl dist(n, INT_MIN);
		dist[i] = 0;
		while(!q.empty()){
			ll cur = q.front();
			q.pop();
			for(auto &x : conexiones[cur]){
				if(dist[x] == INT_MIN){
					dist[x] = dist[cur]+1;
					q.push(x);
				}
			}
		}
		ff(j, i+1, n){
			c += dist[j];
			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: 21 / 21
• Subtask 3: 0 / 23
• Subtask 4: 0 / 45