oj.uz

Submission #959020

# Submission time Handle Problem Language Result Execution time Memory
959020 2024-04-07T11:36:56 Z vjudge1 Ideal city (IOI12_city) C++17
32 / 100
 582 ms 16732 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 = 2e5+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();
  }

  if (NN <= 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 4 ms 14936 KB Output is correct
2 Correct 5 ms 14940 KB Output is correct
3 Correct 4 ms 14940 KB Output is correct
4 Correct 6 ms 14992 KB Output is correct
5 Correct 6 ms 14940 KB Output is correct
6 Correct 7 ms 14940 KB Output is correct
7 Correct 8 ms 14936 KB Output is correct
8 Correct 7 ms 14940 KB Output is correct
9 Correct 8 ms 14976 KB Output is correct
10 Correct 8 ms 14964 KB Output is correct
11 Correct 8 ms 14936 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 14936 KB Output is correct
2 Correct 139 ms 15024 KB Output is correct
3 Correct 308 ms 15048 KB Output is correct
4 Correct 307 ms 14940 KB Output is correct
5 Correct 545 ms 15072 KB Output is correct
6 Correct 582 ms 15172 KB Output is correct
7 Correct 516 ms 14940 KB Output is correct
8 Correct 495 ms 15068 KB Output is correct
9 Correct 563 ms 15184 KB Output is correct
10 Correct 568 ms 14936 KB Output is correct

Subtask #3
0 / 23.0

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

Subtask #4
0 / 45.0

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