Submission #124996

#	Time	Username	Problem	Language	Result	Execution time	Memory
124996		RockyB	Ideal city (IOI12_city)	C++17	100 / 100	367 ms	18516 KiB

city

#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;

int 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)) {
      len += dfs(it.f, it.s);
    }
  }
  ans += len * 1ll *  (n - len) % mod;
  ans %= mod;
  return len;
}
int 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)) {
      len += dfs1(it.f, it.s);
    }
  }
  ans += len * 1ll * (n - len) % mod;
  ans %= mod;
  return len;
}
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;
}

• Subtask 1: 11 / 11
• Subtask 2: 21 / 21
• Subtask 3: 23 / 23
• Subtask 4: 45 / 45