Submission #879718

#	Time	Username	Problem	Language	Result	Execution time	Memory
879718		NeroZein	Ideal city (IOI12_city)	C++17	11 / 100	1064 ms	3156 KiB

city

#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 / 11
• Subtask 2: 0 / 21
• Subtask 3: 0 / 23
• Subtask 4: 0 / 45