#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define IO_OP ios::sync_with_stdio(0), cin.tie(0)
#define F first
#define S second
#define V vector
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(v) int((v).size())
#define ALL(v) (v).begin(), (v).end()
#define SORT_UNIQUE(v) sort(ALL(v)), (v).resize(unique(ALL(v)) - (v).begin())
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;
const int INF = 1e9 + 7, M = 1000000000;
int dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0};
struct DS {
vi p, pp, when, any, sz;
V<vi> pps;
DS(int n) {
p.resize(n), pp.resize(n), any.resize(n), when.resize(n, -1), sz.resize(n, 1);
iota(ALL(p), 0), iota(ALL(pp), 0), iota(ALL(any), 0);
}
int find(int u) {
return p[u] == u ? u : p[u] = find(p[u]);
}
void add(int u, int v, int t) {
u = find(u), v = find(v);
if(u == v) return;
int nw = SZ(p);
p.PB(nw), pp.PB(nw), when.PB(t), sz.PB(sz[u] + sz[v]), any.PB(any[u]);
p[u] = p[v] = pp[u] = pp[v] = nw;
}
void build() {
pps.PB(pp);
for(int j = 1; j < 17; j++) {
vi npp;
for(int i = 0; i < SZ(pp); i++)
npp.PB(pps.back()[pps.back()[i]]);
pps.PB(npp);
}
}
pi find_root(int u, int t) {
for(int i = 16; i >= 0; i--) {
if(when[pps[i][u]] <= t) {
u = pps[i][u];
}
}
return {any[u], sz[u]};
}
};
void add(int& a, int b) {
a += b;
if(a >= M) a -= M;
}
int solve(int n, int* x, int *y) {
int ans = 0;
map<pi, int> mp;
map<int, vi> ys;
int mnx = INF, mxx = -INF;
for(int i = 0; i < n; i++) {
mp[{x[i], y[i]}] = i;
ys[x[i]].PB(y[i]);
mnx = min(mnx, x[i]);
mxx = max(mxx, x[i]);
}
DS dsl(n), dsr(n);
for(int i = mnx; i <= mxx; i++) {
int t = i - mnx;
for(int yy:ys[i]) {
if(mp.count({i, yy - 1})) {
int u = mp[{i, yy}], v = mp[{i, yy - 1}];
dsl.add(u, v, t);
}
if(mp.count({i - 1, yy})) {
int u = mp[{i, yy}], v = mp[{i - 1, yy}];
dsl.add(u, v, t);
}
}
}
for(int i = mxx; i >= mnx; i--) {
int t = mxx - i;
for(int yy:ys[i]) {
if(mp.count({i, yy + 1})) {
int u = mp[{i, yy}], v = mp[{i, yy + 1}];
dsr.add(u, v, t);
}
if(mp.count({i + 1, yy})) {
int u = mp[{i, yy}], v = mp[{i + 1, yy}];
dsr.add(u, v, t);
}
}
}
dsl.build();
dsr.build();
vi sz(n, 1);
for(int i = mnx; i < mxx; i++) {
vi nodes;
V<pi> edges;
for(int yy:ys[i]) {
if(mp.count({i + 1, yy})) {
auto[u, szu] = dsl.find_root(mp[{i, yy}], i - mnx);
auto[v, szv] = dsr.find_root(mp[{i + 1, yy}], mxx - (i + 1));
sz[u] = szu;
sz[v] = szv;
nodes.PB(u), nodes.PB(v);
edges.EB(u, v);
}
}
SORT_UNIQUE(nodes), SORT_UNIQUE(edges);
assert(SZ(edges) == SZ(nodes) - 1);
V<vi> G(SZ(nodes));
for(auto[u, v]:edges) {
u = lower_bound(ALL(nodes), u) - nodes.begin();
v = lower_bound(ALL(nodes), v) - nodes.begin();
G[u].PB(v), G[v].PB(u);
}
function<int(int, int)> dfs = [&] (int u, int p) {
int siz = sz[nodes[u]];
for(int v:G[u]) if(v != p) {
int tt = dfs(v, u);
add(ans, 1LL * tt * (n - tt) % M);
siz += tt;
}
return siz;
};
dfs(0, -1);
}
return ans;
}
int DistanceSum(int n, int *x, int *y) {
return (solve(n, x, y) + solve(n, y, x)) % M;
}
Compilation message
city.cpp: In function 'int solve(int, int*, int*)':
city.cpp:111:21: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
111 | auto[u, szu] = dsl.find_root(mp[{i, yy}], i - mnx);
| ^
city.cpp:112:21: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
112 | auto[v, szv] = dsr.find_root(mp[{i + 1, yy}], mxx - (i + 1));
| ^
city.cpp:122:17: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
122 | for(auto[u, v]:edges) {
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Correct |
1 ms |
340 KB |
Output is correct |
| 6 |
Correct |
2 ms |
344 KB |
Output is correct |
| 7 |
Correct |
2 ms |
340 KB |
Output is correct |
| 8 |
Correct |
1 ms |
340 KB |
Output is correct |
| 9 |
Correct |
2 ms |
340 KB |
Output is correct |
| 10 |
Correct |
1 ms |
340 KB |
Output is correct |
| 11 |
Correct |
2 ms |
340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
724 KB |
Output is correct |
| 2 |
Correct |
5 ms |
724 KB |
Output is correct |
| 3 |
Correct |
8 ms |
980 KB |
Output is correct |
| 4 |
Correct |
8 ms |
980 KB |
Output is correct |
| 5 |
Correct |
10 ms |
1224 KB |
Output is correct |
| 6 |
Correct |
12 ms |
1212 KB |
Output is correct |
| 7 |
Correct |
8 ms |
1208 KB |
Output is correct |
| 8 |
Correct |
8 ms |
1132 KB |
Output is correct |
| 9 |
Correct |
11 ms |
1108 KB |
Output is correct |
| 10 |
Correct |
11 ms |
1212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
123 ms |
9384 KB |
Output is correct |
| 2 |
Correct |
134 ms |
9408 KB |
Output is correct |
| 3 |
Correct |
362 ms |
23088 KB |
Output is correct |
| 4 |
Correct |
348 ms |
23284 KB |
Output is correct |
| 5 |
Correct |
991 ms |
45996 KB |
Output is correct |
| 6 |
Correct |
892 ms |
46900 KB |
Output is correct |
| 7 |
Correct |
829 ms |
46908 KB |
Output is correct |
| 8 |
Correct |
847 ms |
46768 KB |
Output is correct |
| 9 |
Correct |
888 ms |
47012 KB |
Output is correct |
| 10 |
Correct |
881 ms |
49468 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
91 ms |
9308 KB |
Output is correct |
| 2 |
Correct |
110 ms |
9372 KB |
Output is correct |
| 3 |
Correct |
297 ms |
23232 KB |
Output is correct |
| 4 |
Correct |
320 ms |
23268 KB |
Output is correct |
| 5 |
Correct |
785 ms |
46156 KB |
Output is correct |
| 6 |
Correct |
907 ms |
46104 KB |
Output is correct |
| 7 |
Correct |
776 ms |
45984 KB |
Output is correct |
| 8 |
Correct |
926 ms |
46876 KB |
Output is correct |
| 9 |
Correct |
859 ms |
46820 KB |
Output is correct |
| 10 |
Correct |
880 ms |
46856 KB |
Output is correct |
