| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 547659 |
2022-04-11T08:32:02 Z |
tabr |
Ideal city (IOI12_city) |
C++17 |
|
449 ms |
37288 KB |
#include <bits/stdc++.h>
using namespace std;
#ifdef tabr
#include "library/debug.cpp"
#else
#define debug(...)
#endif
struct dsu {
vector<int> p;
vector<int> sz;
int n;
dsu(int _n) : n(_n) {
p = vector<int>(n);
iota(p.begin(), p.end(), 0);
sz = vector<int>(n, 1);
}
inline int get(int x) {
if (p[x] == x) {
return x;
} else {
return p[x] = get(p[x]);
}
}
inline bool unite(int x, int y) {
x = get(x);
y = get(y);
if (x == y) {
return false;
}
p[x] = y;
sz[y] += sz[x];
return true;
}
inline bool same(int x, int y) {
return (get(x) == get(y));
}
inline int size(int x) {
return sz[get(x)];
}
inline bool root(int x) {
return (x == get(x));
}
};
int DistanceSum(int n, int x[], int y[]) {
map<pair<int, int>, int> mp;
for (int i = 0; i < n; i++) {
mp[make_pair(x[i], y[i])] = i;
}
vector<vector<int>> g(n);
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};
for (int i = 0; i < n; i++) {
for (int dir = 0; dir < 4; dir++) {
int nx = x[i] + dx[dir];
int ny = y[i] + dy[dir];
if (mp.count(make_pair(nx, ny))) {
g[i].emplace_back(mp[make_pair(nx, ny)]);
}
}
}
vector<int> rx, ry;
map<pair<int, int>, int> sx, sy;
for (int z = 0; z < 2; z++) {
dsu uf(n);
for (int i = 0; i < n; i++) {
for (int j : g[i]) {
if (x[i] == x[j]) {
uf.unite(i, j);
}
}
}
vector<vector<int>> f(n);
vector<int> r(n);
for (int i = 0; i < n; i++) {
r[i] = uf.get(i);
if (i != r[i]) {
f[i].emplace_back(r[i]);
f[r[i]].emplace_back(i);
}
}
for (int i = 0; i < n; i++) {
for (int j : g[i]) {
if (y[i] == y[j] && uf.unite(i, j)) {
f[r[i]].emplace_back(r[j]);
f[r[j]].emplace_back(r[i]);
}
}
}
map<pair<int, int>, int> s;
vector<int> sz(n);
function<void(int, int)> Dfs = [&](int v, int p) {
sz[v] = 1;
for (int to : f[v]) {
if (to == p) {
continue;
}
Dfs(to, v);
sz[v] += sz[to];
}
if (p != -1 && r[v] == v && r[p] == p) {
s[make_pair(p, v)] = (n - sz[v]) - sz[v];
s[make_pair(v, p)] = sz[v] - (n - sz[v]);
}
};
Dfs(0, -1);
rx = r;
sx = s;
swap(x, y);
swap(rx, ry);
swap(sx, sy);
}
long long now0 = 0;
{
vector<int> d(n, -1);
queue<int> que;
d[0] = 0;
que.emplace(0);
while (!que.empty()) {
int v = que.front();
que.pop();
for (int to : g[v]) {
if (d[to] == -1) {
d[to] = d[v] + 1;
que.emplace(to);
}
}
}
now0 = accumulate(d.begin(), d.end(), 0LL);
}
long long res = 0;
vector<int> was(n);
function<void(int, long long)> Dfs = [&](int v, long long now) {
debug(v, now);
res += now;
was[v] = 1;
for (int to : g[v]) {
if (was[to]) {
continue;
}
long long nxt = now;
if (x[v] != x[to]) {
nxt += sx[make_pair(rx[v], rx[to])];
} else {
nxt += sy[make_pair(ry[v], ry[to])];
}
Dfs(to, nxt);
}
};
Dfs(0, now0);
return (int) (res / 2 % (long long) 1e9);
}
#ifdef tabr
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n = 11;
int x[] = {2, 2, 3, 3, 4, 4, 4, 4, 5, 5, 5};
int y[] = {5, 6, 3, 6, 3, 4, 5, 6, 3, 4, 6};
cout << DistanceSum(n, x, y) << '\n';
return 0;
}
#endif
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
304 KB |
Output is correct |
| 4 |
Correct |
1 ms |
300 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
340 KB |
Output is correct |
| 7 |
Correct |
1 ms |
304 KB |
Output is correct |
| 8 |
Correct |
1 ms |
340 KB |
Output is correct |
| 9 |
Correct |
1 ms |
340 KB |
Output is correct |
| 10 |
Correct |
1 ms |
304 KB |
Output is correct |
| 11 |
Correct |
1 ms |
340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
596 KB |
Output is correct |
| 2 |
Correct |
3 ms |
560 KB |
Output is correct |
| 3 |
Correct |
4 ms |
852 KB |
Output is correct |
| 4 |
Correct |
3 ms |
724 KB |
Output is correct |
| 5 |
Correct |
5 ms |
952 KB |
Output is correct |
| 6 |
Correct |
5 ms |
952 KB |
Output is correct |
| 7 |
Correct |
5 ms |
1084 KB |
Output is correct |
| 8 |
Correct |
4 ms |
852 KB |
Output is correct |
| 9 |
Correct |
6 ms |
920 KB |
Output is correct |
| 10 |
Correct |
5 ms |
852 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
48 ms |
6920 KB |
Output is correct |
| 2 |
Correct |
46 ms |
7036 KB |
Output is correct |
| 3 |
Correct |
125 ms |
16700 KB |
Output is correct |
| 4 |
Correct |
142 ms |
16564 KB |
Output is correct |
| 5 |
Correct |
303 ms |
33156 KB |
Output is correct |
| 6 |
Correct |
315 ms |
33220 KB |
Output is correct |
| 7 |
Correct |
331 ms |
32776 KB |
Output is correct |
| 8 |
Correct |
313 ms |
33180 KB |
Output is correct |
| 9 |
Correct |
341 ms |
33184 KB |
Output is correct |
| 10 |
Correct |
312 ms |
36116 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
54 ms |
7692 KB |
Output is correct |
| 2 |
Correct |
50 ms |
6976 KB |
Output is correct |
| 3 |
Correct |
206 ms |
18568 KB |
Output is correct |
| 4 |
Correct |
166 ms |
16472 KB |
Output is correct |
| 5 |
Correct |
418 ms |
36796 KB |
Output is correct |
| 6 |
Correct |
367 ms |
29896 KB |
Output is correct |
| 7 |
Correct |
449 ms |
37288 KB |
Output is correct |
| 8 |
Correct |
364 ms |
28968 KB |
Output is correct |
| 9 |
Correct |
354 ms |
28836 KB |
Output is correct |
| 10 |
Correct |
379 ms |
26500 KB |
Output is correct |
