#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <queue>
#include <map>
typedef long long llong;
const int MAXN = 100000 + 10;
const int MOD = 1'000'000'000;
int n;
llong ans;
int cnt[MAXN];
int degree[MAXN];
bool isActive[MAXN];
int x[MAXN], y[MAXN];
std::pair <int,int> delta[] = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};
std::map <std::pair <int,int>, int> map;
std::vector <int> g[MAXN];
std::queue <int> q;
int cntActive;
int DistanceSum(int N, int *X, int *Y)
{
n = N;
cntActive = n;
for (int i = 1 ; i <= n ; ++i)
{
x[i] = X[i - 1];
y[i] = Y[i - 1];
map[{x[i], y[i]}] = i;
}
for (int i = 1 ; i <= n ; ++i)
{
for (const auto &[dx, dy] : delta)
{
if (map.count({x[i] + dx, y[i] + dy}))
{
g[i].push_back(map[{x[i] + dx, y[i] + dy}]);
degree[i]++;
}
}
}
std::fill(isActive + 1, isActive + 1 + n, true);
std::fill(cnt + 1, cnt + 1 + n, 1);
for (int i = 1 ; i <= n ; ++i)
{
if (degree[i] == 1)
{
q.push(i);
}
}
while (!q.empty() && cntActive > 1)
{
int top = q.front();
ans += 1LL * cnt[top] * (n - cnt[top]);
ans %= MOD;
isActive[top] = false;
cntActive--;
q.pop();
for (const int &u : g[top])
{
if (!isActive[u])
{
continue;
}
degree[u]--;
cnt[u] += cnt[top];
if (degree[u] == 1)
{
isActive[u] = false;
q.push(u);
}
}
}
ans %= MOD;
for (int i = 1 ; i <= n ; ++i)
{
for (int j = i + 1 ; j <= n ; ++j)
{
if (isActive[i] && isActive[j])
{
ans += ((1LL * cnt[i] * cnt[j]) % MOD) * (abs(x[i] - x[j]) + abs(y[i] - y[j]));
ans %= MOD;
}
}
}
return ans;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
2644 KB |
Output is correct |
2 |
Correct |
1 ms |
2644 KB |
Output is correct |
3 |
Correct |
1 ms |
2644 KB |
Output is correct |
4 |
Incorrect |
1 ms |
2644 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
3 ms |
2772 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
835 ms |
5076 KB |
Output is correct |
2 |
Correct |
837 ms |
5072 KB |
Output is correct |
3 |
Execution timed out |
1077 ms |
8524 KB |
Time limit exceeded |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
646 ms |
5088 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |