oj.uz

Submission #124996

# Submission time Handle Problem Language Result Execution time Memory
124996 2019-07-04T10:11:14 Z RockyB Ideal city (IOI12_city) C++17
100 / 100
 367 ms 18516 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;

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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 252 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 2 ms 380 KB Output is correct
11 Correct 3 ms 376 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 504 KB Output is correct
2 Correct 4 ms 508 KB Output is correct
3 Correct 5 ms 508 KB Output is correct
4 Correct 5 ms 504 KB Output is correct
5 Correct 6 ms 632 KB Output is correct
6 Correct 6 ms 632 KB Output is correct
7 Correct 6 ms 632 KB Output is correct
8 Correct 6 ms 632 KB Output is correct
9 Correct 6 ms 632 KB Output is correct
10 Correct 12 ms 632 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 3320 KB Output is correct
2 Correct 49 ms 3192 KB Output is correct
3 Correct 135 ms 7516 KB Output is correct
4 Correct 131 ms 7596 KB Output is correct
5 Correct 310 ms 15096 KB Output is correct
6 Correct 292 ms 15060 KB Output is correct
7 Correct 289 ms 14328 KB Output is correct
8 Correct 298 ms 15076 KB Output is correct
9 Correct 274 ms 14664 KB Output is correct
10 Correct 290 ms 18516 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 3064 KB Output is correct
2 Correct 51 ms 3292 KB Output is correct
3 Correct 138 ms 7160 KB Output is correct
4 Correct 142 ms 7412 KB Output is correct
5 Correct 305 ms 14000 KB Output is correct
6 Correct 318 ms 14512 KB Output is correct
7 Correct 367 ms 14328 KB Output is correct
8 Correct 300 ms 14200 KB Output is correct
9 Correct 303 ms 13944 KB Output is correct
10 Correct 304 ms 13944 KB Output is correct