Submission #801945

#TimeUsernameProblemLanguageResultExecution timeMemory
801945pavementIdeal city (IOI12_city)C++17
0 / 100
36 ms10644 KiB
#include <bits/stdc++.h> using namespace std; #define mp make_pair #define eb emplace_back using ii = pair<int, int>; const int MOD = (int)1e9; int rep[100005]; vector<ii> row[100005], col[100005]; 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 : {row, col}) { ufds::init(N); int cnt = 0, ccs = 0, cur_prod = 0, tot_sz = 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 + 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++; ccs++; cur_prod += tot_sz; cur_prod %= MOD; tot_sz++; } else { idx = upper; cur_prod += tot_sz - ufds::sz[upper]; cur_prod %= MOD; ufds::sz[upper]++; tot_sz++; } rep[cur] = idx; if (prv_j != -1 && prv_j + 1 == j) { if (ufds::find(prv_idx) != ufds::find(idx)) { ccs--; cur_prod -= ufds::sz[ufds::find(prv_idx)] * (tot_sz - ufds::sz[ufds::find(prv_idx)]) % MOD; cur_prod %= MOD; tot_sz -= ufds::sz[ufds::find(prv_idx)]; cur_prod -= ufds::sz[ufds::find(idx)] * (tot_sz - ufds::sz[ufds::find(idx)]) % MOD; cur_prod %= MOD; tot_sz -= ufds::sz[ufds::find(idx)]; ufds::unite(prv_idx, idx); cur_prod += tot_sz * ufds::sz[ufds::find(prv_idx)] % MOD; cur_prod %= MOD; tot_sz += ufds::sz[ufds::find(prv_idx)]; if (cur_prod < 0) cur_prod += MOD; } } prv_j = j; prv_idx = idx; } //~ cout << "@ " << i << ' ' << cur_prod << ' ' << tot_sz << endl; ans += (2 * cur_prod % MOD + tot_sz * (N - tot_sz) % MOD) % MOD; ans %= MOD; } } for (auto dim : {row, col}) { ufds::init(N); int cnt = 0, ccs = 0, cur_prod = 0, tot_sz = 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++; ccs++; cur_prod += tot_sz; cur_prod %= MOD; tot_sz++; } else { idx = upper; cur_prod += tot_sz - ufds::sz[upper]; cur_prod %= MOD; ufds::sz[upper]++; tot_sz++; } rep[cur] = idx; if (prv_j != -1 && prv_j + 1 == j) { if (ufds::find(prv_idx) != ufds::find(idx)) { ccs--; cur_prod -= ufds::sz[ufds::find(prv_idx)] * (tot_sz - ufds::sz[ufds::find(prv_idx)]) % MOD; cur_prod %= MOD; tot_sz -= ufds::sz[ufds::find(prv_idx)]; cur_prod -= ufds::sz[ufds::find(idx)] * (tot_sz - ufds::sz[ufds::find(idx)]) % MOD; cur_prod %= MOD; tot_sz -= ufds::sz[ufds::find(idx)]; ufds::unite(prv_idx, idx); cur_prod += tot_sz * ufds::sz[ufds::find(prv_idx)] % MOD; cur_prod %= MOD; tot_sz += ufds::sz[ufds::find(prv_idx)]; if (cur_prod < 0) cur_prod += MOD; } } prv_j = j; prv_idx = idx; } //~ cout << "@ " << i << ' ' << cur_prod << ' ' << tot_sz << endl; ans += 2 * cur_prod % MOD; ans %= MOD; } } return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...