oj.uz

Submission #124317

# Submission time Handle Problem Language Result Execution time Memory
124317 2019-07-03T03:56:51 Z turbat Ideal city (IOI12_city) C++14
100 / 100
 221 ms 28260 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(X[s1], Y[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(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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9720 KB Output is correct
2 Correct 11 ms 9700 KB Output is correct
3 Correct 10 ms 9720 KB Output is correct
4 Correct 10 ms 9720 KB Output is correct
5 Correct 11 ms 9592 KB Output is correct
6 Correct 11 ms 9720 KB Output is correct
7 Correct 11 ms 9748 KB Output is correct
8 Correct 11 ms 9720 KB Output is correct
9 Correct 10 ms 9720 KB Output is correct
10 Correct 10 ms 9720 KB Output is correct
11 Correct 11 ms 9720 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 9848 KB Output is correct
2 Correct 11 ms 9848 KB Output is correct
3 Correct 12 ms 9848 KB Output is correct
4 Correct 12 ms 9976 KB Output is correct
5 Correct 13 ms 9948 KB Output is correct
6 Correct 13 ms 9948 KB Output is correct
7 Correct 13 ms 9948 KB Output is correct
8 Correct 13 ms 9976 KB Output is correct
9 Correct 15 ms 9976 KB Output is correct
10 Correct 13 ms 9976 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 12280 KB Output is correct
2 Correct 34 ms 12536 KB Output is correct
3 Correct 96 ms 16504 KB Output is correct
4 Correct 76 ms 16504 KB Output is correct
5 Correct 212 ms 23456 KB Output is correct
6 Correct 158 ms 23384 KB Output is correct
7 Correct 181 ms 23416 KB Output is correct
8 Correct 194 ms 23352 KB Output is correct
9 Correct 138 ms 23112 KB Output is correct
10 Correct 104 ms 28260 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 11868 KB Output is correct
2 Correct 44 ms 12308 KB Output is correct
3 Correct 106 ms 15356 KB Output is correct
4 Correct 95 ms 15684 KB Output is correct
5 Correct 200 ms 21064 KB Output is correct
6 Correct 208 ms 21340 KB Output is correct
7 Correct 209 ms 21460 KB Output is correct
8 Correct 221 ms 21508 KB Output is correct
9 Correct 219 ms 20992 KB Output is correct
10 Correct 201 ms 21008 KB Output is correct