This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef complex<ld> point;
void debug_out(){cerr << endl;}
template<typename H, typename... T>
void debug_out(H h, T... t){
cerr << h << ' ';
debug_out(t...);
}
#define debug(...) cerr << "(" << #__VA_ARGS__ << "): ", debug_out(__VA_ARGS__)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)
const int maxn = 1e5 + 10;
const int inf = 2147483647;
const int mod = 1e9;
int add(int x, int y){
int res = x + y;
if (res >= mod) return res - mod;
if (res < 0) return res + mod;
return res;
}
int n, ans, x[maxn], y[maxn], sz[maxn];
vector<int> valx[maxn], valy[maxn];
vector<int> g[maxn];
void dfs(int v, int p = -1){
//debug(v);
for (auto u: g[v]){
if (u != p){
dfs(u, v);
sz[v] += sz[u];
}
}
ans = add(ans, 1ll * sz[v] * (n-sz[v]) % mod);
//debug(v, sz[v]);
}
int DistanceSum(int N, int *X, int *Y) {
n = N;
int mnx = inf, mny = inf, mx = 0, my = 0;
for (int i = 1; i <= n; i++){
x[i] = X[i-1];
y[i] = Y[i-1];
mnx = min(mnx, x[i]);
mny = min(mny, y[i]);
}
mnx--;
mny--;
for (int i = 1; i <= n; i++){
x[i] -= mnx;
y[i] -= mny;
valx[x[i]].push_back(y[i]);
valy[y[i]].push_back(x[i]);
mx = max(mx, x[i]);
my = max(my, y[i]);
cerr << x[i] << ' ' << y[i] << endl;
}
int cnt = 0;
vector<pair<int,pii>> ver;
for (int i = 1; i <= mx; i++){
vector<pair<int,pii>> tmp;
sort(all(valx[i]));
int l = valx[i][0];
for (int j = 1; j < valx[i].size(); j++){
if (valx[i][j] != valx[i][j-1] + 1){
cnt++;
tmp.push_back({cnt, {l, valx[i][j-1]}});
//debug(i, cnt, l, valx[i][j-1]);
sz[cnt] = valx[i][j-1] - l + 1;
l = valx[i][j];
}
}
cnt++;
tmp.push_back({cnt, {l, valx[i].back()}});
//debug(i, cnt, l, valx[i].back());
sz[cnt] = valx[i].back() - l + 1;
int ptr = 0;
for (auto [x, y]: tmp){
while(ptr < ver.size() && ver[ptr].S.S <= y.S){
if (y.F <= ver[ptr].S.S){
// debug(ver[ptr].F, x);
g[ver[ptr].F].push_back(x);
g[x].push_back(ver[ptr].F);
}
ptr++;
}
if (ptr != ver.size() && ver[ptr].S.F <= y.S){
// debug(ver[ptr].F, x);
g[ver[ptr].F].push_back(x);
g[x].push_back(ver[ptr].F);
}
}
ver = tmp;
}
dfs(1);
for (int i = 1; i <= cnt; i++){
g[i].clear();
}
memset(sz, 0, sizeof sz);
ver.clear();
cnt = 0;
for (int i = 1; i <= my; i++){
vector<pair<int,pii>> tmp;
sort(all(valy[i]));
int l = valy[i][0];
for (int j = 1; j < valy[i].size(); j++){
if (valy[i][j] != valy[i][j-1] + 1){
cnt++;
// debug(i, cnt, l, valy[i][j-1]);
tmp.push_back({cnt, {l, valy[i][j-1]}});
sz[cnt] = valy[i][j-1] - l + 1;
l = valy[i][j];
}
}
cnt++;
tmp.push_back({cnt, {l, valy[i].back()}});
//debug(i, cnt, l, valy[i].back());
sz[cnt] = valy[i].back() - l + 1;
int ptr = 0;
for (auto [x, y]: tmp){
while(ptr < ver.size() && ver[ptr].S.S <= y.S){
if (y.F <= ver[ptr].S.S){
// debug(ver[ptr].F, x);
g[ver[ptr].F].push_back(x);
g[x].push_back(ver[ptr].F);
}
ptr++;
}
if (ptr != ver.size() && ver[ptr].S.F <= y.S){
// debug(ver[ptr].F, x);
g[ver[ptr].F].push_back(x);
g[x].push_back(ver[ptr].F);
}
}
ver = tmp;
}
dfs(1);
return ans;
}
Compilation message (stderr)
city.cpp: In function 'int DistanceSum(int, int*, int*)':
city.cpp:79:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
79 | for (int j = 1; j < valx[i].size(); j++){
| ~~^~~~~~~~~~~~~~~~
city.cpp:94:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
94 | while(ptr < ver.size() && ver[ptr].S.S <= y.S){
| ~~~~^~~~~~~~~~~~
city.cpp:102:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
102 | if (ptr != ver.size() && ver[ptr].S.F <= y.S){
| ~~~~^~~~~~~~~~~~~
city.cpp:122:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
122 | for (int j = 1; j < valy[i].size(); j++){
| ~~^~~~~~~~~~~~~~~~
city.cpp:137:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
137 | while(ptr < ver.size() && ver[ptr].S.S <= y.S){
| ~~~~^~~~~~~~~~~~
city.cpp:145:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
145 | if (ptr != ver.size() && ver[ptr].S.F <= y.S){
| ~~~~^~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |