Submission #371534

#	Time	Username	Problem	Language	Result	Execution time	Memory
371534		WLZ	Ideal city (IOI12_city)	C++14	100 / 100	87 ms	11844 KiB

city

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

const int MOD = (int) 1e9;

int add(int a, int b) {
  if (a + b >= MOD) return a + b - MOD;
  return a + b;
}

int mul(int a, int b) {
  return (long long) a * b % MOD;
}

void dfs(int u, const vector< vector<int> > &g, vector<int> &p, vector<int> &cnt) {
  for (auto& v : g[u]) {
    if (v != p[u]) {
      p[v] = u;
      dfs(v, g, p, cnt);
      cnt[u] += cnt[v];
    }
  }
}

int solve(vector< pair<int, int> > v) {
  int n = (int) v.size();
  sort(v.begin(), v.end());
  vector<int> group(n), cnt(n, 0);
  cnt[0] = 1;
  group[0] = 0;
  for (int i = 1; i < n; i++) {
    group[i] = group[i - 1];
    if (v[i].first != v[i - 1].first || v[i].second != v[i - 1].second + 1) group[i]++;
    cnt[group[i]]++;
  }
  map<int, vector<int> > mp;
  for (int i = 0; i < n; i++) mp[v[i].second].push_back(i);  
  vector< pair<int, int> > edges;
  for (auto& p : mp) {
    for (int i = 1; i < (int) p.second.size(); i++) {
      if (v[p.second[i]].first == v[p.second[i - 1]].first + 1) edges.push_back({group[p.second[i - 1]], group[p.second[i]]});
    }
  }
  sort(edges.begin(), edges.end());
  edges.erase(unique(edges.begin(), edges.end()), edges.end());
  vector< vector<int> > g(group[n - 1] + 1);
  for (auto& e : edges) {
    g[e.first].push_back(e.second);
    g[e.second].push_back(e.first);
  }
  vector<int> p((int) g.size(), -1);
  dfs(0, g, p, cnt);
  int ans = 0;
  for (int i = 1; i <= group[n - 1]; i++) {
    ans = add(ans, mul(cnt[i], n - cnt[i]));
  }
  return ans;
}

int DistanceSum(int N, int *X, int *Y) {
  vector< pair<int, int> > vertical, horizontal;
  for (int i = 0; i < N; i++) {
    horizontal.push_back({X[i], Y[i]});
    vertical.push_back({Y[i], X[i]});
  }
  return add(solve(horizontal), solve(vertical));
}

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