#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int mod = 1e9, maxn = 1e5 + 5;
void upd(int &a, const int &b) { a = (a + b) % mod; }
int add(const int &a, const int &b) { return (a + b) % mod; }
int mul(const int &a, const int &b) { return (a * 1ll * b) % (ll)mod; }
vector<int> g[maxn];
int sz[maxn];
struct bod { int x, y; };
bool cmp(const bod &a, const bod &b) { return (a.x == b.x) ? a.y < b.y : a.x < b.x; }
int ans = 0, n;
void dfs(int u, int p = -1)
{
for (int v : g[u]) if (v != p) dfs(v, u), sz[u] += sz[v];
upd(ans, mul(sz[u], n - sz[u]));
}
void calculate_x_dist(vector<bod> v)
{
for (int i = 0; i < n; i++) g[i].clear(), sz[i] = 0;
map<pair<int, int>, int> m;
set<pair<int, int> > e;
sort(v.begin(), v.end(), cmp);
int cnt = 0;
for (int i = 0; i < n; i++)
{
if (i && (v[i-1].x != v[i].x || v[i-1].y+1 != v[i].y)) cnt++;
m[{v[i].x, v[i].y}] = cnt;
sz[cnt]++;
if (m.count({v[i].x-1, v[i].y})) e.insert({m[{v[i].x-1, v[i].y}], cnt});
}
for (pair<int, int> i : e) g[i.first].push_back(i.second), g[i.second].push_back(i.first);
dfs(0);
}
int DistanceSum(int N, int *x, int *y)
{
n = N; vector<bod> v;
for (int i = 0; i < n; i++) v.push_back({x[i], y[i]});
calculate_x_dist(v);
for (int i = 0; i < n; i++) swap(v[i].x, v[i].y);
calculate_x_dist(v);
return ans;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
2636 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2636 KB |
Output is correct |
| 3 |
Correct |
2 ms |
2636 KB |
Output is correct |
| 4 |
Correct |
1 ms |
2636 KB |
Output is correct |
| 5 |
Correct |
3 ms |
2636 KB |
Output is correct |
| 6 |
Correct |
2 ms |
2636 KB |
Output is correct |
| 7 |
Correct |
0 ms |
2636 KB |
Output is correct |
| 8 |
Correct |
2 ms |
2596 KB |
Output is correct |
| 9 |
Correct |
2 ms |
2636 KB |
Output is correct |
| 10 |
Correct |
2 ms |
2756 KB |
Output is correct |
| 11 |
Correct |
2 ms |
2636 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
2764 KB |
Output is correct |
| 2 |
Correct |
3 ms |
2764 KB |
Output is correct |
| 3 |
Correct |
4 ms |
2788 KB |
Output is correct |
| 4 |
Correct |
4 ms |
2764 KB |
Output is correct |
| 5 |
Correct |
5 ms |
2892 KB |
Output is correct |
| 6 |
Correct |
4 ms |
2892 KB |
Output is correct |
| 7 |
Correct |
5 ms |
2892 KB |
Output is correct |
| 8 |
Correct |
4 ms |
2764 KB |
Output is correct |
| 9 |
Correct |
5 ms |
2764 KB |
Output is correct |
| 10 |
Correct |
5 ms |
2892 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
23 ms |
4552 KB |
Output is correct |
| 2 |
Correct |
25 ms |
4552 KB |
Output is correct |
| 3 |
Correct |
61 ms |
7232 KB |
Output is correct |
| 4 |
Correct |
65 ms |
7352 KB |
Output is correct |
| 5 |
Correct |
154 ms |
11712 KB |
Output is correct |
| 6 |
Correct |
153 ms |
11840 KB |
Output is correct |
| 7 |
Correct |
130 ms |
11996 KB |
Output is correct |
| 8 |
Correct |
135 ms |
11676 KB |
Output is correct |
| 9 |
Correct |
159 ms |
12108 KB |
Output is correct |
| 10 |
Correct |
154 ms |
16636 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
27 ms |
5112 KB |
Output is correct |
| 2 |
Correct |
35 ms |
5144 KB |
Output is correct |
| 3 |
Correct |
74 ms |
9148 KB |
Output is correct |
| 4 |
Correct |
71 ms |
8644 KB |
Output is correct |
| 5 |
Correct |
155 ms |
15792 KB |
Output is correct |
| 6 |
Correct |
151 ms |
13844 KB |
Output is correct |
| 7 |
Correct |
173 ms |
15892 KB |
Output is correct |
| 8 |
Correct |
139 ms |
13896 KB |
Output is correct |
| 9 |
Correct |
141 ms |
13424 KB |
Output is correct |
| 10 |
Correct |
131 ms |
13376 KB |
Output is correct |
