oj.uz

Submission #959009

# Submission time Handle Problem Language Result Execution time Memory
959009 2024-04-07T11:22:08 Z vjudge1 Ideal city (IOI12_city) C++17
0 / 100
 17 ms 9348 KB 
//#include "city.h"
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define all(x) x.begin(), x.end()

const int N = 1e5+5, 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, 0));
      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, 0));
    if (it != cellX[x-1].end() && it->first == y && !vis[it->second]) {
      dp[it->second] = dp[idx] + n - (x ? cntX[0][x-1]*2 : 0); // 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, 0));
    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, 0));
    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, 0));
    if (it != cellX[x].end() && it->first == y-1 && !vis[it->second]) {
      dp[it->second] = dp[idx] + n - (y ? cntY[0][y-1]*2 : 0); // elementos con y' >= y+1
      dfs(it->second);
    }
  }
}

int DistanceSum(int NN, int *XX, int *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();
  }

  bfs(0);
  
  vis.reset();
  dfs(0);

  for (int i = 0; i < n; i++) {
    ans += dp[i];
  }
  return ans/2;
}

Subtask #1
0 / 11.0

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

Subtask #2
0 / 21.0

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

Subtask #3
0 / 23.0

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

Subtask #4
0 / 45.0

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