oj.uz

Submission #879718

# Submission time Handle Problem Language Result Execution time Memory
879718 2023-11-28T02:00:10 Z NeroZein Ideal city (IOI12_city) C++17
11 / 100
 1000 ms 3156 KB 
#include "bits/stdc++.h"
using namespace std; 

const int md = (int) 1e9; 

int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1}; 

int DistanceSum(int N, int *X, int *Y) {
  int ret = 0;
  map<pair<int, int>, int> cells;
  for (int i = 0; i < N; ++i) {
    cells[make_pair(X[i], Y[i])] = i; 
  }
  for (int i = 0; i < N; ++i) {
    queue<pair<int, int>> que; 
    map<pair<int, int>, int> mp; 
    que.emplace(X[i], Y[i]); 
    mp[make_pair(X[i], Y[i])] = 0; 
    while (!que.empty()) {
      auto [x, y] = que.front();
      que.pop();
      if (cells[make_pair(x, y)] < i) {
        ret += mp[make_pair(x, y)];
        ret %= md;         
      }
      for (int k = 0; k < 4; ++k) {
        int nx = x + dx[k], ny = y + dy[k];
        if (cells.count(make_pair(nx, ny)) && !mp.count(make_pair(nx, ny))) {
          mp[make_pair(nx, ny)] = mp[make_pair(x, y)] + 1; 
          que.emplace(nx, ny); 
        }
      }
    }
  }
  return ret;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 5 ms 604 KB Output is correct
5 Correct 5 ms 600 KB Output is correct
6 Correct 22 ms 348 KB Output is correct
7 Correct 20 ms 348 KB Output is correct
8 Correct 19 ms 464 KB Output is correct
9 Correct 22 ms 348 KB Output is correct
10 Correct 21 ms 464 KB Output is correct
11 Correct 21 ms 472 KB Output is correct

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 677 ms 556 KB Output is correct
2 Correct 627 ms 560 KB Output is correct
3 Execution timed out 1027 ms 600 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1064 ms 3156 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1008 ms 3092 KB Time limit exceeded
2 Halted 0 ms 0 KB -