#include <bits/stdc++.h>
#include "city.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 1e5 + 10;
const int MOD = 2e9;
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define fi first
#define se second
#define all(v) (v).begin(), (v).end()
#define fillchar(a, s) memset((a), (s), sizeof(a))
int add (int x, int y) {
int r = (ll(x) + y) % MOD;
if (r < 0) {
r += MOD;
}
return r;
}
void addeq (int &x, int y) {
x = add(x, y);
}
int mult (int x, int y) {
return ll(x) * y % MOD;
}
int N, V;
int X[MAXN], Y[MAXN];
int bel[MAXN];
map<pii, int> mp;
set<pii> edges;
int W[MAXN]; //weight of it
vector<int> ys[MAXN];
vector<int> adj[MAXN];
//let's go now
int sub[MAXN];
int sumd[MAXN];
void dfs1 (int x, int p, int d) {
addeq(sumd[0], mult(d, W[x]));
sub[x] = W[x];
for (int y : adj[x]) {
if (y != p) {
dfs1(y, x, d + 1);
sub[x] += sub[y];
}
}
}
void dfs2 (int x, int p) {
for (int y : adj[x]) {
if (y != p) {
sumd[y] = add(sumd[x], N - 2 * sub[y]);
dfs2(y, x);
}
}
}
int go() {
#warning reset
mp.clear();
edges.clear();
for (int i = 0; i < MAXN; i++) {
ys[i].clear();
adj[i].clear();
W[i] = 0;
sub[i] = 0;
sumd[i] = 0;
}
V = 0;
for (int i = 0; i < N; i++) {
ys[X[i]].push_back(Y[i]);
mp[{X[i], Y[i]}] = i;
}
for (int i = 0; i < MAXN; i++) {
sort(all(ys[i]));
//components
for (int j = 0; j < ys[i].size(); ) {
int k = j;
int comp = V++;
for (; k < ys[i].size() && ys[i][k] - ys[i][j] == k - j; k++) {
W[comp]++;
bel[mp.at({i, ys[i][k]})] = comp;
if (i) {
//connect with previous row
auto it = mp.find({i - 1, ys[i][k]});
if (it != mp.end()) {
edges.emplace(bel[it->se], comp);
}
}
}
j = k;
}
}
//make actual graph
for (pii p : edges) {
adj[p.fi].push_back(p.se);
adj[p.se].push_back(p.fi);
}
dfs1(0, -1, 0);
dfs2(0, -1);
int ans = 0;
for (int i = 0; i < V; i++) {
addeq(ans, mult(W[i], sumd[i]));
}
return ans;
}
int DistanceSum (int nn, int *xx, int *yy) {
N = nn;
int xmin = *min_element(xx, xx + N), ymin = *min_element(yy, yy + N);
for (int i = 0; i < N; i++) {
X[i] = xx[i] - xmin;
Y[i] = yy[i] - ymin;
}
//find w(y) * d(x, y)
int ansx = go();
for (int i = 0; i < N; i++) {
swap(X[i], Y[i]);
}
int ansy = go();
return add(ansx, ansy) / 2;
}
Compilation message
city.cpp:2:10: fatal error: city.h: No such file or directory
#include "city.h"
^~~~~~~~
compilation terminated.
