#include<bits/stdc++.h>
using namespace std;
const long long maxn=2000+10;
long long n,mod=1e9,vis[maxn];
vector<pair<long long,long long>>all;
vector<long long>adj[maxn],adja[maxn];
map<pair<long long,long long>,long long>mp;
long long mainres=0;
struct dsu{
long long par[maxn],sz[maxn];
dsu(){
for(long long i=0;i<maxn;i++){
par[i]=i;
sz[i]=1;
}
}
long long root(long long u){
if(u==par[u]){
return u;
}
return par[u]=root(par[u]);
}
long long con(long long u,long long v){
long long rootu=root(u),rootv=root(v);
if(rootu!=rootv){
par[rootu]=rootv;
sz[rootv]+=sz[rootu];
return 1;
}
return 0;
}
}ds1,ds2;
void bfs(long long u){
vector<long long>vis(n+1),high(n+1),bf;
bf.push_back(u);
vis[u]=1;
for(long long i=0;i<(long long)bf.size();i++){
for(auto x:adj[bf[i]]){
if(vis[x]==0){
vis[x]=1;
high[x]=high[bf[i]]+1;
bf.push_back(x);
if(x>=u)
mainres+=high[x];
mainres%=mod;
}
}
}
}
long long dfs(long long u,long long par=-1){
vis[u]=1;
long long ret=ds1.sz[u];
for(auto x:adj[u]){
if(x!=par){
ret+=dfs(x,u);
}
}
mainres+=(n-ret)*ret;
return ret;
}
long long solve2(){
for(long long i=0;i<n;i++){
mp[all[i]]=i;
}
for(long long i=0;i<n;i++){
if(mp.count(make_pair(all[i].first,all[i].second+1))!=0){
ds1.con(mp[make_pair(all[i].first,all[i].second+1)],i);
}
if(mp.count(make_pair(all[i].first+1,all[i].second))!=0){
ds2.con(mp[make_pair(all[i].first+1,all[i].second)],i);
}
}
for(long long i=0;i<n;i++){
if(mp.count(make_pair(all[i].first,all[i].second+1))!=0){
long long u=ds1.root(i);
long long v=ds1.root(mp[make_pair(all[i].first,all[i].second+1)]);
adj[u].push_back(v);
adj[v].push_back(u);
}
if(mp.count(make_pair(all[i].first+1,all[i].second))!=0){
long long u=ds2.root(i);
long long v=ds2.root(mp[make_pair(all[i].first+1,all[i].second)]);
adja[u].push_back(v);
adja[v].push_back(u);
}
}
for(long long i=0;i<n;i++){
if(vis[i]==0){
dfs(i);
}
}
for(long long i=0;i<n;i++){
vis[i]=0;
swap(ds1.sz[i],ds2.sz[i]);
swap(adj[i],adja[i]);
}
for(long long i=0;i<n;i++){
if(vis[i]==0){
dfs(i);
}
}
mainres%=mod;
return mainres;
}
int DistanceSum(int N,int *X,int *Y){
n=N;
for(long long i=0;i<n;i++){
all.push_back(make_pair(X[i],Y[i]));
}
return solve2();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
600 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
604 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
7 ms |
4560 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
8 ms |
4564 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
