| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 480350 |
2021-10-15T17:57:56 Z |
blue |
Ideal city (IOI12_city) |
C++17 |
|
349 ms |
61632 KB |
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <queue>
#include <map>
using namespace std;
int N;
vector<int> X, Y;
const int MX = 100'000;
const int INF = 1'000'000'000;
struct point
{
int x;
int y;
int i;
int rightNodes;
int downNodes;
};
bool operator < (point A, point B)
{
if(A.x != B.x) return A.x < B.x;
return A.y < B.y;
}
set<point> P;
int getIndex(int x, int y)
{
set<point>::iterator f = P.find(point{x, y, -1, -1, -1});
if(f == P.end()) return -1;
else return f->i;
}
long long new_ans = 0;
vector<int> up_edge[1+MX];
vector<int> down_edge[1+MX];
vector<int> Y_index_size(1+MX);
vector<int> Y_index_coord(1+MX);
int Y_max_index;
vector<int> Y_parent(1+MX);
vector<int> Y_subtree_sum(1+MX);
vector<int> point_Y_line(1+MX);
void Y_dfs(int u, int p)
{
// cerr << "Y dfs " << u << ' ' << p << '\n';
Y_subtree_sum[u] = Y_index_size[u];
for(int v: up_edge[u])
{
if(v == p) continue;
Y_parent[v] = u;
Y_dfs(v, u);
Y_subtree_sum[u] += Y_subtree_sum[v];
}
for(int v: down_edge[u])
{
if(v == p) continue;
Y_parent[v] = u;
Y_dfs(v, u);
Y_subtree_sum[u] += Y_subtree_sum[v];
}
}
vector<int> left_edge[1+MX];
vector<int> right_edge[1+MX];
vector<int> X_index_size(1+MX);
vector<int> X_index_coord(1+MX);
int X_max_index;
vector<int> X_parent(1+MX);
vector<int> X_subtree_sum(1+MX);
vector<int> point_X_line(1+MX);
void X_dfs(int u, int p)
{
X_subtree_sum[u] = X_index_size[u];
for(int v: left_edge[u])
{
if(v == p) continue;
X_parent[v] = u;
X_dfs(v, u);
X_subtree_sum[u] += X_subtree_sum[v];
}
for(int v: right_edge[u])
{
if(v == p) continue;
X_parent[v] = u;
X_dfs(v, u);
X_subtree_sum[u] += X_subtree_sum[v];
}
}
long long init_dist = 0;
vector<int> dx{0, 0, +1, -1};
vector<int> dy{+1, -1, 0, 0};
long long final_ans = 0;
vector<bool> visit(MX, 0);
map<pair<int, int>, long long> X_delta, Y_delta; //adjust value when going from u to v.
void dfs(int u)
{
for(int z = 0; z < 4; z++)
{
int v = getIndex(X[u] + dx[z], Y[u] + dy[z]);
if(v == -1) continue;
if(visit[v]) continue;
visit[v] = 1;
long long adjust_val;
if(X[u] == X[v])
{
adjust_val = X_delta[ make_pair(point_X_line[u], point_X_line[v]) ];
}
else
{
// cerr << "! \n";
// cerr << point_Y_line[u] << ' ' << point_Y_line[v] << ' ' << Y_delta[ make_pair(point_Y_line[u], point_Y_line[v]) ] <<'\n';
adjust_val = Y_delta[ make_pair(point_Y_line[u], point_Y_line[v]) ];
}
init_dist += (N - adjust_val) - adjust_val;
final_ans += init_dist;
dfs(v);
init_dist -= (N - adjust_val) - adjust_val;
}
}
int DistanceSum(int N_, int *X_, int *Y_)
{
//PART 1: Normalize
// cerr << "check\n";
N = N_;
X = vector<int>(N);
Y = vector<int>(N);
for(int i = 0; i < N; i++)
{
X[i] = X_[i];
Y[i] = Y_[i];
}
int Xmin = X[0], Ymin = Y[0];
for(int i = 1; i < N; i++)
{
Xmin = min(Xmin, X[i]);
Ymin = min(Ymin, Y[i]);
}
for(int i = 0; i < N; i++)
{
X[i] = X[i] - Xmin + 1;
Y[i] = Y[i] - Ymin + 1; //CORRECT THIS!!!!!!
// cerr << X[i] << ' ' << Y[i] << '\n';
}
for(int i = 0; i < N; i++)
{
P.insert(point{X[i], Y[i], i, -1, -1});
}
vector<int> Ylist[1+MX];
for(int i = 0; i < N; i++)
{
Ylist[ X[i] ].push_back(Y[i]);
}
for(int x = 1; x <= MX; x++)
sort(Ylist[x].begin(), Ylist[x].end());
//
//
int curr_Y_index = 0;
vector<int> Y_begin[1+MX], Y_end[1+MX];
vector<int>* Y_index = new vector<int>[1+MX]; //FIGURE OUT WHY THIS WENT WRONG
// vector<int> Y_index[1+MX];
for(int x = 1; x <= MX; x++)
{
if(Ylist[x].empty()) continue;
Y_begin[x].push_back(Ylist[x][0]);
curr_Y_index++;
Y_index[x].push_back(curr_Y_index);
for(int i = 1; i < (int)Ylist[x].size(); i++)
{
if(Ylist[x][i-1] + 1 != Ylist[x][i])
{
Y_end[x].push_back(Ylist[x][i-1]);
Y_begin[x].push_back(Ylist[x][i]);
curr_Y_index++;
Y_index[x].push_back(curr_Y_index);
}
}
Y_end[x].push_back(Ylist[x].back());
// cerr << "x = " << x << '\n';
for(int v = 0; v < (int)Y_begin[x].size(); v++)
{
Y_index_size[ Y_index[x][v] ] = Y_end[x][v] - Y_begin[x][v] + 1;
Y_index_coord[ Y_index[x][v] ] = x;
for(int y = Y_begin[x][v]; y <= Y_end[x][v]; y++)
point_Y_line[ getIndex(x, y) ] = Y_index[x][v];
}
}
for(int x = 1; x+1 <= MX; x++)
{
if(Y_index[x].empty() || Y_index[x+1].empty()) continue;
int q = 0;
for(int p = 0; p < (int)Y_index[x].size(); p++)
{
if(max(Y_begin[x][p], Y_begin[x+1][q]) <= min(Y_end[x][p], Y_end[x+1][q]))
{
down_edge[Y_index[x][p]].push_back(Y_index[x+1][q]);
up_edge[Y_index[x+1][q]].push_back(Y_index[x][p]);
}
while(q+1 < (int)Y_begin[x+1].size() && Y_begin[x+1][q+1] <= Y_end[x][p])
{
q++;
if(max(Y_begin[x][p], Y_begin[x+1][q]) <= min(Y_end[x][p], Y_end[x+1][q]))
{
down_edge[Y_index[x][p]].push_back(Y_index[x+1][q]);
up_edge[Y_index[x+1][q]].push_back(Y_index[x][p]);
}
}
}
}
Y_max_index = curr_Y_index;
Y_parent[1] = 0;
Y_dfs(1, 1);
for(int u = 1; u <= Y_max_index; u++)
{
for(int v: down_edge[u])
{
if(v == Y_parent[u])
{
Y_delta[ make_pair(u, v) ] = (N - Y_subtree_sum[u]);
Y_delta[ make_pair(v, u) ] = Y_subtree_sum[u];
new_ans += (long long)Y_subtree_sum[u] * (long long)(N - Y_subtree_sum[u]);
}
else
{
Y_delta[ make_pair(u, v) ] = Y_subtree_sum[v];
Y_delta[ make_pair(v, u) ] = (N - Y_subtree_sum[v]);
new_ans += (long long)Y_subtree_sum[v] * (long long)(N - Y_subtree_sum[v]);
}
}
}
vector<int>* Xlist = new vector<int>[1+MX];
for(int i = 0; i < N; i++)
{
Xlist[ Y[i] ].push_back(X[i]);
}
for(int y = 1; y <= MX; y++)
sort(Xlist[y].begin(), Xlist[y].end());
int curr_X_index = 0;
vector<int>* X_begin = new vector<int>[1+MX];
vector<int>* X_end = new vector<int>[1+MX];
vector<int>* X_index = new vector<int>[1+MX]; //FIGURE OUT WHY THIS WENT WRONG
for(int y = 1; y <= MX; y++)
{
if(Xlist[y].empty()) continue;
X_begin[y].push_back(Xlist[y][0]);
curr_X_index++;
X_index[y].push_back(curr_X_index);
for(int i = 1; i < (int)Xlist[y].size(); i++)
{
if(Xlist[y][i-1] + 1 != Xlist[y][i])
{
X_end[y].push_back(Xlist[y][i-1]);
X_begin[y].push_back(Xlist[y][i]);
curr_X_index++;
X_index[y].push_back(curr_X_index);
}
}
X_end[y].push_back(Xlist[y].back());
for(int v = 0; v < (int)X_begin[y].size(); v++)
{
X_index_size[ X_index[y][v] ] = X_end[y][v] - X_begin[y][v] + 1;
X_index_coord[ X_index[y][v] ] = y;
for(int x = X_begin[y][v]; x <= X_end[y][v]; x++)
{
point_X_line[ getIndex(x, y) ] = X_index[y][v];
}
}
}
for(int y = 1; y+1 <= MX; y++)
{
if(X_index[y].empty() || X_index[y+1].empty()) continue;
int q = 0;
for(int p = 0; p < (int)X_index[y].size(); p++)
{
if(max(X_begin[y][p], X_begin[y+1][q]) <= min(X_end[y][p], X_end[y+1][q]))
{
right_edge[X_index[y][p]].push_back(X_index[y+1][q]);
left_edge[X_index[y+1][q]].push_back(X_index[y][p]);
}
while(q+1 < (int)X_begin[y+1].size() && X_begin[y+1][q+1] <= X_end[y][p])
{
q++;
if(max(X_begin[y][p], X_begin[y+1][q]) <= min(X_end[y][p], X_end[y+1][q]))
{
right_edge[X_index[y][p]].push_back(X_index[y+1][q]);
left_edge[X_index[y+1][q]].push_back(X_index[y][p]);
}
}
}
}
X_max_index = curr_X_index;
X_parent[1] = 0;
X_dfs(1, 1);
for(int u = 1; u <= X_max_index; u++)
{
for(int v: right_edge[u])
{
if(v == X_parent[u])
{
X_delta[ make_pair(u, v) ] = N - X_subtree_sum[u];
X_delta[ make_pair(v, u) ] = N - (N - X_subtree_sum[u]);
new_ans += (long long)X_subtree_sum[u] * (long long)(N - X_subtree_sum[u]);
}
else
{
X_delta[ make_pair(u, v) ] = X_subtree_sum[v];
X_delta[ make_pair(v, u) ] = (N - X_subtree_sum[v]);
new_ans += (long long)X_subtree_sum[v] * (long long)(N - X_subtree_sum[v]);
}
}
}
vector<int> dist0(N, INF);
dist0[0] = 0;
queue<int> tbv;
tbv.push(0);
while(!tbv.empty())
{
int u = tbv.front();
tbv.pop();
for(int z = 0; z < 4; z++)
{
int v = getIndex(X[u] + dx[z], Y[u] + dy[z]);
if(v == -1) continue;
if(dist0[v] <= dist0[u] + 1) continue;
dist0[v] = dist0[u] + 1;
tbv.push(v);
}
}
for(int i = 0; i < N; i++)
{
init_dist += dist0[i];
}
final_ans = init_dist;
visit[0] = 1;
dfs(0);
final_ans = final_ans/2;
return int(new_ans % 1'000'000'000LL);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
32348 KB |
Output is correct |
| 2 |
Correct |
22 ms |
32328 KB |
Output is correct |
| 3 |
Correct |
22 ms |
32324 KB |
Output is correct |
| 4 |
Correct |
24 ms |
32332 KB |
Output is correct |
| 5 |
Correct |
22 ms |
32336 KB |
Output is correct |
| 6 |
Correct |
22 ms |
32396 KB |
Output is correct |
| 7 |
Correct |
23 ms |
32388 KB |
Output is correct |
| 8 |
Correct |
22 ms |
32460 KB |
Output is correct |
| 9 |
Correct |
23 ms |
32464 KB |
Output is correct |
| 10 |
Correct |
23 ms |
32460 KB |
Output is correct |
| 11 |
Correct |
24 ms |
32392 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
25 ms |
32656 KB |
Output is correct |
| 2 |
Correct |
25 ms |
32652 KB |
Output is correct |
| 3 |
Correct |
26 ms |
32832 KB |
Output is correct |
| 4 |
Correct |
23 ms |
32740 KB |
Output is correct |
| 5 |
Correct |
25 ms |
32916 KB |
Output is correct |
| 6 |
Correct |
25 ms |
32804 KB |
Output is correct |
| 7 |
Correct |
26 ms |
32936 KB |
Output is correct |
| 8 |
Correct |
27 ms |
32784 KB |
Output is correct |
| 9 |
Correct |
26 ms |
32708 KB |
Output is correct |
| 10 |
Correct |
25 ms |
32696 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
56 ms |
36548 KB |
Output is correct |
| 2 |
Correct |
55 ms |
36588 KB |
Output is correct |
| 3 |
Correct |
115 ms |
41408 KB |
Output is correct |
| 4 |
Correct |
113 ms |
41124 KB |
Output is correct |
| 5 |
Correct |
244 ms |
50296 KB |
Output is correct |
| 6 |
Correct |
249 ms |
49732 KB |
Output is correct |
| 7 |
Correct |
240 ms |
51012 KB |
Output is correct |
| 8 |
Correct |
243 ms |
51160 KB |
Output is correct |
| 9 |
Correct |
237 ms |
52420 KB |
Output is correct |
| 10 |
Correct |
269 ms |
61632 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
71 ms |
37776 KB |
Output is correct |
| 2 |
Correct |
64 ms |
37060 KB |
Output is correct |
| 3 |
Correct |
156 ms |
45560 KB |
Output is correct |
| 4 |
Correct |
135 ms |
43248 KB |
Output is correct |
| 5 |
Correct |
329 ms |
58436 KB |
Output is correct |
| 6 |
Correct |
271 ms |
51188 KB |
Output is correct |
| 7 |
Correct |
349 ms |
59040 KB |
Output is correct |
| 8 |
Correct |
288 ms |
50496 KB |
Output is correct |
| 9 |
Correct |
300 ms |
48220 KB |
Output is correct |
| 10 |
Correct |
261 ms |
47796 KB |
Output is correct |
