//#include "grader.cpp"
#include <set>
#include <map>
#include <cmath>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
const int mod = 1e9;
const int MAXN = 1e5 + 5;
struct Point
{
long long x, y;
Point(){}
Point(long long x, long long y)
{
this->x = x;
this->y = y;
}
};
long long getDist(Point A, Point B)
{
return abs(A.x-B.x) + abs(A.y-B.y);
}
bool operator <(Point A, Point B)
{
if(A.x!=B.x) return A.x<B.x;
return A.y<B.y;
}
long long evalVector(vector <Point> v)
{
long long answer = 0;
sort(v.begin(), v.end(),
[&](Point A, Point B)
{
if(A.x!=B.x) return A.x<B.x;
return A.y<B.y;
});
long long sum = 0;
for(int i = 0;i<v.size();i++)
{
answer = (answer + (i*1LL*v[i].x - sum))%mod;
sum += v[i].x;
}
sort(v.begin(), v.end(),
[&](Point A, Point B)
{
if(A.y!=B.y) return A.y<B.y;
return A.x<B.x;
});
sum = 0;
for(int i = 0;i<v.size();i++)
{
answer = (answer + (i*1LL*v[i].y - sum))%mod;
sum += v[i].y;
}
return answer;
}
Point ind2Point[MAXN];
map <Point, int> point2Ind;
int cntOver[MAXN], depth[MAXN], treeSize[MAXN];
vector <int> graph[MAXN];
bool used[MAXN];
set <pair <int, int>> bridges;
long long answer = 0;
long long coef[MAXN];
void DFSInit(int x, int last, int level, int all)
{
used[x] = true;
depth[x] = level;
cntOver[x] = 0;
treeSize[x] = 1;
for(int y: graph[x])
{
//if(x==9) cout << " ----> " << y << '\n';
if(y==last) continue;
if(used[y]==true)
{
if(depth[y]<depth[x]) cntOver[x]++;
else cntOver[x]--;
continue;
}
DFSInit(y, x, level+1, all);
cntOver[x] += cntOver[y];
treeSize[x] += treeSize[y];
}
//cout << x << " " << last << " -> " << treeSize[x] << " " << depth[x] << " || " << cntOver[x] << '\n';
if(last!=-1 && cntOver[x]==0)
{
bridges.insert({x, last});
bridges.insert({last, x});
answer += treeSize[x]*1LL*(all-treeSize[x]);
answer %= mod;
//cout << x << " <=> " << last << " || " << treeSize[x] << " * " << all - treeSize[x] << '\n';
}
}
void DFSNoBridge(int x, vector <int> &v)
{
used[x] = true;
v.push_back(x);
for(int y: graph[x])
{
if(used[y]==true) continue;
if(bridges.count({x, y})==true) continue;
DFSNoBridge(y, v);
}
}
void init(vector <Point> &v)
{
set <Point> s;
for(int i = 0;i<v.size();i++)
{
s.insert(v[i]);
ind2Point[i] = v[i];
point2Ind[ v[i] ] = i;
}
for(int i = 0;i<v.size();i++)
{
for(pair <int, int> jump: vector <pair <int, int>>{{-1, 0}, {1, 0}, {0, -1}, {0, 1}})
{
Point a = v[i];
Point b = Point(v[i].x+jump.first, v[i].y+jump.second);
if(s.count(b)==false) continue;
graph[ point2Ind[a] ].push_back(point2Ind[b]);
}
}
//cout << "all bridges:" << '\n';
DFSInit(0, -1, 1, v.size());
}
void doComponent(vector <int> &v)
{
//if(v.size()>1) cout << "KKK" << '\n';
for(int i: v)
{
for(int j: v)
{
if(i==j) continue;
answer = (answer + coef[i]*getDist(ind2Point[i], ind2Point[j]))%mod;
//cout << i << " -> " << coef[i] << " * " << getDist(ind2Point[i], ind2Point[j]) << '\n';
}
}
for(int i: v)
{
for(int j: v)
{
if(i==j) continue;
if(j>i) continue;
answer = (answer + ((coef[i]*coef[j])%mod)*getDist(ind2Point[i], ind2Point[j]))%mod;
//cout << i << " -> " << coef[i] << " * " << getDist(ind2Point[i], ind2Point[j]) << '\n';
}
}
}
void evalComponents(int n)
{
memset(used, false, sizeof(used));
for(int x = 0;x<n;x++)
{
if(used[x]==false)
{
vector <int> inds;
DFSNoBridge(x, inds);
vector <Point> v;
for(int i: inds) v.push_back(ind2Point[i]);
answer += evalVector(v);
doComponent(inds);
}
}
}
void calcCoefs(int n)
{
for(pair <int, int> e: bridges)
{
if(depth[e.first]>depth[e.second])
{
coef[e.first] += n - treeSize[e.first];
}
else
{
coef[e.first] += treeSize[e.second];
}
}
for(int i = 0;i<n;i++) coef[i] %= mod;
//for(int i = 0;i<n;i++) cout << i << " -> " << coef[i] << '\n';
}
int DistanceSum(int N, int *X, int *Y)
{
vector <Point> v;
for(int i = 0;i<N;i++) v.push_back(Point(X[i], Y[i]));
init(v);
calcCoefs(N);
evalComponents(N);
return answer%mod;
}
Compilation message
city.cpp: In function 'long long int evalVector(std::vector<Point>)':
city.cpp:52:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Point>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
52 | for(int i = 0;i<v.size();i++)
| ~^~~~~~~~~
city.cpp:66:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Point>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
66 | for(int i = 0;i<v.size();i++)
| ~^~~~~~~~~
city.cpp: In function 'void init(std::vector<Point>&)':
city.cpp:143:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Point>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
143 | for(int i = 0;i<v.size();i++)
| ~^~~~~~~~~
city.cpp:151:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Point>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
151 | for(int i = 0;i<v.size();i++)
| ~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2816 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2816 KB |
Output is correct |
| 3 |
Correct |
2 ms |
2816 KB |
Output is correct |
| 4 |
Correct |
2 ms |
2816 KB |
Output is correct |
| 5 |
Incorrect |
3 ms |
2816 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
3072 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1044 ms |
9200 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
74 ms |
8304 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
