제출 #440005

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
440005		prvocislo	Ideal city (IOI12_city)	C++17	100 / 100	173 ms	16636 KiB

city

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

const int mod = 1e9, maxn = 1e5 + 5;
void upd(int &a, const int &b) { a = (a + b) % mod; }
int add(const int &a, const int &b) { return (a + b) % mod; }
int mul(const int &a, const int &b) { return (a * 1ll * b) % (ll)mod; }
vector<int> g[maxn];
int sz[maxn];
struct bod { int x, y; };
bool cmp(const bod &a, const bod &b) { return (a.x == b.x) ? a.y < b.y : a.x < b.x; }
int ans = 0, n;
void dfs(int u, int p = -1)
{
  for (int v : g[u]) if (v != p) dfs(v, u), sz[u] += sz[v];
  upd(ans, mul(sz[u], n - sz[u]));
}
void calculate_x_dist(vector<bod> v)
{
  for (int i = 0; i < n; i++) g[i].clear(), sz[i] = 0;
  map<pair<int, int>, int> m;
  set<pair<int, int> > e;
  sort(v.begin(), v.end(), cmp);
  int cnt = 0;
  for (int i = 0; i < n; i++)
  {
    if (i && (v[i-1].x != v[i].x || v[i-1].y+1 != v[i].y)) cnt++;
    m[{v[i].x, v[i].y}] = cnt;
    sz[cnt]++;
    if (m.count({v[i].x-1, v[i].y})) e.insert({m[{v[i].x-1, v[i].y}], cnt});
  }
  for (pair<int, int> i : e) g[i.first].push_back(i.second), g[i.second].push_back(i.first);
  dfs(0);
}
int DistanceSum(int N, int *x, int *y) 
{
  n = N; vector<bod> v;
  for (int i = 0; i < n; i++) v.push_back({x[i], y[i]}); 
  calculate_x_dist(v);
  for (int i = 0; i < n; i++) swap(v[i].x, v[i].y);
  calculate_x_dist(v);
  return ans;
}

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