Submission #1209343

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209343		LIA	Ideal city (IOI12_city)	C++17	0 / 100	1096 ms	5444 KiB

city

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef tuple<ll, ll, ll> plll;
typedef vector<plll> vplll;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
typedef vector<pll> vpll;
typedef vector<vector<pll>> vvpll;
typedef vector<vector<ll>> vvll;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;
#define loop(i, s, e) for (ll i = (s); i < (e); ++i)
#define loopr(i, e, s) for (ll i = (e)-1; i >= (s); --i)
#define all(a) a.begin(), a.end()
const ll inf = 1e18;
const ll mod = 1e9;
vvll g;
ll ans = 0;
vll dist;
ll n;
void di(ll source) {
  dist.assign(n, inf);
  dist[source] = 0;
  priority_queue<pll, vpll, greater<pll>> pq;
  pq.push({0, source});
  while (!pq.empty()) {
    auto [dis, node] = pq.top();
    pq.pop();
    for (auto it : g[node]) {
      if (dist[it] > dis + 1) {
        dist[it] = dis+1;
        pq.push({dis+1, it});
      }
    }
  }
}
pll dir[] = {{0,1}, {1,0}, {-1,0} , {0,-1}};
int DistanceSum(int N, int *X, int *Y) {
  n=N;
  map<pll,ll> id;
  g.resize(n);
  set<pll> s;
  dist.resize(n);
  loop(i,0,n) {
    id[{X[i], Y[i]}] =i;
    s.insert({X[i], Y[i]});
  }
  loop(i,0,n) {
    ll x =  X[i], y=Y[i];
    for (auto [a,b] : dir) {
      if (s.lower_bound({x+a, y+b})!= s.end()) {
        g[i].push_back(id[{x+a, y+b}]);
        g[id[{x+a, y+b}]].push_back(i);
      }
    }
  }

  loop(i,0,n) {
    di(i);
    for (auto it : dist) ans = (ans+it)%mod;
  }
  return ans;

}

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