제출 #1195069

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1195069		madamadam3	Ideal city (IOI12_city)	C++20	100 / 100	753 ms	37608 KiB

city

#include <bits/stdc++.h>

using namespace std;

#define FOR(i, a, b) for (ll i = a; i < b; i++)
#define pb push_back
#define trace(x) for (auto &a : x) cout << a << " ";
#define all(x) (x).begin(), (x).end()

typedef long long ll;
using vi = vector<ll>;

const ll MOD = 1'000'000'000;

ll n;
vector<ll> x, y;
map<pair<ll, ll>, ll> nmap;
map<ll, vi> xmap;

/*
  Stages (repeat for y): 
  (1) make rep nodes
    for each column, go down from highest node on x to lowest node x
    merge adjacent cells llo one node (store size of component)
    continue
  (2) go through each column, join adjacent representatives with an edge
  (3) take the tree structure, do dp to find number of paths going through each edge (= sum(|xi-xj| over all ij))
  (4) 
*/

void dfs_dp(ll u, ll p, ll tlcmps, vector<set<ll>> &adj, vi &weights, vi &DP, vi &sz) {
  // cout << "Did I segfdault at u = " << u << " p = " << p << "?\n";
  DP[u] = 0;
  sz[u] = weights[u];

  for (auto &v : adj[u]) {
    // cout << "U = " << u << " V = " << v << " P = " << p << "\n";
    if (v == p) continue;
    // cout << "We are searching " << v << "\n";
    dfs_dp(v, u, tlcmps, adj, weights, DP, sz);
    DP[u] += DP[v] + sz[v];
    sz[u] += sz[v];
  }
}

void dfs_dp2(ll u, ll p, ll tlcmps, vector<set<ll>> &adj, vi &weights, vi &DP, vi &DP2, vi &sz) {
  if (u != p) {
    ll pc = DP2[p] - DP[u] - sz[u];
    ll psz = sz[p] - sz[u];
    DP2[u] = DP[u] + pc + psz;
  }

  for (auto &v : adj[u]) {
    if (v == p) continue;
    dfs_dp2(v, u, tlcmps, adj, weights, DP, DP2, sz);
  }
}

void dfs(ll u, ll p, ll tlcmps, ll &total, vector<set<ll>> &adj, vi &sz, vi &weights) {
  sz[u] = weights[u];

  for (auto v : adj[u]) {
    if (v == p) continue;
    dfs(v, u, tlcmps, total, adj, sz, weights);
    sz[u] += sz[v];
  }

  total += sz[u] * (n - sz[u]);
  total %= MOD;
}

ll solveOrientation() {
  ll ans = 0;

  map<ll, vi> colblocks;
  map<ll, vi> blocks;
  map<ll, ll> nodeblock;

  ll curcmp = -1;
  for (auto &el : xmap) {
    sort(all(el.second), [&](ll a, ll b) {return y[a] < y[b];});

    ll prevy = -10;
    for (auto &node : el.second) {
      if (y[node] > prevy + 1 || prevy == -10) {
        curcmp++;
        colblocks[el.first].pb(curcmp);
      }
      blocks[curcmp].pb(node);
      nodeblock[node] = curcmp;
      prevy = y[node];
    }
  }

  set<pair<ll, ll>> edges;
  for (ll i = 0; i < n; i++) {
    vector<pair<ll, ll>> d = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
    for (auto v : d) {
      if (!nmap.count({x[i] + v.first, y[i] + v.second})) continue;
      ll a = nodeblock[i];
      ll b = nodeblock[nmap[{x[i] + v.first, y[i] + v.second}]];
      if (a == b) continue;
      if (a > b) swap(a, b);
      edges.insert({a, b});
    }
  }

  ll tlcmps = curcmp + 1;
  vector<set<ll>> nadj(tlcmps, set<ll>());
  for (auto edge : edges) {
    nadj[edge.first].insert(edge.second);
    nadj[edge.second].insert(edge.first);
  }

  vi weights(tlcmps);
  FOR(i, 0, tlcmps) weights[i] = blocks[i].size();

  vi DP(tlcmps, 0), sz(tlcmps, 0), DP2(tlcmps, 0);
  // dfs_dp(0, 0, tlcmps, nadj, weights, DP, sz);
  // DP2[0] = DP[0];
  // dfs_dp2(0, 0, tlcmps, nadj, weights, DP, DP2, sz);

  // ans = accumulate(all(DP2), 0);
  ll total = 0;
  dfs(0, 0, tlcmps, total, nadj, sz, weights);
  ans = total;
  return ans;
}

int DistanceSum(int _N, int *_X, int *_Y) {
  ll ans = 0;

  n = _N;
  x.resize(0); y.resize(0);
  for (ll i = 0; i < n; i++) x.pb(_X[i]), y.pb(_Y[i]); 

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

  ans += solveOrientation();
  ans %= MOD;

  nmap.clear();
  xmap.clear();

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

  ans += solveOrientation();
  ans %= MOD;

  n = 0;
  x.clear();
  y.clear();
  return ans % MOD;
}

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