# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
532271 |
2022-03-02T16:11:20 Z |
sidon |
Ideal city (IOI12_city) |
C++17 |
|
607 ms |
61744 KB |
#include <bits/stdc++.h>
using namespace std;
using i64 = int64_t;
const array<int, 2> mv[4] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
const int Z = 1e5;
int n, s[Z];
map<int, int> toS[Z];
set<int> g[Z], h[Z];
void dfs(int u, int p) {
for(const int &v : g[u]) if(v != p) {
dfs(v, u);
s[u] += toS[u][v] = s[v];
toS[v][u] = n - s[v];
}
}
i64 curSum, ans;
void cnt(int u) {
s[u] = 1;
ans += curSum;
for(const int &v : h[u]) if(!s[v]) {
curSum += i64(n - 2 * toS[u][v]);
cnt(v);
curSum -= i64(n - 2 * toS[u][v]);
}
}
int DistanceSum(int N, int *X, int *Y) {
map<int, map<int, int>> cAt;
int o[N], id[N]; n = N;
for(int i = 0; i < N; ++i)
cAt[X[i]][Y[i]] = (o[i] = i) + 1;
for(int u = 0; u < N; ++u) {
for(const auto &[dx, dy] : mv) {
int v = cAt[X[u] + dx][Y[u] + dy] - 1;
if(v >= 0) h[u].insert(v);
}
}
for(int _ = 0; _ < 2; ++_) {
if(_) {
cAt.clear();
for(int i = 0; i < N; ++i)
cAt[X[i]][Y[i]] = i + 1;
}
sort(o, o + N, [&](const int &i, const int &j) {
return Y[i] < Y[j];
});
for(const int &u : o) {
int v = cAt[X[u]][Y[u] - 1] - 1;
id[u] = v < 0 ? u : id[v];
}
fill(s, s + N, 0);
fill(g, g + N, set<int> ());
for(int u = 0; u < N; ++u) {
++s[id[u]];
for(const int &v : h[u]) if(id[u] != id[v])
g[id[u]].insert(id[v]);
}
dfs(id[0], id[0]);
for(int u = 0; u < N; ++u)
for(const int &v : h[u]) if(id[u] != id[v])
toS[u][v] = toS[id[u]][id[v]];
swap(X, Y);
}
queue<pair<int, int>> q;
bool vis[N] {1};
q.emplace(0, 0);
while(!empty(q)) {
auto [u, d] = q.front(); q.pop();
curSum += i64(d);
for(const int &v : h[u])
if(v >= 0 && !vis[v])
vis[v] = 1, q.emplace(v, d + 1);
}
fill(s, s + N, 0);
cnt(0);
return (ans >> 1) % i64(1e9);
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
14288 KB |
Output is correct |
2 |
Correct |
10 ms |
14392 KB |
Output is correct |
3 |
Correct |
8 ms |
14288 KB |
Output is correct |
4 |
Correct |
8 ms |
14392 KB |
Output is correct |
5 |
Correct |
10 ms |
14388 KB |
Output is correct |
6 |
Correct |
8 ms |
14436 KB |
Output is correct |
7 |
Correct |
9 ms |
14396 KB |
Output is correct |
8 |
Correct |
10 ms |
14416 KB |
Output is correct |
9 |
Correct |
8 ms |
14416 KB |
Output is correct |
10 |
Correct |
9 ms |
14416 KB |
Output is correct |
11 |
Correct |
8 ms |
14392 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
14732 KB |
Output is correct |
2 |
Correct |
10 ms |
14800 KB |
Output is correct |
3 |
Correct |
14 ms |
15040 KB |
Output is correct |
4 |
Correct |
11 ms |
15040 KB |
Output is correct |
5 |
Correct |
13 ms |
15112 KB |
Output is correct |
6 |
Correct |
13 ms |
15292 KB |
Output is correct |
7 |
Correct |
13 ms |
15260 KB |
Output is correct |
8 |
Correct |
13 ms |
15312 KB |
Output is correct |
9 |
Correct |
12 ms |
15184 KB |
Output is correct |
10 |
Correct |
13 ms |
15200 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
66 ms |
23908 KB |
Output is correct |
2 |
Correct |
70 ms |
23680 KB |
Output is correct |
3 |
Correct |
192 ms |
38364 KB |
Output is correct |
4 |
Correct |
186 ms |
37448 KB |
Output is correct |
5 |
Correct |
380 ms |
61744 KB |
Output is correct |
6 |
Correct |
428 ms |
61060 KB |
Output is correct |
7 |
Correct |
398 ms |
60908 KB |
Output is correct |
8 |
Correct |
416 ms |
61508 KB |
Output is correct |
9 |
Correct |
440 ms |
61016 KB |
Output is correct |
10 |
Correct |
504 ms |
60760 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
81 ms |
22608 KB |
Output is correct |
2 |
Correct |
82 ms |
23436 KB |
Output is correct |
3 |
Correct |
222 ms |
34908 KB |
Output is correct |
4 |
Correct |
261 ms |
36448 KB |
Output is correct |
5 |
Correct |
563 ms |
55460 KB |
Output is correct |
6 |
Correct |
515 ms |
59468 KB |
Output is correct |
7 |
Correct |
607 ms |
55676 KB |
Output is correct |
8 |
Correct |
484 ms |
58632 KB |
Output is correct |
9 |
Correct |
526 ms |
57908 KB |
Output is correct |
10 |
Correct |
455 ms |
58816 KB |
Output is correct |