#include "grader.h"
#include <bits/stdc++.h>
namespace {
using namespace std;
const int MAXN = 1e5;
const long long MOD = 1e9;
int N, *X, *Y;
vector<int> atX[MAXN + 10], atY[MAXN + 10];
vector<pair<int,int>> G[MAXN + 10];
set<tuple<int,int,int>> st;
map<int,int> val, mp;
map<int,map<int,int>> id;
int par[MAXN + 10];
long long cc[MAXN + 10], dis[MAXN + 10], sum[MAXN + 10];
void dfs(int u, int p = -1) {
for(auto e : G[u]) {
int v, w; tie(v, w) = e;
if(v != p) dfs(v, u);
}
cc[u] = 1; dis[u] = 0;
for(auto e : G[u]) {
int v, w; tie(v, w) = e;
if(v == p) continue;
cc[u] += cc[v];
dis[u] += w*cc[v] + dis[v];
}
sum[u] = 0;
for(auto e : G[u]) {
int v, w; tie(v, w) = e;
if(v == p) continue;
sum[u] += sum[v];
sum[u] += (dis[v] + w*cc[v]) * (cc[u] - cc[v]);
}
}
long long calc(vector<int> at[MAXN + 10]) {
fill(G, G + MAXN + 1, vector<pair<int,int>>());
st.clear(); id.clear();
memset(par, -1, sizeof par);
int jj = 0;
for(int x = 1; x <= N; x++) {
for(int y : at[x]) id[x][y] = ++jj;
}
set<pair<int,int>> yay;
jj = 0;
for(int x = 1; x <= N; x++) {
int l = 0, r = 0;
while(l < (int)at[x].size()) {
r = l;
while(r+1 < (int)at[x].size() && at[x][r+1] == at[x][r]+1) {
r++;
}
++jj;
for(int i = l; i <= r; i++) {
par[id[x][at[x][i]]] = jj;
}
//cerr << "[" << val[at[x][l]] << ", " << val[at[x][r]] << "]\n";
for(int i = l; i <= r; i++) {
auto add = [&](int a, int b, int c, int d, int w) {
int u = id[a][b], v = id[c][d];
st.emplace(u, v, w);
st.emplace(v, u, w);
yay.emplace(par[u], par[v]);
yay.emplace(par[v], par[u]);
};
int y = at[x][i];
if(i < r) add(x, y, x, y+1, 0);
if(binary_search(at[x-1].begin(), at[x-1].end(), y)) {
if(!yay.count({par[id[x][y]], par[id[x-1][y]]})) {
//cerr << "yay " << val[x] << " " << val[y] << " " << val[x-1] << " " << val[y] << "\n";
add(x, y, x-1, y, 1);
} else {
//cerr << "bad " << val[x] << " " << val[y] << " " << val[x-1] << " " << val[y] << "\n";
}
}
}
l = r+1;
}
}
for(auto it : st) {
int u, v, w; tie(u, v, w) = it;
G[u].emplace_back(v, w);
}
dfs(1);
return sum[1];
}
};
int DistanceSum(int N_, int* X_, int* Y_) {
N = N_; X = X_; Y = Y_;
set<int> st;
for(int i = 0; i < N; i++) {
st.insert(X[i]);
st.insert(Y[i]);
}
int ii = 0;
for(int x : st) {
mp[x] = ++ii;
val[ii] = x;
}
for(int i = 0; i < N; i++) {
X[i] = mp[X[i]];
Y[i] = mp[Y[i]];
}
for(int i = 0; i < N; i++) {
atX[X[i]].push_back(Y[i]);
atY[Y[i]].push_back(X[i]);
}
for(int x = 1; x <= N; x++) {
sort(atX[x].begin(), atX[x].end());
}
for(int y = 1; y <= N; y++) {
sort(atY[y].begin(), atY[y].end());
}
long long res = calc(atX);
//cerr << "\n\n\n";
res += calc(atY);
return res % MOD;
}
Compilation message
city.cpp:1:10: fatal error: grader.h: No such file or directory
#include "grader.h"
^~~~~~~~~~
compilation terminated.
