oj.uz

Submission #124314

# Submission time Handle Problem Language Result Execution time Memory
124314 2019-07-03T03:54:34 Z turbat Ideal city (IOI12_city) C++14
0 / 100
 32 ms 12408 KB 
#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(Y[s1], X[s1]);
	return ans;
}

Compilation message

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(Y[s1], X[s1]);
                  ^
city.cpp:69:15: warning: 's' may be used uninitialized in this function [-Wmaybe-uninitialized]
  dfs(X[s], Y[s]);
               ^

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9848 KB Output is correct
2 Incorrect 10 ms 9720 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 9848 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 30 ms 12408 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Incorrect 32 ms 12024 KB Output isn't correct
2 Halted 0 ms 0 KB -