#include <bits/stdc++.h>
using namespace std;
typedef int INT;
#define pb push_back
#define int long long
#define fst first
#define snd second
#define FOR(i,l,r) for(int i = (l); i < (r); i++)
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> ii;
typedef vector<ii> vii;
struct edge{
int v, i;
};
int N;
vii points;
vvi adj;
map<ii, int> idx;
vvi rowgr, colgr;
vii ce, re;
vector<vector<edge>> rg, cg;
vi rowsz, colsz;
vi row, col;
vi vis;
void flood(int u, int c, bool co){
vis[u] = 1;
if(co) col[u] = c, colsz[c] ++;
else row[u] = c, rowsz[c] ++;
for(int i = co; i < 4; i+= 2) if(adj[u][i] != -1 and !vis[adj[u][i]]) flood(adj[u][i], c, co);
for(int i = 1-co; i < 4; i+= 2) if(adj[u][i] != -1 and vis[adj[u][i]]) {
int v = adj[u][i];
if(v == -1) continue;
if(co) colgr[c].pb(col[v]), colgr[col[v]].pb(c);
else rowgr[c].pb(row[v]), rowgr[row[v]].pb(c);
}
}
int dp[200000][2];
int dfs(int e, int u, int p, bool col){
int &res = dp[e][col];
if(res != 0) return res;
res = col ? colsz[u] : rowsz[u];
for(edge E : (col ? cg[u] : rg[u]) ) if(E.v != p) res += dfs(E.i, E.v, u, col);
return res;
}
int dfs(int u, int p, int col){
//cout << u << " " << p << " " << col << endl;
if(col) {
int e = lower_bound(ce.begin(), ce.end(), make_pair(p, u))-ce.begin();
//cout << (ce[e] == make_pair(u,p)) << endl;
return dfs(e, u, p, col);
} else {
int e = lower_bound(re.begin(),re.end(), make_pair(p,u)) -re.begin();
//cout << (re[e] == make_pair(u,p)) << endl;
return dfs(e,u,p,col);
}
}
int gettot(int u, int tot){
//cout << u << " " << tot << endl;
int res = tot;
vis[u] = 1;
FOR(i, 0, 4){
int v = adj[u][i];
if(v == -1 || vis[v]) continue;
if(i % 2 == 0) { res += gettot(v, tot - 2*dfs(col[v], col[u], 1) + N); }
else res += gettot(v, tot - 2*dfs(row[v], row[u], 0) + N);
}
return res;
}
int bfs(int u){
vis.assign(N, 0);
int total = 0;
queue<ii> q;
q.push({u, 0});
vis[u] = 1;
while(!q.empty()){
ii p = q.front(); q.pop();
total += p.snd;
for(int v : adj[p.fst])if(v !=-1 and !vis[v]){
q.push({v,p.snd+1});
vis[v] = 1;
}
}
vis.assign(N, 0);
return total;
}
INT DistanceSum(INT n, INT *X, INT *Y) {
FOR(i,0,200000) FOR(j,0,2) dp[i][j] = 0;
N = n;
adj.assign(N, vi(4, -1));
FOR(i, 0, N) {points.pb({X[i], Y[i]}); idx[{X[i], Y[i]}] = i+1;}
FOR(i, 0, N){
int x = X[i], y = Y[i];
int neigh;
if(neigh = idx[{x+1, y}]) adj[i][0] = neigh-1;
if(neigh = idx[{x, y-1}]) adj[i][1] = neigh-1;
if(neigh = idx[{x-1, y}]) adj[i][2] = neigh-1;
if(neigh = idx[{x, y+1}]) adj[i][3] = neigh-1;
}
idx.clear();
int k = 0;
row.assign(N, -1);
col.assign(N, -1);
vis.assign(N, 0);
FOR(i, 0, N) if(!vis[i]){
rowgr.pb(vi(0));
rowsz.pb(0);
flood(i, k++,0);
}
for(auto &v : rowgr){
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
}
k = 0;
vis.assign(N, 0);
FOR(i, 0, N) if(!vis[i]){
colgr.pb(vi(0));
colsz.pb(0);
flood(i, k++,1);
}
vis.assign(N, 0);
for(auto &v : colgr){
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
}
rg.resize(rowgr.size());
cg.resize(colgr.size());
int i = 0;
FOR(u, 0, rowgr.size()){
FOR(v, 0, rowgr[u].size()){
rg[u].pb({rowgr[u][v], i++});
re.pb({u, rowgr[u][v]});
}
}
i = 0;
FOR(u, 0, colgr.size()){
FOR(v, 0, colgr[u].size()){
cg[u].pb({colgr[u][v], i++});
ce.pb({u, colgr[u][v]});
}
}
/*
cout<<i<<endl;
for(auto &v : adj) {
for(int k : v) cout << k << " ";
cout<<endl;
}
for(auto &v : colgr) {
for(int k : v) cout << k << " ";
cout<<endl;
}
cout<<endl;
for(auto &v : rowgr) {
for(int k : v) cout << k << " ";
cout<<endl;
}
for(int k : col) cout << k << " ";
cout<<endl;
for(int k : row) cout << k << " ";
cout<<endl;
cout << dfs(1, 0, 0) << endl;
cout << bfs(4) <<endl;
cout << "bfs " + to_string(dfs(3,4,1)) <<endl;
*/
return (gettot(0, bfs(0))/2) % 1000000000;
}
/*-1 -1 -1 1
3 0 -1 -1
4 -1 -1 -1
7 -1 1 -1
8 -1 2 5
9 4 -1 6
-1 5 -1 7
10 6 3 -1
-1 -1 4 9
-1 8 5 -1
-1 -1 7 -1
2
3
0 3
1 2 4 5
3
3
1
0 4
3
2 4
1 3
0 0 1 2 3 3 3 3 4 4 5
0 1 2 1 2 3 4 1 2 3 1
10
45
0 45
1 36
3 29
7 24
10 33
5 3
6 23
5 24
9 31
8 36
4 29
2 38
1 3
3 4
4 3
3 2
2 0
*/
Compilation message
city.cpp: In function 'INT DistanceSum(INT, INT*, INT*)':
city.cpp:109:12: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
if(neigh = idx[{x+1, y}]) adj[i][0] = neigh-1;
city.cpp:110:12: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
if(neigh = idx[{x, y-1}]) adj[i][1] = neigh-1;
city.cpp:111:12: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
if(neigh = idx[{x-1, y}]) adj[i][2] = neigh-1;
city.cpp:112:12: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
if(neigh = idx[{x, y+1}]) adj[i][3] = neigh-1;
city.cpp:10:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define FOR(i,l,r) for(int i = (l); i < (r); i++)
^
city.cpp:148:2: note: in expansion of macro 'FOR'
FOR(u, 0, rowgr.size()){
^~~
city.cpp:10:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define FOR(i,l,r) for(int i = (l); i < (r); i++)
^
city.cpp:149:3: note: in expansion of macro 'FOR'
FOR(v, 0, rowgr[u].size()){
^~~
city.cpp:10:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define FOR(i,l,r) for(int i = (l); i < (r); i++)
^
city.cpp:156:2: note: in expansion of macro 'FOR'
FOR(u, 0, colgr.size()){
^~~
city.cpp:10:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define FOR(i,l,r) for(int i = (l); i < (r); i++)
^
city.cpp:157:3: note: in expansion of macro 'FOR'
FOR(v, 0, colgr[u].size()){
^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
3448 KB |
Output is correct |
| 2 |
Correct |
5 ms |
3604 KB |
Output is correct |
| 3 |
Correct |
4 ms |
3604 KB |
Output is correct |
| 4 |
Correct |
5 ms |
3724 KB |
Output is correct |
| 5 |
Correct |
5 ms |
3724 KB |
Output is correct |
| 6 |
Correct |
5 ms |
3724 KB |
Output is correct |
| 7 |
Correct |
5 ms |
3724 KB |
Output is correct |
| 8 |
Correct |
5 ms |
3724 KB |
Output is correct |
| 9 |
Correct |
4 ms |
3724 KB |
Output is correct |
| 10 |
Correct |
5 ms |
3724 KB |
Output is correct |
| 11 |
Correct |
4 ms |
3724 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
4000 KB |
Output is correct |
| 2 |
Correct |
7 ms |
4000 KB |
Output is correct |
| 3 |
Correct |
7 ms |
4072 KB |
Output is correct |
| 4 |
Correct |
7 ms |
4072 KB |
Output is correct |
| 5 |
Correct |
11 ms |
4204 KB |
Output is correct |
| 6 |
Correct |
8 ms |
4204 KB |
Output is correct |
| 7 |
Correct |
9 ms |
4204 KB |
Output is correct |
| 8 |
Correct |
8 ms |
4204 KB |
Output is correct |
| 9 |
Correct |
11 ms |
4204 KB |
Output is correct |
| 10 |
Correct |
7 ms |
4204 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
54 ms |
8280 KB |
Output is correct |
| 2 |
Correct |
52 ms |
8420 KB |
Output is correct |
| 3 |
Correct |
170 ms |
14944 KB |
Output is correct |
| 4 |
Correct |
281 ms |
14956 KB |
Output is correct |
| 5 |
Correct |
455 ms |
26900 KB |
Output is correct |
| 6 |
Correct |
497 ms |
26900 KB |
Output is correct |
| 7 |
Correct |
490 ms |
26900 KB |
Output is correct |
| 8 |
Correct |
494 ms |
27100 KB |
Output is correct |
| 9 |
Correct |
478 ms |
27100 KB |
Output is correct |
| 10 |
Correct |
555 ms |
28724 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
87 ms |
28724 KB |
Output is correct |
| 2 |
Correct |
70 ms |
28724 KB |
Output is correct |
| 3 |
Correct |
275 ms |
28724 KB |
Output is correct |
| 4 |
Correct |
237 ms |
28724 KB |
Output is correct |
| 5 |
Correct |
661 ms |
31168 KB |
Output is correct |
| 6 |
Correct |
548 ms |
31168 KB |
Output is correct |
| 7 |
Correct |
658 ms |
33192 KB |
Output is correct |
| 8 |
Correct |
560 ms |
33192 KB |
Output is correct |
| 9 |
Correct |
561 ms |
33192 KB |
Output is correct |
| 10 |
Correct |
536 ms |
33192 KB |
Output is correct |
