| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 411789 |
2021-05-26T01:25:36 Z |
couplefire |
ČVENK (COI15_cvenk) |
C++17 |
|
1278 ms |
90720 KB |
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair <int , int>
#define X first
#define Y second
#define F first
#define S second
#define mp make_pair
#define all(v) v.begin(), v.end()
const int N = 30, M = 2e5 + 5;
int pw[N], x[M], y[M], cnt[M], sz[M], dw[M], up[M];
vector <pii> P, g[M];
map <pii, int> Label;
int Zone(pii p, int n) {
if (p.X >= pw[n-1]) return 2;
if (p.Y >= pw[n-1]) return 1;
return 0;
}
void dfs_order(vector <pii> &vec, int n = N) {
if (n == 0 || vec.size() == 0) return ;
vector <pii> v[3];
for (pii p : vec) {
int z = Zone(p, n);
if (z == 1) v[1].push_back({p.X, p.Y - pw[n-1]});
if (z == 2) v[2].push_back({p.X - pw[n-1], p.Y});
if (z == 0) v[0].push_back(p);
}
vec.clear();
dfs_order(v[0], n - 1), dfs_order(v[1], n - 1), dfs_order(v[2], n - 1);
int pnt = 0;
while (pnt < v[0].size() && v[0][pnt].X == 0) vec.push_back(v[0][pnt++]);
for (pii p : v[1]) vec.push_back({p.X, p.Y + pw[n-1]});
while (pnt < v[0].size()) vec.push_back(v[0][pnt++]);
for (pii p : v[2]) vec.push_back({p.X + pw[n-1], p.Y});
}
pii LCA(pii u, pii v, int n = N) {
if (n == 0) return {0, 0};
int zu = Zone(u, n), zv = Zone(v, n);
if (zu > zv) swap(u, v), swap(zu, zv);
if (zu == 1 && zv == 2) return {0, 0};
if (zu == 2 && zv == 2) {
pii A = LCA({u.X - pw[n-1], u.Y}, {v.X - pw[n-1], v.Y}, n - 1);
return {A.X + pw[n - 1], A.Y};
}
if (zu == 1 && zv == 1) {
pii A = LCA({u.X, u.Y - pw[n - 1]}, {v.X, v.Y - pw[n - 1]}, n - 1);
return {A.X, A.Y + pw[n - 1]};
}
if (zu == 0 && zv == 0) return LCA(u, v, n - 1);
if (zv == 2) return LCA(u, {pw[n - 1] - 1, 0});
if (zv == 1) return LCA(u, {0, pw[n - 1] - 1});
}
int DIS(pii u, pii v, int n = N) {
if (n == 0) return 0;
int zu = Zone(u, n), zv = Zone(v, n);
if (zu > zv) swap(u, v), swap(zu, zv);
if (zu == 1 && zv == 2) return u.X + u.Y + v.X + v.Y;
if (zu == 2 && zv == 2) return DIS({u.X - pw[n-1], u.Y}, {v.X - pw[n-1], v.Y}, n - 1);
if (zu == 1 && zv == 1) return DIS({u.X, u.Y - pw[n-1]}, {v.X, v.Y - pw[n-1]}, n - 1);
if (zu == 0 && zv == 0) return DIS(u, v, n - 1);
if (zv == 2) return DIS(u, {pw[n - 1] - 1, 0}) + v.X + v.Y - pw[n-1] + 1;
if (zv == 1) return DIS(u, {0, pw[n - 1] - 1}) + v.X + v.Y - pw[n-1] + 1;
}
void dfs_down(int v) {
sz[v] = cnt[v];
for (pii e : g[v]) dfs_down(e.F), dw[v] += e.S * sz[e.F] + dw[e.F], sz[v] += sz[e.F];
}
void dfs_up(int v, int p = -1, int w = 0) {
if (p != -1)
up[v] = dw[p] + up[p] + (sz[0] - sz[v]) * w - dw[v] - sz[v] * w;
for (pii e : g[v]) dfs_up(e.F, v, e.S);
}
int32_t main() {
for (int i = 0; i < N; i++) pw[i] = 1<<i;
int n; cin >> n, P.resize(n);
for (int i = 0; i < n; i++) {
cin >> x[i] >> y[i];
P[i].X = x[i], P[i].Y = y[i];
}
if (n == 2) return cout << DIS(P[0], P[1]) << "\n", 0;
dfs_order(P);
for (int i = 1; i < n; i++) P.push_back(LCA(P[i - 1], P[i]));
P.push_back(LCA(P[0], P[n - 1]));
dfs_order(P);
P.resize(unique(all(P)) - P.begin());
for (int i = 0; i < P.size(); i++) Label[P[i]] = i;
for (int i = 0; i < n; i++) cnt[Label[{x[i], y[i]}]]++;
vector <int> s;
s.push_back(0);
for (int v = 1; v < P.size(); v++) {
while (LCA(P[s.back()], P[v]) != P[s.back()]) s.pop_back();
g[s.back()].push_back(mp(v, DIS(P[s.back()], P[v])));
s.push_back(v);
}
dfs_down(0), dfs_up(0);
int ans = 1e18;
for (int i = 0; i < P.size(); i++) ans = min(ans, dw[i] + up[i]);
cout << ans << "\n";
}
Compilation message
cvenk.cpp: In function 'void dfs_order(std::vector<std::pair<long long int, long long int> >&, long long int)':
cvenk.cpp:34:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
34 | while (pnt < v[0].size() && v[0][pnt].X == 0) vec.push_back(v[0][pnt++]);
| ~~~~^~~~~~~~~~~~~
cvenk.cpp:36:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
36 | while (pnt < v[0].size()) vec.push_back(v[0][pnt++]);
| ~~~~^~~~~~~~~~~~~
cvenk.cpp: In function 'int32_t main()':
cvenk.cpp:91:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
91 | for (int i = 0; i < P.size(); i++) Label[P[i]] = i;
| ~~^~~~~~~~~~
cvenk.cpp:95:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
95 | for (int v = 1; v < P.size(); v++) {
| ~~^~~~~~~~~~
cvenk.cpp:102:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
102 | for (int i = 0; i < P.size(); i++) ans = min(ans, dw[i] + up[i]);
| ~~^~~~~~~~~~
cvenk.cpp: In function 'std::pair<long long int, long long int> LCA(std::pair<long long int, long long int>, std::pair<long long int, long long int>, long long int)':
cvenk.cpp:55:1: warning: control reaches end of non-void function [-Wreturn-type]
55 | }
| ^
cvenk.cpp: In function 'long long int DIS(std::pair<long long int, long long int>, std::pair<long long int, long long int>, long long int)':
cvenk.cpp:66:1: warning: control reaches end of non-void function [-Wreturn-type]
66 | }
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
4940 KB |
Output is correct |
| 2 |
Correct |
3 ms |
4940 KB |
Output is correct |
| 3 |
Correct |
3 ms |
4940 KB |
Output is correct |
| 4 |
Correct |
3 ms |
4940 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
5068 KB |
Output is correct |
| 2 |
Correct |
4 ms |
4940 KB |
Output is correct |
| 3 |
Correct |
4 ms |
4940 KB |
Output is correct |
| 4 |
Correct |
4 ms |
4940 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
242 ms |
85372 KB |
Output is correct |
| 2 |
Correct |
236 ms |
85920 KB |
Output is correct |
| 3 |
Correct |
212 ms |
88772 KB |
Output is correct |
| 4 |
Correct |
231 ms |
90720 KB |
Output is correct |
| 5 |
Correct |
212 ms |
88092 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1271 ms |
33316 KB |
Output is correct |
| 2 |
Correct |
1278 ms |
35112 KB |
Output is correct |
| 3 |
Correct |
669 ms |
32212 KB |
Output is correct |
| 4 |
Correct |
712 ms |
27816 KB |
Output is correct |
| 5 |
Correct |
726 ms |
27004 KB |
Output is correct |
