oj.uz

Submission #577238

# Submission time Handle Problem Language Result Execution time Memory
577238 2022-06-14T10:10:25 Z Justin1 Ideal city (IOI12_city) C++14
23 / 100
 96 ms 41512 KB 
#include <bits/stdc++.h>
#define f first
#define s second
#define ll long long
#define pii pair<int,int>
using namespace std;
 
unordered_map<int,int> ar[100005], v[100005];
ll ans = 0, n;
ll cntX[100005], cntY[100005];
 
void dfs(int x, int y, ll sum) {
	ans += sum;
	v[x][y] = 1;
	if (!v[x-1][y] && ar[x-1][y]) dfs(x-1,y,sum+cntX[n]-2*cntX[x-1]);
	if (!v[x+1][y] && ar[x+1][y]) dfs(x+1,y,sum-cntX[n]+2*cntX[x]);
	if (!v[x][y-1] && ar[x][y-1]) dfs(x,y-1,sum+cntY[n]-2*cntY[y-1]);
	if (!v[x][y+1] && ar[x][y+1]) dfs(x,y+1,sum-cntY[n]+2*cntY[y]);
}
 
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]);
	for (int i = 0; i < N; i++) mnY = min(mnY, Y[i]);
	for (int i = 0; i < N; i++) X[i] -= mnX-1;
	for (int i = 0; i < N; i++) Y[i] -= mnY-1;
 
	for (int i = 0; i < N; i++) cntX[X[i]]++, cntY[Y[i]]++;
	for (int i = 1; i <= N; i++) cntX[i] += cntX[i-1], cntY[i] += cntY[i-1];
	for (int i = 0; i < N; i++) ar[X[i]][Y[i]] = 1;
	int tmp = 0;
	for (int i = 1; i < N; i++) tmp += abs(X[i]-X[0]) + abs(Y[i]-Y[0]);
	dfs(X[0], Y[0], tmp);
	return (ans/2) % 1'000'000'000;
}

Subtask #1
0 / 11.0

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

Subtask #2
0 / 21.0

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

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 14780 KB Output is correct
2 Correct 22 ms 15280 KB Output is correct
3 Correct 37 ms 20256 KB Output is correct
4 Correct 36 ms 20136 KB Output is correct
5 Correct 68 ms 31916 KB Output is correct
6 Correct 71 ms 32524 KB Output is correct
7 Correct 65 ms 28024 KB Output is correct
8 Correct 69 ms 33884 KB Output is correct
9 Correct 73 ms 34348 KB Output is correct
10 Correct 96 ms 41512 KB Output is correct

Subtask #4
0 / 45.0

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