#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; }

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);
            ^