Submission #959022

#TimeUsernameProblemLanguageResultExecution timeMemory
959022vjudge1Ideal city (IOI12_city)C++17
32 / 100
593 ms87376 KiB
//#include "city.h" #include <bits/stdc++.h> using namespace std; #define ll long long #define int long long #define all(x) x.begin(), x.end() const int N = 1e6+6, inf = INT_MAX; const vector<pair<int, int>> dir = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}}; int n, X[N], Y[N], cntX[2][N], cntY[2][N]; ll ans, dp[N]; vector<pair<int, int>> cellX[N], cellY[N]; bitset<N> vis; bool ok(int x, int y) { return min(x, y) >= 0; } void bfs(int idx) { queue<pair<int, int>> q; q.push(make_pair(0, idx)); while (!q.empty()) { int d = q.front().first; int nwIdx = q.front().second; q.pop(); if (vis[nwIdx]) continue; vis[nwIdx] = 1; dp[idx] += d; int x = X[nwIdx]; int y = Y[nwIdx]; for (auto [a, b] : dir) { if (!ok(x+a, y+b)) continue; auto it = lower_bound(all(cellX[x+a]), make_pair(y+b, 0ll)); if (it != cellX[x+a].end() && it->first == y+b && !vis[it->second]) { q.push(make_pair(d+1, it->second)); } } } } void dfs(int idx) { vis[idx] = 1; int x = X[idx]; int y = Y[idx]; // arriba if (ok(x-1, y)) { auto it = lower_bound(all(cellX[x-1]), make_pair(y, 0ll)); if (it != cellX[x-1].end() && it->first == y && !vis[it->second]) { dp[it->second] = dp[idx] + n - cntX[0][x-1]*2; // elementos con x' <= x-1 dfs(it->second); } } // abajo if (ok(x+1, y)) { auto it = lower_bound(all(cellX[x+1]), make_pair(y, 0ll)); if (it != cellX[x+1].end() && it->first == y && !vis[it->second]) { dp[it->second] = dp[idx] + n - cntX[1][x+1]*2; // elementos con x' >= x+1 dfs(it->second); } } // derecha if (ok(x, y+1)) { auto it = lower_bound(all(cellX[x]), make_pair(y+1, 0ll)); if (it != cellX[x].end() && it->first == y+1 && !vis[it->second]) { dp[it->second] = dp[idx] + n - cntY[1][y+1]*2; // elementos con y' >= y+1 dfs(it->second); } } // izquierda if (ok(x, y-1)) { auto it = lower_bound(all(cellX[x]), make_pair(y-1, 0ll)); if (it != cellX[x].end() && it->first == y-1 && !vis[it->second]) { dp[it->second] = dp[idx] + n - cntY[0][y-1]*2; // elementos con y' >= y+1 dfs(it->second); } } } int DistanceSum(signed NN, signed *XX, signed *YY) { n = NN; ans = 0; int mnX = inf; int mnY = inf; for (int i = 0; i < n; i++) { X[i] = XX[i]; Y[i] = YY[i]; mnX = min(mnX, X[i]); mnY = min(mnY, Y[i]); } for (int i = 0; i < n; i++) { X[i] -= mnX; Y[i] -= mnY; cellX[X[i]].push_back(make_pair(Y[i], i)); cellY[Y[i]].push_back(make_pair(X[i], i)); } for (int i = 0; i < N; i++) { sort(all(cellX[i])); sort(all(cellY[i])); } for (int i = 0; i < N; i++) { cntX[0][i] = (i ? cntX[0][i-1] : 0) + cellX[i].size(); cntY[0][i] = (i ? cntY[0][i-1] : 0) + cellY[i].size(); } for (int i = N-1; i >= 0; i--) { cntX[1][i] = (i+1 < N ? cntX[1][i+1] : 0) + cellX[i].size(); cntY[1][i] = (i+1 < N ? cntY[1][i+1] : 0) + cellY[i].size(); } if (n <= 5000) { for (int i = 0; i < n; i++) { vis.reset(); bfs(i); ans += dp[i]; } return ans/2; } bfs(0); vis.reset(); dfs(0); for (int i = 0; i < n; i++) { ans += dp[i];cerr << dp[i] << endl; } 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...