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;
const int MOD = 1e9;
struct nhelp{
int x;
};
const int N = 1e5 + 5;
set<int> gr[N];
int sz[N];
void dfs(int nod, int dad, long long &ans, int tot){
for(auto x:gr[nod]){
if(x == dad)
continue;
dfs(x, nod, ans, tot);
sz[nod] += sz[x];
}
ans += 1LL * sz[nod] * (tot - sz[nod]) % MOD;
ans %= MOD;
}
long long solve(vector<pair<pair<int, int>, int>> coord){
sort(coord.begin(), coord.end());
int n = coord.size();
int nrnod = 0;
for(int i = 0; i < n; i++){
if(i == 0)
coord[i].second = ++nrnod, sz[nrnod] = 1;
else if(coord[i].first.first == coord[i - 1].first.first && coord[i].first.second == coord[i - 1].first.second + 1)
coord[i].second = coord[i - 1].second, sz[coord[i - 1].second]++;
else
coord[i].second = ++nrnod, sz[nrnod] = 1;
}
for(int i = 0; i < n; i++){
swap(coord[i].first.first, coord[i].first.second);
}
sort(coord.begin(), coord.end());
for(int i = 0; i < n; i++){
if(i > 0 && coord[i].first.first == coord[i - 1].first.first && coord[i].first.second == coord[i - 1].first.second + 1){
int a = coord[i].second, b = coord[i - 1].second;
gr[a].insert(b);
gr[b].insert(a);
}
}
long long ans = 0;
dfs(1, 0, ans, n);
for(int i =1 ; i<=nrnod; i++){
gr[i].clear();
sz[i] = 0;
}
return ans;
}
int DistanceSum(int N, int *X, int *Y) {
vector<pair<pair<int, int>, int>> coord(N);
for(int i = 0; i < N; i++){
coord[i] = {{X[i], Y[i]}, 0};
}
int ans1 = solve(coord);
for(int i = 0; i < coord.size(); i++){
swap(coord[i].first.first, coord[i].first.second);
coord[i].second = 0;
}
int ans2 = solve(coord);
return (1LL * ans1 + ans2) % MOD;
}
Compilation message (stderr)
city.cpp: In function 'int DistanceSum(int, int*, int*)':
city.cpp:57:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
57 | for(int i = 0; i < coord.size(); i++){
| ~~^~~~~~~~~~~~~~
# | 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... |