| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 50871 | Mamnoon_Siam | Ideal city (IOI12_city) | C++17 | 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.
//#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
using namespace std;
#define debug(s) cout<< #s <<" = "<< s <<endl
#define all(v) (v).begin(), (v).end()
#define KeepUnique(v) (v).erase( unique(all(v)), v.end() )
#define MEMSET(a,val) memset(a, val, sizeof a)
#define PB push_back
#define endl '\n'
typedef long long ll;
inline int myrand(int l, int r) {
int ret = rand(); ret <<= 15; ret ^= rand();
if(ret < 0) ret = -ret; ret %= (r-l+1); ret += l;
return ret;
}
template <typename F, typename S>
ostream& operator << (ostream& os, const pair< F, S>& p) {
return os<<"(" <<p.first<<", "<<p.second<<")"; }
typedef pair<int, int> ii;
template<typename T> using min_pq =
priority_queue<T, vector<T>, greater<T> >;
int udx[] = {-1, +0, +1, +0};
int udy[] = {+0, +1, +0, -1};
const int mod = 1e9;
struct point {
int x, y;
point() {x = y = 0;}
point(int x, int y) {
this -> x = x;
this -> y = y;
}
bool operator < (const point &tmp) const {
return x < tmp.x or (x == tmp.x and y < tmp.y);
}
};
bool cmpx(point p, point q) {
return (p.x < q.x) or (p.x == q.x and p.y < q.y);
}
bool cmpy(point p, point q) {
return (p.y < q.y) or (p.y == q.y and p.x < q.x);
}
struct TreeBuilder {
vector<point> nodes;
vector<int> dx, dy;
map<point, int> idx;
vector<bool>vis;
vector<int>comp;
int comp_cnt;
TreeBuilder() {}
void build(vector<point>&vec, vector<int>Dx, vector<int>Dy, vector<ii>&edges, vector<int>&w) {
dx = Dx, dy = Dy, nodes = vec;
sort(all(nodes));
vis.resize(nodes.size()); fill(all(vis), 0);
comp.resize(nodes.size()); fill(all(comp), 0);
idx.clear();
for(int i = 0; i < nodes.size(); i++)
idx[nodes[i]] = i;
comp_cnt = 0;
for(int i = 0; i < nodes.size(); i++) {
if(!vis[i]) {
dfs(i);
comp_cnt++;
}
}
for(int i = 0; i < nodes.size(); i++) {
for(int j = 0; j < 4; j++) {
int xx = nodes[i].x + udx[j];
int yy = nodes[i].y + udy[j];
if(binary_search(all(nodes), point(xx, yy))) {
int u = i, v = idx[point(xx, yy)];
u = comp[u], v = comp[v];
if(u != v) {
if(u > v) swap(u, v);
edges.push_back(ii(u, v));
}
}
}
}
sort(all(edges));
KeepUnique(edges);
w.resize(comp_cnt); fill(all(w), 0);
for(int i = 0; i < nodes.size(); i++) {
w[comp[i]]++;
}
}
void dfs(int u) {
vis[u] = 1;
comp[u] = comp_cnt;
for(int i = 0; i < 2; i++) {
int xx = nodes[u].x + dx[i];
int yy = nodes[u].y + dy[i];
if(binary_search(all(nodes), point(xx, yy))) {
int v = idx[point(xx, yy)];
if(!vis[v]) {
dfs(v);
}
}
}
}
}TB;
ll f(ll x) { // f(x) = \sum_{i = 1}^{x} i * (x - i + 1) = x * (x + 1) * (x + 2) / 6
ll F = x, A = x + 1, P = x + 2;
if(F % 2 == 0) F /= 2;
else if(A % 2 == 0) A /= 2;
else if(P % 2 == 0) P /= 2;
if(F % 3 == 0) F /= 3;
else if(A % 3 == 0) A /= 3;
else if(P % 3 == 0) P /= 3;
ll ret = (F * A) % mod;
ret = (ret * P) % mod;
return ret;
}
int n;
vector<point> pts;
vector<ii> edges;
vector<int> w, g[200010];
ll ans = 0;
int dfs(int u, int p) {
int sz = w[u];
for(int v : g[u]) {
if(p - v) {
sz += dfs(v, u);
}
}
ans = (ans + ((1LL * sz * (n - sz)) % mod)) % mod;
return sz;
}
int32_t main () {
cin >> n;
pts.resize(n);
for(point &p : pts)
cin >> p.x >> p.y;
edges.clear();
w.clear();
for(int i = 0; i < n; i++)
g[i].clear();
TB.build(pts, {-1, +1}, {0, 0}, edges, w);
for(ii &b : edges) {
int x = b.first, y = b.second;
g[x].push_back(y);
g[y].push_back(x);
//cout << w[b.first] << ' ' << w[b.second] << endl;
}
//for(int x : w) ans = (ans + f(x-1)) % mod;
dfs(0, -1);
//cout << "----------------------" << endl;
edges.clear();
w.clear();
for(int i = 0; i < n; i++)
g[i].clear();
TB.build(pts, {0, 0}, {-1, +1}, edges, w);
for(ii &b : edges) {
int x = b.first, y = b.second;
g[x].push_back(y);
g[y].push_back(x);
//cout << w[b.first] << ' ' << w[b.second] << endl;
}
//for(int x : w) ans = (ans + f(x-1)) % mod;
dfs(0, -1);
cout << ans << endl;
}
int DistanceSum(int N, int *X, int *Y) {
n = N;
pts.resize(n);
for(int i = 0; i < n; i++) {
p[i].x = X[i], p[i].y = Y[i];
}
edges.clear();
w.clear();
for(int i = 0; i < n; i++)
g[i].clear();
TB.build(pts, {-1, +1}, {0, 0}, edges, w);
for(ii &b : edges) {
int x = b.first, y = b.second;
g[x].push_back(y);
g[y].push_back(x);
//cout << w[b.first] << ' ' << w[b.second] << endl;
}
//for(int x : w) ans = (ans + f(x-1)) % mod;
dfs(0, -1);
//cout << "----------------------" << endl;
edges.clear();
w.clear();
for(int i = 0; i < n; i++)
g[i].clear();
TB.build(pts, {0, 0}, {-1, +1}, edges, w);
for(ii &b : edges) {
int x = b.first, y = b.second;
g[x].push_back(y);
g[y].push_back(x);
//cout << w[b.first] << ' ' << w[b.second] << endl;
}
//for(int x : w) ans = (ans + f(x-1)) % mod;
dfs(0, -1);
return (int)ans;
}