| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 469063 | ntabc05101 | Ideal city (IOI12_city) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
int DistanceSum(int N, int *X, int *Y) {
int mnX = (1LL << 31) - 2, mnY = mnX, mxX = 0, mxY = 0;
for (int i = 0; i < N; i++) {
mnX = min(mnX, X[i]); mnY = min(mnY, Y[i]);
mxX = max(mxX, X[i]); mxY = max(mxY, Y[i]);
}
mxX -= mnX - 1; mxY -= mnY - 1;
for (int i = 0; i < N; i++) {
X[i] -= mnX; Y[i] -= mnY;
}
long long res = 0;
for (int e = 0; e < 2; e++) {
vector<int> pts[mxX];
for (int i = 0; i < N; i++) {
pts[X[i]].push_back(Y[i]);
}
int cur = 0, cnt = 0;
vector<int> c, d, w;
vector< vector<int> > adj(1);
for (int i = 0; i < mxX; i++) {
sort(pts[i].begin(), pts[i].end());
int k = 0;
d.clear();
for (int j = 0; j < pts[i].size(); j++) {
d.push_back(cur);
//cout << cur << " ";
//cout << pts[i][j] << " ";
cnt++;
if (i > 0) {
while (k < pts[i - 1].size() && pts[i - 1][k] < pts[i][j]) {
k++;
}
if (k < pts[i - 1].size() && pts[i - 1][k] == pts[i][j]) {
//cout << " " << cur << " " << c[k] << "\n";
adj[cur].push_back(c[k]);
adj[c[k]].push_back(cur);
}
}
if (j == pts[i].size() - 1 || pts[i][j] + 1 < pts[i][j + 1]) {
w.push_back(cnt);
cur++; cnt = 0;
adj.push_back(vector<int>());
}
}
//cout << "\n";
swap(c, d);
}
for (auto& ad: adj) {
/*for (auto& _: ad) {
cout << _ << " ";
}
cout << "\n";*/
ad.resize(unique(ad.begin(), ad.end()) - ad.begin());
}
function<long long(int, int)> dfs = [&](int u, int p) {
long long W = w[u];
for (auto &to: adj[u]) {
if (to != p) {
int v = dfs(to, u);
res += 1ll * v * (N - v);
W += v;
}
}
return W;
};
dfs(0, -1);
for (int i = 0; i < N; i++) {
swap(X[i], Y[i]);
}
}
return res;
}
int main() {
//cin.tie(0)->sync_with_stdio(0);
int N; cin >> N;
int *X = new int[N], *Y = new int[N];
for (int i = 0; i < N; i++) {
cin >> X[i] >> Y[i];
}
cout << DistanceSum(N, X, Y) << "\n";
return 0;
}
/*
11
2 5
2 6
3 3
3 6
4 3
4 4
4 5
4 6
5 3
5 4
5 6
*/