#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define f first
#define s second
using namespace std;
const int Nn = 1e5 + 5;
ll tot[Nn], ans, mod = 1e9;
int n, id[Nn], x[Nn], y[Nn], c[Nn];
int a[4] = {1, -1, 0, 0};
int b[4] = {0, 0, 1, -1};
map < pair < int , int > , int > f;
vector < int > v[Nn];
void dfs(int x, int p) {
tot[x] = c[x];
for (int i = 0; i < v[x].size(); ++i) {
int to = v[x][i];
if (to == p) continue;
dfs(to, x);
tot[x] += tot[to];
}
ans += (tot[x] * (n - tot[x])) % mod;
ans %= mod;
}
void solve() {
vector < pair < pair < int , int > , int > > s;
for (int i = 0; i < n; ++i) {
f[{x[i], y[i]}] = i;
s.pb({{x[i], y[i]}, i});
}
sort(s.begin(), s.end());
int nd = 0;
for (int i = 0; i < s.size(); ++i) {
if (!i || (s[i - 1].f.f != s[i].f.f || s[i - 1].f.s + 1 < s[i].f.s)) ++nd;
id[s[i].s] = nd, ++c[nd];
}
vector < pair < int , int > > ss;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < 2; ++j) {
int Ax = x[i] + a[j], Ay = y[i] + b[j];
if (f.find({Ax, Ay}) != f.end()) {
int A = id[i];
int B = id[f[{Ax, Ay}]];
if (A > B) swap(A, B);
ss.pb({A, B});
}
}
}
sort(ss.begin(), ss.end());
for (int i = 0; i < ss.size(); ++i) {
if (!i || ss[i - 1] != ss[i]) {
v[ss[i].f].pb(ss[i].s);
v[ss[i].s].pb(ss[i].f);
}
}
dfs(1, 1);
}
void clear() {
f.clear();
for (int i = 1; i <= n; ++i) {
v[i].clear(), c[i] = tot[i] = 0;
}
for (int i = 0; i < n; ++i) {
swap(x[i], y[i]);
}
}
int DistanceSum(int nn, int *X, int *Y) {
n = nn;
for (int i = 0; i < n; ++i) {
x[i] = X[i], y[i] = Y[i];
}
solve();
clear();
solve();
return ans;
}
Compilation message
city.cpp: In function 'void dfs(int, int)':
city.cpp:21:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
21 | for (int i = 0; i < v[x].size(); ++i) {
| ~~^~~~~~~~~~~~~
city.cpp: In function 'void solve()':
city.cpp:39: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]
39 | for (int i = 0; i < s.size(); ++i) {
| ~~^~~~~~~~~~
city.cpp:56:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
56 | for (int i = 0; i < ss.size(); ++i) {
| ~~^~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2644 KB |
Output is correct |
2 |
Correct |
1 ms |
2644 KB |
Output is correct |
3 |
Correct |
2 ms |
2644 KB |
Output is correct |
4 |
Correct |
2 ms |
2644 KB |
Output is correct |
5 |
Correct |
2 ms |
2644 KB |
Output is correct |
6 |
Correct |
1 ms |
2644 KB |
Output is correct |
7 |
Correct |
2 ms |
2644 KB |
Output is correct |
8 |
Correct |
2 ms |
2644 KB |
Output is correct |
9 |
Correct |
2 ms |
2644 KB |
Output is correct |
10 |
Correct |
2 ms |
2688 KB |
Output is correct |
11 |
Correct |
2 ms |
2644 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
2772 KB |
Output is correct |
2 |
Correct |
3 ms |
2772 KB |
Output is correct |
3 |
Correct |
4 ms |
2900 KB |
Output is correct |
4 |
Correct |
5 ms |
2900 KB |
Output is correct |
5 |
Correct |
5 ms |
2900 KB |
Output is correct |
6 |
Correct |
5 ms |
2884 KB |
Output is correct |
7 |
Correct |
5 ms |
2900 KB |
Output is correct |
8 |
Correct |
5 ms |
2964 KB |
Output is correct |
9 |
Correct |
5 ms |
2900 KB |
Output is correct |
10 |
Correct |
5 ms |
2956 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
45 ms |
5644 KB |
Output is correct |
2 |
Correct |
45 ms |
5848 KB |
Output is correct |
3 |
Correct |
127 ms |
10308 KB |
Output is correct |
4 |
Correct |
129 ms |
10400 KB |
Output is correct |
5 |
Correct |
301 ms |
17740 KB |
Output is correct |
6 |
Correct |
329 ms |
18136 KB |
Output is correct |
7 |
Correct |
347 ms |
18212 KB |
Output is correct |
8 |
Correct |
321 ms |
17904 KB |
Output is correct |
9 |
Correct |
303 ms |
18152 KB |
Output is correct |
10 |
Correct |
254 ms |
20800 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
44 ms |
5532 KB |
Output is correct |
2 |
Correct |
48 ms |
5756 KB |
Output is correct |
3 |
Correct |
120 ms |
10144 KB |
Output is correct |
4 |
Correct |
124 ms |
10624 KB |
Output is correct |
5 |
Correct |
280 ms |
17608 KB |
Output is correct |
6 |
Correct |
321 ms |
18476 KB |
Output is correct |
7 |
Correct |
278 ms |
17772 KB |
Output is correct |
8 |
Correct |
308 ms |
18240 KB |
Output is correct |
9 |
Correct |
301 ms |
18024 KB |
Output is correct |
10 |
Correct |
302 ms |
17916 KB |
Output is correct |