Submission #959030

#	Time	Username	Problem	Language	Result	Execution time	Memory
959030		d4xn	Ideal city (IOI12_city)	C++17	32 / 100	602 ms	87352 KiB

city

//#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 / 11
• Subtask 2: 21 / 21
• Subtask 3: 0 / 23
• Subtask 4: 0 / 45