Submission #1194995

#	Time	Username	Problem	Language	Result	Execution time	Memory
1194995		madamadam3	Ideal city (IOI12_city)	C++20	0 / 100	1099 ms	96644 KiB

city

#include <bits/stdc++.h>

using namespace std;

#define FOR(i, a, b) for (int i = a; i < b; i++)
#define pb push_back
#define trace(x) for (auto &a : x) cout << a << " ";

const int MOD = 1'000'000'000;

int n;
vector<int> x, y;
map<pair<int, int>, int> nmap;
vector<vector<int>> adj;

int bfs_sum(int node) {
  int ans = 0;

  set<int> vis;
  vector<int> dist(n, 0);
  queue<int> q; q.push(node);

  while (!q.empty()) {
    int cur = q.front();
    q.pop();

    vis.insert(cur);

    for (int nei : adj[cur]) {
      if (vis.count(nei)) continue;
      dist[nei] = dist[cur] + 1;

      q.push(nei);
    }

  }
  
  FOR(i, node+1, n) {
    ans += dist[i];
    ans %= MOD;
  }

  return ans % MOD;
}

int DistanceSum(int _N, int *_X, int *_Y) {
  n = _N;
  x.resize(0); y.resize(0);
  adj.assign(n, vector<int>());
  for (int i = 0; i < n; i++) x.pb(_X[i]), y.pb(_Y[i]); 

  FOR(i, 0, n) {
    nmap[{x[i], y[i]}] = i;
  }

  FOR(i, 0, n) {
    FOR(dx, -1, 2) {
      FOR(dy, -1, 2) {
        if (abs(dx) == abs(dy)) continue;
        if (!nmap.count({x[i] + dx, y[i] + dy})) continue;
        adj[i].pb(nmap[{x[i] + dx, y[i] + dy}]);
      }
    }
  }

  int ans = 0;
  FOR(i, 0, n) {
    ans += bfs_sum(i);
    ans %= MOD;
  }

  return ans % MOD;
}

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