| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 630878 | sonamoo | 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>
#define FastIO ios_base::sync_with_stdio(false); cin.tie(NULL);
#define pii pair<int,int>
#define mod 1000000000
#define SIZE 100005
using namespace std;
int n;
vector<pii> cell , cell2;
long long int arr[SIZE] , sz[SIZE] , dp[SIZE] , pr[SIZE];
vector<int> graph[SIZE];
long long int ans;
long long int SUM;
bool cmp(pii A , pii B) {
if (A.second == B.second) return A.first < B.first;
return A.second < B.second;
}
void init() {
memset(arr , 0 , sizeof(arr));
memset(dp , 0 , sizeof(dp));
memset(sz , 0 , sizeof(sz));
for (int i = 0; i < SIZE; i++) graph[i].clear();
SUM = 0;
}
void make_tree(int here) {
for (auto there : graph[here]) {
if (pr[there] == -1) {
pr[there] = here;
make_tree(there);
}
}
}
void solve(int here) {
long long int res = 0;
sz[here] = arr[here];
for (auto there : graph[here]) {
if (there == pr[here]) continue;
solve(there);
sz[here] += sz[there];
}
ans += sz[here]*(SUM-sz[here]);
ans %= mod;
}
void make_graph() {
sort(cell.begin() , cell.end() , cmp);
// cout << "=======\n";
for (auto t : cell) {
//cout << t.first << " " << t.second << "\n";
}
long long int s = cell[0].first;
long long int e = cell[0].first;
int siz = 0;
vector<pair<int, pii> > tmp;
vector<int> yidx;
for (int i = 0; i < cell.size()-1; i++) {
if (cell[i].second == cell[i+1].second && cell[i+1].first-cell[i].first == 1) e++;
else {
tmp.push_back({cell[i].second , {s , e}});
arr[siz++] = e-s+1;
yidx.push_back(cell[i].second);
s = cell[i+1].first;
e = cell[i+1].first;
}
}
tmp.push_back({cell[cell.size()-1].second , {s , e}});
arr[siz++] = e-s+1;
yidx.push_back(cell[cell.size()-1].second);
for (int i = 0; i < siz; i++) SUM += arr[i];
//printf("ok1\n");
sort(tmp.begin() , tmp.end());
sort(yidx.begin() , yidx.end());
yidx.push_back(1e18);
for (int i = 0; i < tmp.size(); i++) {
auto t = tmp[i];
// cout << t.first << " " << t.second.first << " " << t.second.second << " : ";
// cout << arr[i] << "\n";
}
for (int idx = 0; idx < tmp.size(); idx++) {
int y = tmp[idx].first;
int s = tmp[idx].second.first;
int e = tmp[idx].second.second;
int idx1 = lower_bound(yidx.begin() , yidx.end() , y+1)-yidx.begin();
int idx2 = upper_bound(yidx.begin() , yidx.end() , y+1)-yidx.begin();
idx2--;
if (idx1 == yidx.size()-1) continue;
int l = idx1;
int r = idx2;
// printf("ok1\n");
while(l < r) {
int mid = (l+r)/2;
if (tmp[mid].second.second >= s) r = mid;
else l = mid+1;
}
//printf("ok2\n");
int lo = l;
l = idx1;
r = idx2;
while(l < r) {
int mid = (l+r+1)/2;
//printf("%d %d %d\n" , l , r , mid);
if (tmp[mid].second.first <= e) l = mid;
else r = mid-1;
}
// printf("ok3\n");
int hi = l;
for (int i = lo; i <= hi; i++) {
graph[idx].push_back(i);
graph[i].push_back(idx);
//cout << idx << " " << i << "\n";
}
}
memset(pr , -1 , sizeof(pr));
pr[0] = 0;
make_tree(0);
}
int DistanceSum(int N , int *X , int *Y) {
n = N;
for (int i = 0; i < n; i++) {
cell.push_back({x[i] , y[i]});
cell2.push_back({y[i] , x[i]});
}
make_graph();
solve(0);
ans %= mod;
init();
for (int i = 0; i < cell.size(); i++) cell[i] = cell2[i];
make_graph();
solve(0);
ans %= mod;
return ans;
}