oj.uz

답안 #577240

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
577240 2022-06-14T10:13:27 Z Justin1 이상적인 도시 (IOI12_city) C++14
55 / 100
 614 ms 40844 KB 
#include <bits/stdc++.h>
#define f first
#define s second
#define ll long long
#define pii pair<int,int>
using namespace std;
 
vector<pii> dir = {{0,1},{1,0},{-1,0},{0,-1}};
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]);
}
 
ll bfs(int sx, int sy) {
	ll ans = 0;
	queue<pair<pii,int>> nxt;
	nxt.push({{sx,sy},0});
	while (!nxt.empty()) {
		auto tmp = nxt.front();
		nxt.pop();
		if (v[tmp.f.f][tmp.f.s]) continue;
		v[tmp.f.f][tmp.f.s] = 1;
		ans += tmp.s;
		for (auto i : dir) {
			if (!v[tmp.f.f+i.f][tmp.f.s+i.s] && ar[tmp.f.f+i.f][ tmp.f.s+i.s]) {
				nxt.push({{tmp.f.f+i.f, tmp.f.s+i.s}, tmp.s+1});
			}
		}
	}  
	return ans;
}

int DistanceSum(int N, int *X, int *Y) {
	if (N <= 2000) {
		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;
		ll ans = 0;
		for (int i = 0; i < N; i++) ar[X[i]][Y[i]] = 1;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) v[X[j]][Y[j]] = 0;
			ans += bfs(X[i],Y[i]);
		}
		return (ans/2) % 1'000'000'000;
	} else {
		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
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 11216 KB Output is correct
2 Correct 7 ms 11272 KB Output is correct
3 Correct 6 ms 11220 KB Output is correct
4 Correct 8 ms 11220 KB Output is correct
5 Correct 8 ms 11268 KB Output is correct
6 Correct 11 ms 11272 KB Output is correct
7 Correct 10 ms 11284 KB Output is correct
8 Correct 12 ms 11312 KB Output is correct
9 Correct 12 ms 11272 KB Output is correct
10 Correct 11 ms 11268 KB Output is correct
11 Correct 11 ms 11220 KB Output is correct

Subtask #2
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 142 ms 11432 KB Output is correct
2 Correct 139 ms 11400 KB Output is correct
3 Correct 306 ms 11540 KB Output is correct
4 Correct 273 ms 11528 KB Output is correct
5 Correct 588 ms 11620 KB Output is correct
6 Correct 549 ms 11544 KB Output is correct
7 Correct 614 ms 11604 KB Output is correct
8 Correct 475 ms 11484 KB Output is correct
9 Correct 470 ms 11516 KB Output is correct
10 Correct 444 ms 11524 KB Output is correct

Subtask #3
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 14804 KB Output is correct
2 Correct 26 ms 15192 KB Output is correct
3 Correct 50 ms 19904 KB Output is correct
4 Correct 40 ms 20008 KB Output is correct
5 Correct 70 ms 31328 KB Output is correct
6 Correct 73 ms 31860 KB Output is correct
7 Correct 70 ms 27096 KB Output is correct
8 Correct 80 ms 33264 KB Output is correct
9 Correct 103 ms 33740 KB Output is correct
10 Correct 90 ms 40844 KB Output is correct

Subtask #4
0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 23 ms 15248 KB Output isn't correct
2 Halted 0 ms 0 KB -