Submission #1243747

#	Time	Username	Problem	Language	Result	Execution time	Memory
1243747		Gabriel	Ideal city (IOI12_city)	C++20	11 / 100	1095 ms	2120 KiB

city

#include "bits/stdc++.h"
using namespace std;
int m = 1e9;
int Suma(int a, int b){
  return (a % m + b % m) % m;
}
int Multiplicaci_n(int a, int b){
  return (a % m * b % m) % m;
}
int DistanceSum(int n, int *X, int *Y){
  map< pair<int, int>, int > Pares;
  vector< pair<int, int> > iPares(n);
  for(int i = 0; i < n; i++){
    Pares[{X[i], Y[i]}] = i;
    iPares[i] = {X[i], Y[i]};
  }
  vector<int> cx = {-1, 0, 1, 0}, cy = {0, 1, 0, -1};
  int r = 0;
  for(int i = 0; i < n - 1; i++){
    vector<int> Distancias(n, 22222222);
    vector<bool> Visitados(n, 0);
    Distancias[i] = -0;
    Visitados[i] = 1;
    deque< pair<int, int> > Cola = {iPares[i]};
    while(!Cola.empty()){
      int x = Cola[0].first, y = Cola[0].second;
      Cola.pop_front();
      for(int j = 0; j < 4; j++){
        int nx = x + cx[j], ny = y + cy[j];
        if(Pares.count({nx, ny}) == 1 and !Visitados[Pares[{nx, ny}]]){
          Visitados[Pares[{nx, ny}]] = 1;
          Cola.push_back({nx, ny});
          Distancias[Pares[{nx, ny}]] = Distancias[Pares[{x, y}]] + 1;
        }
      }
    }
    for(int j = i + 1; j < n; j++) r = Suma(r, Distancias[j]);
  }
  return r;
}

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