#include <bits/stdc++.h>
#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 < 20; 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 = 19; 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:110:21: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
110 | auto[u, szu] = dsl.find_root(mp[{i, yy}], i - mnx);
| ^
city.cpp:111:21: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
111 | auto[v, szv] = dsr.find_root(mp[{i + 1, yy}], mxx - (i + 1));
| ^
city.cpp:121:17: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
121 | for(auto[u, v]:edges) {
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
300 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Correct |
1 ms |
304 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 |
2 ms |
340 KB |
Output is correct |
| 11 |
Correct |
1 ms |
340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
804 KB |
Output is correct |
| 2 |
Correct |
5 ms |
800 KB |
Output is correct |
| 3 |
Correct |
6 ms |
1108 KB |
Output is correct |
| 4 |
Correct |
6 ms |
988 KB |
Output is correct |
| 5 |
Correct |
8 ms |
1236 KB |
Output is correct |
| 6 |
Correct |
10 ms |
1304 KB |
Output is correct |
| 7 |
Correct |
8 ms |
1244 KB |
Output is correct |
| 8 |
Correct |
11 ms |
1212 KB |
Output is correct |
| 9 |
Correct |
10 ms |
1236 KB |
Output is correct |
| 10 |
Correct |
11 ms |
1244 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
116 ms |
10472 KB |
Output is correct |
| 2 |
Correct |
121 ms |
10444 KB |
Output is correct |
| 3 |
Correct |
403 ms |
26248 KB |
Output is correct |
| 4 |
Correct |
355 ms |
26352 KB |
Output is correct |
| 5 |
Execution timed out |
1067 ms |
52372 KB |
Time limit exceeded |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
115 ms |
10504 KB |
Output is correct |
| 2 |
Correct |
108 ms |
10472 KB |
Output is correct |
| 3 |
Correct |
347 ms |
26384 KB |
Output is correct |
| 4 |
Correct |
474 ms |
26284 KB |
Output is correct |
| 5 |
Correct |
874 ms |
52424 KB |
Output is correct |
| 6 |
Execution timed out |
1058 ms |
52492 KB |
Time limit exceeded |
| 7 |
Halted |
0 ms |
0 KB |
- |
