#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pp;
typedef vector<int> vec;
typedef vector<vec> mat;
#define pb push_back
#define MOD 1000000000
struct pt{
int x,y,v;
pt(){}
pt(int x_,int y_):x(x_),y(y_){}
bool operator<(const pt& r)const{
return x!=r.x?x<r.x:y<r.y;
}
}s[100000];
mat path;
int n;
int cnt[100000];
ll dfs(int v,int p,ll &ans){
ll ret=0;
for(int i=0;i<path[v].size();i++){
int u=path[v][i];
if(u==p)continue;
ret+=dfs(u,v,ans);
}
ret+=cnt[v];
ans+=(n-ret)*ret;
ans%=MOD;
return ret;
}
int f(int N, int *X, int *Y) {
n=N;
for(int i=0;i<N;i++)s[i]=pt(X[i],Y[i]);
sort(s,s+N);
int sz=0;
for(int i=0;i<N;i++){
int p=i;
while(s[i].x==s[i+1].x)i++;
int v=p;
while(v<=i){
while(v<i&&s[v].y+1==s[v+1].y){
s[v].v=sz;
v++;
}
s[v].v=sz;
cnt[sz++]=s[v].y-s[p].y+1;
p=++v;
}
}
path.clear();
path.assign(sz,vec());
for(int i=0;i<N;i++){
pt* it=lower_bound(s,s+N,pt(s[i].x-1,s[i].y));
if(it->x==s[i].x-1&&it->y==s[i].y)path[s[i].v].pb(it->v);
it=lower_bound(s,s+N,pt(s[i].x+1,s[i].y));
if(it->x==s[i].x+1&&it->y==s[i].y)path[s[i].v].pb(it->v);
}
for(int i=0;i<sz;i++){
sort(path[i].begin(),path[i].end());
path[i].erase(unique(path[i].begin(),path[i].end()),path[i].end());
}
ll ret=0;
dfs(0,0,ret);
return (int)ret;
}
int DistanceSum(int N, int *X, int *Y){
return (f(N,X,Y)+f(N,Y,X))%MOD;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
3284 KB |
Output is correct |
| 2 |
Correct |
0 ms |
3284 KB |
Output is correct |
| 3 |
Correct |
0 ms |
3284 KB |
Output is correct |
| 4 |
Correct |
0 ms |
3416 KB |
Output is correct |
| 5 |
Correct |
0 ms |
3416 KB |
Output is correct |
| 6 |
Correct |
0 ms |
3416 KB |
Output is correct |
| 7 |
Correct |
0 ms |
3416 KB |
Output is correct |
| 8 |
Correct |
0 ms |
3416 KB |
Output is correct |
| 9 |
Correct |
0 ms |
3416 KB |
Output is correct |
| 10 |
Correct |
0 ms |
3416 KB |
Output is correct |
| 11 |
Correct |
0 ms |
3416 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
3416 KB |
Output is correct |
| 2 |
Correct |
0 ms |
3416 KB |
Output is correct |
| 3 |
Correct |
2 ms |
3420 KB |
Output is correct |
| 4 |
Correct |
2 ms |
3420 KB |
Output is correct |
| 5 |
Correct |
2 ms |
3420 KB |
Output is correct |
| 6 |
Correct |
0 ms |
3420 KB |
Output is correct |
| 7 |
Correct |
2 ms |
3420 KB |
Output is correct |
| 8 |
Correct |
0 ms |
3420 KB |
Output is correct |
| 9 |
Correct |
0 ms |
3420 KB |
Output is correct |
| 10 |
Correct |
2 ms |
3420 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
19 ms |
3756 KB |
Output is correct |
| 2 |
Correct |
19 ms |
3756 KB |
Output is correct |
| 3 |
Correct |
46 ms |
4344 KB |
Output is correct |
| 4 |
Correct |
46 ms |
4236 KB |
Output is correct |
| 5 |
Correct |
90 ms |
5400 KB |
Output is correct |
| 6 |
Correct |
92 ms |
5376 KB |
Output is correct |
| 7 |
Correct |
96 ms |
5324 KB |
Output is correct |
| 8 |
Correct |
97 ms |
5392 KB |
Output is correct |
| 9 |
Correct |
97 ms |
5340 KB |
Output is correct |
| 10 |
Correct |
95 ms |
8592 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
22 ms |
3944 KB |
Output is correct |
| 2 |
Correct |
21 ms |
3812 KB |
Output is correct |
| 3 |
Correct |
56 ms |
4928 KB |
Output is correct |
| 4 |
Correct |
50 ms |
4660 KB |
Output is correct |
| 5 |
Correct |
110 ms |
6444 KB |
Output is correct |
| 6 |
Correct |
110 ms |
5904 KB |
Output is correct |
| 7 |
Correct |
102 ms |
6604 KB |
Output is correct |
| 8 |
Correct |
112 ms |
5852 KB |
Output is correct |
| 9 |
Correct |
115 ms |
5652 KB |
Output is correct |
| 10 |
Correct |
104 ms |
5512 KB |
Output is correct |
