제출 #1195066

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1195066		madamadam3	이상적인 도시 (IOI12_city)	C++20	32 / 100	97 ms	3396 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 << " ";
#define all(x) (x).begin(), (x).end()

using vi = vector<int>;

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

int n;
vector<int> x, y;
map<pair<int, int>, int> nmap;
map<int, 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 into 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(int u, int p, int tlcmps, vector<set<int>> &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(int u, int p, int tlcmps, vector<set<int>> &adj, vi &weights, vi &DP, vi &DP2, vi &sz) {
  if (u != p) {
    int pc = DP2[p] - DP[u] - sz[u];
    int 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(int u, int p, int tlcmps, int &total, vector<set<int>> &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]);
}

int solveOrientation() {
  int ans = 0;

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

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

    int 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<int, int>> edges;
  for (int i = 0; i < n; i++) {
    vector<pair<int, int>> 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;
      int a = nodeblock[i];
      int 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});
    }
  }

  int tlcmps = curcmp + 1;
  vector<set<int>> nadj(tlcmps, set<int>());
  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);
  int total = 0;
  dfs(0, 0, tlcmps, total, nadj, sz, weights);
  ans = total;
  return ans;
}



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

  n = _N;
  x.resize(0); y.resize(0);
  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;
    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: 0 / 23
• Subtask 4: 0 / 45