oj.uz

답안 #801941

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
801941 2023-08-02T08:32:12 Z pavement 이상적인 도시 (IOI12_city) C++17
0 / 100
 11 ms 6148 KB 
#include <bits/stdc++.h>
using namespace std;

#define mp make_pair
#define eb emplace_back

using ii = pair<int, int>;

int rep[100005];
vector<ii> row[100005], col[100005];

namespace ufds {
	int lnk[100005], sz[100005];
	
	void init(int n) {
		iota(lnk, lnk + n, 0);
		fill(sz, sz + n, 1);
	}
	int find(int x) {
		if (x == lnk[x]) return x;
		return lnk[x] = find(lnk[x]);
	}
	void unite(int a, int b) {
		a = find(a);
		b = find(b);
		if (a == b) return;
		if (sz[b] > sz[a]) swap(a, b);
		sz[a] += sz[b];
		lnk[b] = a;
	}
};

int DistanceSum(int N, int X[], int Y[]) {
	int ans = 0, min_X = *min_element(X, X + N), min_Y = *min_element(Y, Y + N);
	for (int i = 0; i < N; i++) {
		X[i] -= min_X;
		Y[i] -= min_Y;
		row[X[i]].eb(Y[i], i);
		col[Y[i]].eb(X[i], i);
	}
	for (int i = 0; i < N; i++) {
		sort(row[i].begin(), row[i].end());
		sort(col[i].begin(), col[i].end());
	}
	for (auto dim : {row, col}) {
		ufds::init(N);
		int cnt = 0, ccs = 0, cur_prod = 0, tot_sz = 0;
		for (int i = 0; i < N; i++) {
			int prv_j = -1, prv_idx = -1;
			for (auto [j, cur] : dim[i]) {
				int upper = -1, idx;
				if (i) {
					auto it = lower_bound(dim[i - 1].begin(), dim[i - 1].end(), mp(j, 0));
					if (it != dim[i - 1].end() && it->first == j) {
						upper = ufds::find(rep[it->second]);
					}
				}
				if (upper == -1) {
					idx = cnt++;
					ccs++;
					cur_prod += tot_sz;
					tot_sz++;
				} else {
					idx = upper;
					cur_prod += tot_sz - ufds::sz[upper];
					ufds::sz[upper]++;
					tot_sz++;
				}
				rep[cur] = idx;
				if (prv_j != -1 && prv_j + 1 == j) {
					if (ufds::find(prv_idx) != ufds::find(idx)) {
						ccs--;
						cur_prod -= ufds::sz[ufds::find(prv_idx)] * (tot_sz - ufds::sz[ufds::find(prv_idx)]);
						tot_sz -= ufds::sz[ufds::find(prv_idx)];
						cur_prod -= ufds::sz[ufds::find(idx)] * (tot_sz - ufds::sz[ufds::find(idx)]);
						tot_sz -= ufds::sz[ufds::find(idx)];
						ufds::unite(prv_idx, idx);
						cur_prod += tot_sz * ufds::sz[ufds::find(prv_idx)];
						tot_sz += ufds::sz[ufds::find(prv_idx)];
					}
				}
				prv_j = j;
				prv_idx = idx;
			}
			//~ cout << "@ " << i << ' ' << cur_prod << ' ' << tot_sz << endl;
			ans += 2 * cur_prod + tot_sz * (N - tot_sz);
		}
	}
	for (auto dim : {row, col}) {
		ufds::init(N);
		int cnt = 0, ccs = 0, cur_prod = 0, tot_sz = 0;
		for (int i = N - 1; i >= 0; i--) {
			int prv_j = -1, prv_idx = -1;
			for (auto [j, cur] : dim[i]) {
				int upper = -1, idx;
				if (i + 1 < N) {
					auto it = lower_bound(dim[i + 1].begin(), dim[i + 1].end(), mp(j, 0));
					if (it != dim[i + 1].end() && it->first == j) {
						upper = ufds::find(rep[it->second]);
					}
				}
				if (upper == -1) {
					idx = cnt++;
					ccs++;
					cur_prod += tot_sz;
					tot_sz++;
				} else {
					idx = upper;
					cur_prod += tot_sz - ufds::sz[upper];
					ufds::sz[upper]++;
					tot_sz++;
				}
				rep[cur] = idx;
				if (prv_j != -1 && prv_j + 1 == j) {
					if (ufds::find(prv_idx) != ufds::find(idx)) {
						ccs--;
						cur_prod -= ufds::sz[ufds::find(prv_idx)] * (tot_sz - ufds::sz[ufds::find(prv_idx)]);
						tot_sz -= ufds::sz[ufds::find(prv_idx)];
						cur_prod -= ufds::sz[ufds::find(idx)] * (tot_sz - ufds::sz[ufds::find(idx)]);
						tot_sz -= ufds::sz[ufds::find(idx)];
						ufds::unite(prv_idx, idx);
						cur_prod += tot_sz * ufds::sz[ufds::find(prv_idx)];
						tot_sz += ufds::sz[ufds::find(prv_idx)];
					}
				}
				prv_j = j;
				prv_idx = idx;
			}
			//~ cout << "@ " << i << ' ' << cur_prod << ' ' << tot_sz << endl;
			ans += 2 * cur_prod;
		}
	}
	return ans;
}

Subtask #1
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 5020 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Incorrect 3 ms 4948 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

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

Subtask #3
0 / 23.0

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

Subtask #4
0 / 45.0

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