제출 #61757

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
61757		aome	이상적인 도시 (IOI12_city)	C++17	100 / 100	763 ms	34488 KiB

city

#include <bits/stdc++.h>

using namespace std;

const int N = 100005;
const int mod = 1e9;
const int INF = 2147483646;

const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, -1, 1};

int n;
int res;
int sz[N];
int cnt[N];
int par[N];
int sum2[N];
int X[N], Y[N];
bool visit[N];
vector<int> G[N];
vector<int> G2[N];
vector<int> vec[N];
pair<int, int> L[N], R[N];
map< pair<int, int>, int > label;

int find(int u) {
	return u == par[u] ? u : par[u] = find(par[u]);
}

void join(int u, int v) {
	par[find(u)] = find(v);
}

struct Data {
	int val, cnt, type;

	bool operator < (const Data& rhs) const {
		return val < rhs.val;
	}
};

int calc(vector<Data> &vec) {
	sort(vec.begin(), vec.end());
	int ret = 0, sum;
	sum = 0;
	for (auto i : vec) sum2[i.type] = 0;
	for (auto i : vec) {
		int tmp = (sum + mod - sum2[i.type]) % mod;
		ret = (ret + 1LL * tmp * i.val % mod * i.cnt) % mod;
		sum = (sum + i.cnt) % mod;
		sum2[i.type] = (sum2[i.type] + i.cnt) % mod;
	}
	reverse(vec.begin(), vec.end());
	sum = 0;
	for (auto i : vec) sum2[i.type] = 0;
	for (auto i : vec) {
		int tmp = (sum + mod - sum2[i.type]) % mod;
		ret = (ret + mod - 1LL * tmp * i.val % mod * i.cnt % mod) % mod;
		sum = (sum + i.cnt) % mod;
		sum2[i.type] = (sum2[i.type] + i.cnt) % mod;
	}
	return ret;
}

void dfs(int u) {
	sz[u] = vec[u].size();
	visit[u] = 1;
	vector<Data> vec2;
	for (auto i : vec[u]) {
		for (auto j : G[i]) {
			int v = find(j);
			if (visit[v]) continue;
			// cout << u << ' ' << v << '\n';
			L[v] = {INF, 0}, R[v] = {-INF, 0};
			for (auto k : vec[v]) {
				for (auto l : G[k]) {
					if (find(l) != u) continue;
					L[v] = min(L[v], {Y[k], k});
					R[v] = max(R[v], {Y[k], k});
				}
			}
			dfs(v), sz[u] += sz[v];
			for (auto k : vec[v]) {
				for (auto l : G[k]) {
					if (find(l) != u) continue;
					cnt[l] += cnt[k];
					vec2.push_back({Y[k], cnt[k], v});
					res = (res + 1LL * cnt[k] * (n - sz[v])) % mod;
					// cout << k << ' ' << cnt[k] << ' ' << n - sz[v] << '\n';
				}
			}
		}
	}
	for (auto i : vec[u]) {
		vec2.push_back({Y[i], 1, i});
	}
	int tmp = calc(vec2);
	res = (res + tmp) % mod;
	// cout << "#at " << u << '\n';
	// for (auto i : vec2) cout << i.first << ' ' << i.second << '\n';
	// cout << tmp << '\n';
	if (u == find(0)) return;
	for (auto i : vec[u]) {
		if (L[u].first <= Y[i] && Y[i] <= R[u].first) continue;
		if (Y[i] < L[u].first) {
			res = (res + 1LL * cnt[i] * (n - sz[u]) % mod * (L[u].first - Y[i])) % mod;
			cnt[L[u].second] += cnt[i];
		}
		if (Y[i] > R[u].first) {
			res = (res + 1LL * cnt[i] * (n - sz[u]) % mod * (Y[i] - R[u].first)) % mod;
			cnt[R[u].second] += cnt[i];
		}
	}
}

int DistanceSum(int _n, int *_X, int *_Y) {
	n = _n;
	for (int i = 0; i < n; ++i) X[i] = _X[i], Y[i] = _Y[i];
	for (int i = 0; i < n; ++i) {
		label[{X[i], Y[i]}] = i;
	}
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < 4; ++j) {
			int x = X[i] + dx[j], y = Y[i] + dy[j];
			if (label.count({x, y})) {
				int id = label[{x, y}];
				G[i].push_back(id);
			}
		}
	}
	for (int i = 0; i < n; ++i) par[i] = i;
	for (int i = 0; i < n; ++i) {
		for (auto j : G[i]) {
			if (X[i] == X[j]) join(i, j);
		}
	}
	for (int i = 0; i < n; ++i) {
		cnt[i] = 1, vec[find(i)].push_back(i);
	}
	dfs(find(0));
	return res;
}

• Subtask 1: 11 / 11
• Subtask 2: 21 / 21
• Subtask 3: 23 / 23
• Subtask 4: 45 / 45