#include<bits/stdc++.h>
using namespace std;
#define maxn 100005
#define mod 1000000007LL
int head[maxn];
long long now, ans;
long long sum[maxn], val[maxn];
bool vis[maxn];
vector<int> from[maxn];
map<pair<int,int>, int> p;
void dfs(int x,int h) {
int i;
vis[x] = 1; now = (now + val[x]*h)%mod;
for(i=0;i<from[x].size();i++) {
if(!vis[from[x][i]]) {
dfs(from[x][i],h+1);
sum[x] = (sum[x] + sum[from[x][i]])%mod;
}
}
sum[x] = (sum[x] + val[x])%mod;
}
void dfs2(int x) {
int i;
vis[x] = 1;
ans = (ans + now*val[x]);
for(i=0;i<from[x].size();i++) {
if(!vis[from[x][i]]) {
now = (now + sum[x] - sum[from[x][i]] - sum[from[x][i]] + mod)%mod;
dfs2(from[x][i]);
now = (now - sum[x] + sum[from[x][i]] + sum[from[x][i]] + mod)%mod;
}
}
}
int findhead(int x) {
if(head[x]==x) return x;
return head[x] = findhead(head[x]);
}
void solve(int N, int *X, int *Y,int type) {
int i,x;
pair<int,int> t;
map<pair<int,int>, int>::iterator it;
p.clear();
memset(sum,0,sizeof(sum)); memset(val,0,sizeof(val));
for(i=0;i<N;i++) head[i] = i, from[i].clear();
for(i=0;i<N;i++) {
if(type==0) p[{X[i],Y[i]}] = i;
else p[{Y[i],X[i]}] = i;
}
for(it=p.begin();it!=p.end();++it) {
t = it->first;
if(p.find({t.first,t.second+1})!=p.end()) head[findhead(p[t])] = findhead(p[{t.first,t.second+1}]);
}
for(i=0;i<N;i++) val[findhead(i)]++;
for(it=p.begin();it!=p.end();++it) {
t = it->first;
if(p.find({t.first+1,t.second})!=p.end()) from[findhead(p[t])].push_back(findhead(p[{t.first+1,t.second}]));
if(p.find({t.first-1,t.second})!=p.end()) from[findhead(p[t])].push_back(findhead(p[{t.first-1,t.second}]));
}
for(i=0;i<N;i++) if(val[i]) x = i;
memset(vis,0,sizeof(vis));
dfs(x,0);
memset(vis,0,sizeof(vis));
dfs2(x);
}
int DistanceSum(int N,int* X,int* Y) {
ans = 0;
solve(N,X,Y,0);
solve(N,X,Y,1);
return ans/2;
}
Compilation message
city.cpp: In function 'void dfs(int, int)':
city.cpp:14:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0;i<from[x].size();i++) {
^
city.cpp: In function 'void dfs2(int)':
city.cpp:26:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0;i<from[x].size();i++) {
^
city.cpp: In function 'void solve(int, int*, int*, int)':
city.cpp:63:12: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]
dfs2(x);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
6556 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
6688 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
56 ms |
8416 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
53 ms |
8416 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
