| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1195068 | madamadam3 | Ideal city (IOI12_city) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
#define int long long int
#define FOR(i, a, b) for (int i = a; i < b; i++)
#define pb push_back
#define trace(x) for (auto &a : x) cout << a << " ";
#define all(x) (x).begin(), (x).end()
using vi = vector<int>;
const int MOD = 1'000'000'000;
int n;
vector<int> x, y;
map<pair<int, int>, int> nmap;
map<int, vi> xmap;
/*
Stages (repeat for y):
(1) make rep nodes
for each column, go down from highest node on x to lowest node x
merge adjacent cells into one node (store size of component)
continue
(2) go through each column, join adjacent representatives with an edge
(3) take the tree structure, do dp to find number of paths going through each edge (= sum(|xi-xj| over all ij))
(4)
*/
void dfs_dp(int u, int p, int tlcmps, vector<set<int>> &adj, vi &weights, vi &DP, vi &sz) {
// cout << "Did I segfdault at u = " << u << " p = " << p << "?\n";
DP[u] = 0;
sz[u] = weights[u];
for (auto &v : adj[u]) {
// cout << "U = " << u << " V = " << v << " P = " << p << "\n";
if (v == p) continue;
// cout << "We are searching " << v << "\n";
dfs_dp(v, u, tlcmps, adj, weights, DP, sz);
DP[u] += DP[v] + sz[v];
sz[u] += sz[v];
}
}
void dfs_dp2(int u, int p, int tlcmps, vector<set<int>> &adj, vi &weights, vi &DP, vi &DP2, vi &sz) {
if (u != p) {
int pc = DP2[p] - DP[u] - sz[u];
int psz = sz[p] - sz[u];
DP2[u] = DP[u] + pc + psz;
}
for (auto &v : adj[u]) {
if (v == p) continue;
dfs_dp2(v, u, tlcmps, adj, weights, DP, DP2, sz);
}
}
void dfs(int u, int p, int tlcmps, int &total, vector<set<int>> &adj, vi &sz, vi &weights) {
sz[u] = weights[u];
for (auto v : adj[u]) {
if (v == p) continue;
dfs(v, u, tlcmps, total, adj, sz, weights);
sz[u] += sz[v];
}
total += sz[u] * (n - sz[u]);
total %= MOD;
}
int solveOrientation() {
int ans = 0;
map<int, vi> colblocks;
map<int, vi> blocks;
map<int, int> nodeblock;
int curcmp = -1;
for (auto &el : xmap) {
sort(all(el.second), [&](int a, int b) {return y[a] < y[b];});
int prevy = -10;
for (auto &node : el.second) {
if (y[node] > prevy + 1 || prevy == -10) {
curcmp++;
colblocks[el.first].pb(curcmp);
}
blocks[curcmp].pb(node);
nodeblock[node] = curcmp;
prevy = y[node];
}
}
set<pair<int, int>> edges;
for (int i = 0; i < n; i++) {
vector<pair<int, int>> d = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
for (auto v : d) {
if (!nmap.count({x[i] + v.first, y[i] + v.second})) continue;
int a = nodeblock[i];
int b = nodeblock[nmap[{x[i] + v.first, y[i] + v.second}]];
if (a == b) continue;
if (a > b) swap(a, b);
edges.insert({a, b});
}
}
int tlcmps = curcmp + 1;
vector<set<int>> nadj(tlcmps, set<int>());
for (auto edge : edges) {
nadj[edge.first].insert(edge.second);
nadj[edge.second].insert(edge.first);
}
vi weights(tlcmps);
FOR(i, 0, tlcmps) weights[i] = blocks[i].size();
vi DP(tlcmps, 0), sz(tlcmps, 0), DP2(tlcmps, 0);
// dfs_dp(0, 0, tlcmps, nadj, weights, DP, sz);
// DP2[0] = DP[0];
// dfs_dp2(0, 0, tlcmps, nadj, weights, DP, DP2, sz);
// ans = accumulate(all(DP2), 0);
int total = 0;
dfs(0, 0, tlcmps, total, nadj, sz, weights);
ans = total;
return ans;
}
signed DistanceSum(int _N, int *_X, int *_Y) {
int ans = 0;
n = _N;
x.resize(0); y.resize(0);
for (int i = 0; i < n; i++) x.pb(_X[i]), y.pb(_Y[i]);
FOR(i, 0, n) {
nmap[{x[i], y[i]}] = i;
xmap[x[i]].pb(i);
}
ans += solveOrientation();
ans %= MOD;
nmap.clear();
xmap.clear();
swap(x, y);
FOR(i, 0, n) {
nmap[{x[i], y[i]}] = i;
xmap[x[i]].pb(i);
}
ans += solveOrientation();
ans %= MOD;
n = 0;
x.clear();
y.clear();
return ans % MOD;
}