oj.uz

Submission #124992

# Submission time Handle Problem Language Result Execution time Memory
124992 2019-07-04T10:01:52 Z RockyB Ideal city (IOI12_city) C++17
0 / 100
 51 ms 3320 KB 
#include <bits/stdc++.h>

#define f first
#define s second

using namespace std;

const int mod = (int)1e9;

int n;
int ans;

map < pair <int, int>, int> used, a;

void dfs(int x, int y) {
  int len = 0;
  vector < pair <int, int > > go;
  int ptr = y - 1;
  while (a.count({x, ptr + 1})) {
    ++len, ++ptr;
    for (int i = -1; i <= 1; i += 2) {
      if (a.count({x + i, ptr}) && !used.count({x + i, ptr})) {
        go.push_back({x + i, ptr});
      }
    }
    used[{x, ptr}] = 1;
  }
  ptr = y;
  while (a.count({x, ptr - 1})) {
    ++len, --ptr;
    for (int i = -1; i <= 1; i += 2) {
      if (a.count({x + i, ptr}) && !used.count({x + i, ptr})) {
        go.push_back({x + i, ptr});
      }
    }
    used[{x, ptr}] = 1;
  }
  for (auto it : go) {
    if (!used.count(it)) {
      dfs(it.f, it.s);
    }
  }
  ans += len * 1ll *  (n - len) % mod;
  ans %= mod;
}
void dfs1(int x, int y) {
  int len = 0;
  vector < pair <int, int > > go;

  int ptr = x - 1;
  while (a.count({ptr + 1, y})) {
    ++len, ++ptr;
    for (int i = -1; i <= 1; i += 2) {
      if (a.count({ptr, y + i}) && !used.count({ptr, y + i})) {
        go.push_back({ptr, y + i});
      }
    }
    used[{ptr, y}] = 1;
  }
  ptr = x;
  while (a.count({ptr - 1, y})) {
    ++len, --ptr;
    for (int i = -1; i <= 1; i += 2) {
      if (a.count({ptr, y + i}) && !used.count({ptr, y + i})) {
        go.push_back({ptr, y + i});
      }
    }
    used[{ptr, y}] = 1;
  }
  for (auto it : go) {
    if (!used.count(it)) {
      dfs1(it.f, it.s);
    }
  }
  ans += len * 1ll * (n - len) % mod;
  ans %= mod;
}
int DistanceSum(int N, int *X, int *Y) {
  n = N;
  // copy finished

  for (int i = 0; i < N; i++) {
    a[{X[i], Y[i]}] = 1;
  }
  dfs(X[0], Y[0]);
  used.clear();
  dfs1(X[0], Y[0]);
  return ans / 2;
}

Subtask #1
0 / 11.0

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

Subtask #2
0 / 21.0

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

Subtask #3
0 / 23.0

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

Subtask #4
0 / 45.0

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