Submission #124317

#	Time	Username	Problem	Language	Result	Execution time	Memory
124317		turbat	Ideal city (IOI12_city)	C++14	100 / 100	221 ms	28260 KiB

city

#include <bits/stdc++.h>
using namespace std;

map <int, bool> m[100005], used[100005];
long long ans, mod = 1e9;
int n;

int dfs(int x, int y){
	int s = 0, ty = y - 1;
	vector <pair <int, int> > v;
	while (m[x].count(ty + 1)){
		s++;
		used[x][++ty] = 1;
		if (m[x + 1].count(ty)) v.push_back({x + 1, ty});
		if (m[x - 1].count(ty)) v.push_back({x - 1, ty});
	}
	ty = y;
	while (m[x].count(ty - 1)){
		s++;
		used[x][--ty] = 1;
		if (m[x + 1].count(ty)) v.push_back({x + 1, ty});
		if (m[x - 1].count(ty)) v.push_back({x - 1, ty});
	}
	for (auto to : v)
		if (!used[to.first].count(to.second))
			s += dfs(to.first, to.second);
	ans = (ans + 1ll * s * (n - s)) % mod;
	return s;
}

int dfs1(int x, int y){
	int s = 0, tx = x - 1;
	vector <pair <int, int> > v;
	while (m[tx + 1].count(y)){
		s++;
		used[++tx][y] = 1;
		if (m[tx].count(y + 1)) v.push_back({tx, y + 1});
		if (m[tx].count(y - 1)) v.push_back({tx, y - 1});
	}
	tx = x;
	while (m[tx - 1].count(y)){
		s++;
		used[--tx][y] = 1;
		if (m[tx].count(y + 1)) v.push_back({tx, y + 1});
		if (m[tx].count(y - 1)) v.push_back({tx, y - 1});
	}
	for (auto to : v)
		if (!used[to.first].count(to.second))
			s += dfs1(to.first, to.second);
	ans = (ans + 1ll * s * (n - s)) % mod;
	return s;
}

int DistanceSum(int N, int *X, int *Y) {
	n = N;
	int mnx = INT_MAX, mny = INT_MAX;
	for (int i = 0;i < n;i++){
		mnx = min(mnx, X[i]);
		mny = min(mny, Y[i]);
	}
	int s, s1;
	for (int i = 0;i < n;i++){
		X[i] = X[i] - mnx + 1;
		Y[i] = Y[i] - mny + 1; 
		if (X[i] == 1) s = i;
		if (Y[i] == 1) s1 = i;
		m[X[i]][Y[i]] = 1;
	}
	dfs(X[s], Y[s]);
	for (int i = 0;i < 100005;i++) used[i].clear();
	dfs1(X[s1], Y[s1]);
	return ans;
}

Compilation message (stderr)

city.cpp: In function 'int DistanceSum(int, int*, int*)':
city.cpp:71:18: warning: 's1' may be used uninitialized in this function [-Wmaybe-uninitialized]
  dfs1(X[s1], Y[s1]);
                  ^
city.cpp:69:15: warning: 's' may be used uninitialized in this function [-Wmaybe-uninitialized]
  dfs(X[s], Y[s]);
               ^

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