#include <map>
#include <vector>
#include <algorithm>
#include <iostream>
#include <stack>
using ll = long long;
int const nmax = 100000;
int const modulo = 1000000000;
int const iplus[4] = {0, 0, 1, -1};
int const jplus[4] = {1, -1, 0, 0};
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))
struct Point{
int x;
int y;
bool operator < (Point const &a) const{
if(x != a.x)
return x < a.x;
else
return y < a.y;
}
};
void normalize(std::vector<Point> &v){
int xmin = v[0].x, ymin = v[0].y;
for(int i = 1; i < v.size(); i++){
xmin = MIN(xmin, v[i].x);
ymin = MIN(ymin, v[i].y);
}
for(int i = 0; i < v.size(); i++){
v[i].x -= xmin;
v[i].y -= ymin;
}
}
std::map<std::pair<int,int>, int> cell;
namespace Dsu{
int mult[1 + nmax];
int sz[1 + nmax];
struct Update{
int x;
int y;
int szx;
int szy;
};
std::stack<Update> st;
void initialize(int n){
for(int i = 0; i <= n; i++) {
mult[i] = i;
sz[i] = 1;
}
while(0 < st.size())
st.pop();
}
int jump(int a){
if(mult[a] != a)
return jump(mult[a]);
else
return a;
}
void unite(int gala, int galb){
gala = jump(gala);
galb = jump(galb);
if(sz[galb] < sz[gala])
std::swap(gala, galb);
if(gala != galb){
st.push({gala, galb, sz[gala], sz[galb]});
mult[gala] = galb;
sz[galb] += sz[gala];
}
}
void reset(){
while(0 < st.size()){
Update e = st.top();
mult[e.x] = e.x;
mult[e.y] = e.y;
sz[e.x] = e.szx;
sz[e.y] = e.szy;
st.pop();
}
}
}
std::vector<Point> line[1 + nmax];
std::map<Point, int> id;
std::map<int, int> leftextrem;
int dp[1 + nmax], dp2[1 + nmax];
int cost[1 + nmax], seen[1 + nmax];
std::vector<int> g[1 + nmax];
void dfs(int node, int parent){
seen[node] = 1;
for(int h = 0; h < g[node].size(); h++){
int to = g[node][h];
if(to != parent) {
dfs(to, node);
cost[node] += cost[to];
}
}
}
int dfs2(int node, int parent, int total){
int result = 1LL * (total - cost[node]) * cost[node] % modulo;
for(int h = 0; h < g[node].size(); h++){
int to = g[node][h];
if(to != parent){
result += dfs2(to, node, total);
if(modulo <= result)
result -= modulo;
}
}
return result;
}
int solveline(int x){
Dsu::reset();
std::vector<int> nodes;
for(int i = 0; i < line[x].size(); i++){
Point curr = line[x][i];
g[id[curr]].clear();
if(0 == cell[{x, curr.y - 1}]) {
cost[id[curr]] = dp[id[curr]];
nodes.push_back(id[curr]);
}
}
for(int i = 0; i < line[x + 1].size(); i++){
Point curr = line[x + 1][i];
g[id[curr]].clear();
if(0 == cell[{x + 1, curr.y - 1}]) {
cost[id[curr]] = dp2[id[curr]];
nodes.push_back(id[curr]);
}
}
int result = 0;
for(int i = 0; i < line[x].size(); i++){
Point curr = line[x][i];
if(0 < cell[{x + 1, curr.y}] && (0 == cell[{x, curr.y - 1}] || 0 == cell[{x + 1, curr.y - 1}])) {
int gala = leftextrem[cell[{x + 1, curr.y}]], galb = leftextrem[id[curr]];
g[galb].push_back(gala);
g[gala].push_back(galb);
//std::cout << "edge " << gala << " " << galb << '\n';
}
}
for(int i = 0; i < nodes.size(); i++){
int node = nodes[i];
seen[node] = 0;
}
for(int i = 0; i < nodes.size(); i++){
int node = nodes[i];
if(seen[node] == 0){
dfs(node, -1);
//std::cout << node << " " << cost[node] << '\n';
result += dfs2(node, -1, cost[node]);
if(modulo <= result)
result -= modulo;
}
}
// std::cout << ":" << x << " " << result << '\n' << '\n';
return result ;
}
int solve(std::vector<Point> v){
int n = v.size();
std::sort(v.begin(), v.end());
for(int i = 0; i < n; i++)
dp[i] = dp2[i] = 0;
leftextrem.clear();
id.clear();
cell.clear();
for(int i = 0; i < n; i++)
line[i].clear();
for(int i = 0; i < n; i++) {
line[v[i].x].push_back(v[i]);
id[v[i]] = i + 1;
}
Dsu::initialize(n);
for(int i = 0; i < n; i++){
for(int j = 0; j < line[i].size(); j++){
Point curr = line[i][j];
if(0 < cell[{curr.x, curr.y - 1}])
leftextrem[id[curr]] = leftextrem[id[{curr.x, curr.y - 1}]];
else
leftextrem[id[curr]] = id[curr];
cell[{curr.x, curr.y}] = id[curr];
if(0 < cell[{curr.x, curr.y - 1}]) {
Dsu::unite(id[curr], cell[{curr.x, curr.y - 1}]);
} if(0 < cell[{curr.x - 1, curr.y}]) {
Dsu::unite(id[curr], cell[{curr.x - 1, curr.y}]);
}
}
for(int j = 0; j < line[i].size(); j++){
Point curr = line[i][j];
dp[id[curr]] = Dsu::sz[Dsu::jump(id[curr])];
}
}
Dsu::reset();
for(int i = n - 1; 0 <= i; i--){
for(int j = 0; j < line[i].size(); j++){
Point curr = line[i][j];
cell[{curr.x, curr.y}] = id[curr];
if(0 < cell[{curr.x, curr.y - 1}])
Dsu::unite(id[curr], cell[{curr.x, curr.y - 1}]);
if(0 < cell[{curr.x + 1, curr.y}])
Dsu::unite(id[curr], cell[{curr.x + 1, curr.y}]);
}
for(int j = 0; j < line[i].size(); j++){
Point curr = line[i][j];
dp2[id[curr]] = Dsu::sz[Dsu::jump(id[curr])];
}
}
int result = 0;
for(int i = 0; i < n; i++) {
result += solveline(i);
if(modulo <= result)
result -= modulo;
}
/*
std::cout << '\n';
for(int i = 0; i < n; i++)
std::cout << v[i].x << " " << v[i].y << " " << dp[id[v[i]]] << " " << dp2[id[v[i]]] << '\n';
*/
return result;
}
int DistanceSum(int N, int *X, int *Y) {
std::vector<Point> v(N);
for(int i = 0; i < N; i++) {
v[i].x = X[i];
v[i].y = Y[i];
}
normalize(v);
int result = 0;
result += solve(v);
//return result;
for(int i = 0; i < N; i++)
std::swap(v[i].x, v[i].y);
result = (result + solve(v)) % modulo;
return result;
}
Compilation message
city.cpp: In function 'void normalize(std::vector<Point>&)':
city.cpp:31:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 1; i < v.size(); i++){
~~^~~~~~~~~~
city.cpp:35:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < v.size(); i++){
~~^~~~~~~~~~
city.cpp: In function 'void dfs(int, int)':
city.cpp:104:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int h = 0; h < g[node].size(); h++){
~~^~~~~~~~~~~~~~~~
city.cpp: In function 'int dfs2(int, int, int)':
city.cpp:116:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int h = 0; h < g[node].size(); h++){
~~^~~~~~~~~~~~~~~~
city.cpp: In function 'int solveline(int)':
city.cpp:131:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < line[x].size(); i++){
~~^~~~~~~~~~~~~~~~
city.cpp:140:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < line[x + 1].size(); i++){
~~^~~~~~~~~~~~~~~~~~~~
city.cpp:150:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < line[x].size(); i++){
~~^~~~~~~~~~~~~~~~
city.cpp:160:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < nodes.size(); i++){
~~^~~~~~~~~~~~~~
city.cpp:165:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < nodes.size(); i++){
~~^~~~~~~~~~~~~~
city.cpp: In function 'int solve(std::vector<Point>)':
city.cpp:200:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0; j < line[i].size(); j++){
~~^~~~~~~~~~~~~~~~
city.cpp:215:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0; j < line[i].size(); j++){
~~^~~~~~~~~~~~~~~~
city.cpp:223:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0; j < line[i].size(); j++){
~~^~~~~~~~~~~~~~~~
city.cpp:231:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0; j < line[i].size(); j++){
~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
5240 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
4984 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
5496 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
143 ms |
10340 KB |
Output is correct |
| 2 |
Correct |
153 ms |
10616 KB |
Output is correct |
| 3 |
Correct |
376 ms |
18032 KB |
Output is correct |
| 4 |
Correct |
376 ms |
18416 KB |
Output is correct |
| 5 |
Correct |
813 ms |
31000 KB |
Output is correct |
| 6 |
Correct |
850 ms |
32116 KB |
Output is correct |
| 7 |
Correct |
828 ms |
31976 KB |
Output is correct |
| 8 |
Correct |
797 ms |
30820 KB |
Output is correct |
| 9 |
Correct |
794 ms |
32072 KB |
Output is correct |
| 10 |
Correct |
868 ms |
36968 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
166 ms |
11812 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
