Submission #803210

#TimeUsernameProblemLanguageResultExecution timeMemory
803210pavementIdeal city (IOI12_city)C++17
32 / 100
26 ms9184 KiB
#include <bits/stdc++.h> using namespace std; #define mp make_pair #define mt make_tuple #define pb push_back #define eb emplace_back using ll = long long; using ii = pair<int, int>; const int MOD = (int)1e9; int rep[100005], dist[100005]; bool vis[100005]; ii row_to_1[100005], col_to_1[100005], row_to_2[100005], col_to_2[100005]; vector<int> adj[100005]; vector<ii> row[100005], col[100005]; queue<int> Q; namespace ufds { int lnk[100005], sz[100005]; void init(int n) { iota(lnk, lnk + n, 0); fill(sz, sz + n, 1); } int find(int x) { if (x == lnk[x]) return x; return lnk[x] = find(lnk[x]); } void unite(int a, int b) { a = find(a); b = find(b); if (a == b) return; if (sz[b] > sz[a]) swap(a, b); sz[a] += sz[b]; lnk[b] = a; } }; int DistanceSum(int N, int X[], int Y[]) { int ans = 0, min_X = *min_element(X, X + N), min_Y = *min_element(Y, Y + N); for (int i = 0; i < N; i++) { X[i] -= min_X; Y[i] -= min_Y; assert(0 <= X[i] && X[i] < N && 0 <= Y[i] && Y[i] < N); row[X[i]].eb(Y[i], i); col[Y[i]].eb(X[i], i); } for (int i = 0; i < N; i++) { sort(row[i].begin(), row[i].end()); sort(col[i].begin(), col[i].end()); } for (auto [dim, to] : {mp(row, row_to_1), mp(col, col_to_1)}) { ufds::init(N); int cnt = 0; for (int i = 0; i < N; i++) { int prv_j = -1, prv_idx = -1; for (auto [j, cur] : dim[i]) { int upper = -1, idx; if (i) { auto it = lower_bound(dim[i - 1].begin(), dim[i - 1].end(), mp(j, 0)); if (it != dim[i - 1].end() && it->first == j) { upper = ufds::find(rep[it->second]); } } if (upper == -1) { idx = cnt++; } else { idx = upper; ufds::sz[upper]++; } rep[cur] = idx; if (prv_j != -1 && prv_j + 1 == j) { if (ufds::find(prv_idx) != ufds::find(idx)) { ufds::unite(prv_idx, idx); } } prv_j = j; prv_idx = idx; } for (auto [j, cur] : dim[i]) { to[cur] = mp(ufds::find(rep[cur]), ufds::sz[ufds::find(rep[cur])]); } } } for (auto [dim, to] : {mp(row, row_to_2), mp(col, col_to_2)}) { ufds::init(N); int cnt = 0; for (int i = N - 1; i >= 0; i--) { int prv_j = -1, prv_idx = -1; for (auto [j, cur] : dim[i]) { int upper = -1, idx; if (i + 1 < N) { auto it = lower_bound(dim[i + 1].begin(), dim[i + 1].end(), mp(j, 0)); if (it != dim[i + 1].end() && it->first == j) { upper = ufds::find(rep[it->second]); } } if (upper == -1) { idx = cnt++; } else { idx = upper; ufds::sz[upper]++; } rep[cur] = idx; if (prv_j != -1 && prv_j + 1 == j) { if (ufds::find(prv_idx) != ufds::find(idx)) { ufds::unite(prv_idx, idx); } } prv_j = j; prv_idx = idx; } for (auto [j, cur] : dim[i]) { to[cur] = mp(ufds::find(rep[cur]), ufds::sz[ufds::find(rep[cur])]); } } } for (auto [dim, to_1, to_2] : {mt(row, row_to_1, row_to_2), mt(col, col_to_1, col_to_2)}) { for (int i = 1; i < N; i++) { vector<ii> nodes, edges; for (auto [j, cur] : dim[i]) { int upper = -1; if (i) { auto it = lower_bound(dim[i - 1].begin(), dim[i - 1].end(), mp(j, 0)); if (it != dim[i - 1].end() && it->first == j) { upper = it->second; } } if (upper != -1) { nodes.pb(mp(to_2[cur].first + N, to_2[cur].second)); nodes.pb(mp(to_1[upper].first, to_1[upper].second)); edges.eb(to_2[cur].first + N, to_1[upper].first); } } sort(nodes.begin(), nodes.end()); nodes.erase(unique(nodes.begin(), nodes.end()), nodes.end()); for (auto [x, s] : nodes) { adj[x].clear(); } for (auto [u, v] : edges) { adj[u].pb(v); adj[v].pb(u); } for (auto [x, s] : nodes) { for (auto [x2, _] : nodes) { vis[x2] = 0; } dist[x] = 0; vis[x] = 1; Q.push(x); while (!Q.empty()) { int a = Q.front(); Q.pop(); for (auto v : adj[a]) { if (!vis[v]) { vis[v] = 1; dist[v] = dist[a] + 1; Q.push(v); } } } for (auto [x2, s2] : nodes) { ans = (ans + (ll)dist[x2] * s2 % MOD * (ll)s % MOD) % MOD; } } } } return ans / 2; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...