Submission #1241758

#	Time	Username	Problem	Language	Result	Execution time	Memory
1241758		luvlorndev	Ideal city (IOI12_city)	C++20	11 / 100	1094 ms	1352 KiB

city

#include <bits/stdc++.h>
using namespace std;
#define ll long long

int coorX[2010];
int coorY[2010];
int MOD = 1000000000;
int dx[4] = {1,-1,0,0};
int dy[4] = {0,0,1,-1};
map<pair<int, int>, int> mp;

ll bfs(int idx, int n) {
  queue <int> q;
  vector<bool> visited(2010,0);
  vector<int> dist(2010, 0);
  q.push(idx);
  visited[idx]=1;
  while (!q.empty()) {
    int fr = q.front();
    q.pop();

    // cout << fr << " " << dist[fr] << endl;
    int cx = coorX[fr];
    int cy = coorY[fr];
    for (int i = 0; i < 4; i++) {
      int nx = cx+dx[i];
      int ny = cy+dy[i];
      if (mp.count(make_pair(nx, ny))) {
        int nxt = mp[make_pair(nx, ny)];
        if (visited[nxt] == 0) {
          q.push(nxt);
          dist[nxt] = dist[fr]+1;
          visited[nxt] = 1;
        }
      }
    }
  }
  ll sum =0 ;
  for (int i = 0; i < idx; i++) {
    sum += dist[i];
    // cout << dist[i] << endl;
  }
  return sum;
}

int DistanceSum(int N, int *X, int *Y) {
  for (int i = 0; i < N; i++) {
    mp[make_pair(X[i], Y[i])] = i;
    coorX[i] = X[i];
    coorY[i] = Y[i];
  }

  ll sumtot = 0;
  for (int i = 0; i < N; i++) {
    sumtot += bfs(i, N);
    sumtot %= MOD;
  }
  
  return sumtot;
}

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