이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
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);
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) {
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);
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
*/
컴파일 시 표준 에러 (stderr) 메시지
city.cpp: In function 'int DistanceSum(int, int*, int*)':
city.cpp:50:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
50 | for (int j = 0; j < pts[i].size(); j++) {
| ~~^~~~~~~~~~~~~~~
city.cpp:54:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
54 | while (k < pts[i - 1].size() && pts[i - 1][k] < pts[i][j]) {
| ~~^~~~~~~~~~~~~~~~~~~
city.cpp:57:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
57 | if (k < pts[i - 1].size() && pts[i - 1][k] == pts[i][j]) {
| ~~^~~~~~~~~~~~~~~~~~~
city.cpp:62:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
62 | if (j == pts[i].size() - 1 || pts[i][j] + 1 < pts[i][j + 1]) {
| ~~^~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |