| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 469072 | ntabc05101 | 이상적인 도시 (IOI12_city) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
const int mod = 1e9;
int N;
long long res;
vector< vector<int> > adj;
vector<int> w;
int dfs(int u, int p) {
int W = w[u];
for (auto &to: adj[u]) {
if (to != p) {
int v = dfs(to, u);
(res += 1ll * v * (N - v)) %= mod;
W += v;
}
}
return W;
}
int DistanceSum(int N, int *X, int *Y) {
::N = N;
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;
}
res = 0;
vector<int> c, d;
vector< vector<int> > pts;
for (int e = 0; e < 2; e++) {
pts.assign(mxX, vector<int>());
for (int i = 0; i < N; i++) {
pts[X[i]].push_back(Y[i]);
}
int cur = 0, cnt = 0;
w.clear(); c.clear(); d.clear();
adj.clear();
adj.push_back(vector<int>());
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);
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]) {
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>());
}
}
swap(c, d);
}
for (auto& ad: adj) {
sort(ad.begin(), ad.end());
ad.resize(unique(ad.begin(), ad.end()) - ad.begin());
/*for (auto& _: ad) {
cout << _ << " ";
}
cout << "\n";*/
}
dfs(0, -1);
for (int i = 0; i < N; i++) {
swap(X[i], Y[i]);
}
swap(mxX, mxY);
}
return res;
}
int main() {
cin.tie(0)->sync_with_stdio(0);
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
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
*/