# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
725081 | stevancv | Ideal city (IOI12_city) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#include "city.h"
#define ll long long
#define ld long double
#define sp ' '
#define en '\n'
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
using namespace std;
const int N = 1e5 + 2;
const int inf = 1e9;
vector<int> g[N];
ll sz[N], ans;
void Dfs(int s, int e, int n) {
for (int u : g[s]) {
if (u == e) continue;
Dfs(u, s, n);
sz[s] += sz[u];
}
for (int u : g[s]) {
if (u == e) continue;
ans += sz[u] * (n - sz[u]);
}
}
int Resi(int n, int x[], int y[]) {
map<int, vector<int>> mp;
map<pair<int, int>, int> id;
for (int i = 0; i < n; i++) mp[x[i]].push_back(y[i]);
for (int i = 0; i < n; i++) {
g[i].clear();
sz[i] = 0;
}
int tsz = 0;
for (auto z : mp) {
int ii = z.first;
auto v = z.second;
sort(v.begin(), v.end());
int c = 0;
for (int i = 0; i < v.size(); i++) {
if (i == 0 || v[i - 1] + 1 == v[i]) c++;
else {
sz[tsz++] = c;
c = 1;
}
id[{ii, v[i]}] = tsz;
}
sz[tsz++] = c;
for (int i = 0; i < v.size(); i++) {
if (id.find({ii - 1, v[i]}) != id.end()) {
int o = id[{ii - 1, v[i]}];
int oo = id[{ii, v[i]}];
g[o].push_back(oo);
g[oo].push_back(o);
}
}
}
for (int i = 0; i < tsz; i++) {
sort(g[i].begin(), g[i].end());
g[i].erase(unique(g[i].begin(), g[i].end()), g[i].end());
}
ans = 0;
Dfs(0, -1, n);
ans %= inf;
return ans;
}
int DistanceSum(int n, int x[], int y[]) {return (Resi(n, x, y) + Resi(n, y, x)) % inf;}