oj.uz

Submission #959030

# Submission time Handle Problem Language Result Execution time Memory
959030 2024-04-07T11:50:07 Z d4xn Ideal city (IOI12_city) C++17
32 / 100
 602 ms 87352 KB 
//#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;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 82520 KB Output is correct
2 Correct 26 ms 82524 KB Output is correct
3 Correct 26 ms 82676 KB Output is correct
4 Correct 28 ms 82504 KB Output is correct
5 Correct 25 ms 82524 KB Output is correct
6 Correct 27 ms 82524 KB Output is correct
7 Correct 33 ms 82696 KB Output is correct
8 Correct 27 ms 82692 KB Output is correct
9 Correct 30 ms 82576 KB Output is correct
10 Correct 28 ms 82648 KB Output is correct
11 Correct 31 ms 82584 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 82760 KB Output is correct
2 Correct 172 ms 82748 KB Output is correct
3 Correct 333 ms 82796 KB Output is correct
4 Correct 338 ms 82800 KB Output is correct
5 Correct 585 ms 82836 KB Output is correct
6 Correct 602 ms 82780 KB Output is correct
7 Correct 525 ms 82828 KB Output is correct
8 Correct 522 ms 82832 KB Output is correct
9 Correct 601 ms 82828 KB Output is correct
10 Correct 599 ms 82832 KB Output is correct

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 80 ms 87352 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Incorrect 80 ms 86448 KB Output isn't correct
2 Halted 0 ms 0 KB -