# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
464121 |
2021-08-12T12:06:03 Z |
fskarica |
ČVENK (COI15_cvenk) |
C++14 |
|
520 ms |
18820 KB |
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define fi first
#define se second
#define pii pair<ll, ll>
const ll MAX = 2e5 + 10;
ll n;
ll x, y;
ll id;
ll sol;
ll head;
ll black[MAX];
ll parent[MAX];
vector <pii> v;
vector <ll> veze[MAX];
pii movek(ll x, ll y, ll k) {
while (k) {
if (x == 0) {
y = max(0ll, y - k);
break;
}
if (y == 0) {
x = max(0ll, x - k);
break;
}
if ((x&-x) < (y&-y)) {
if (k < (x&-x)) {
x -= k;
k = 0;
}
else {
k -= x&-x;
x -= x&-x;
}
}
else {
if (k < (y&-y)) {
y -= k;
k = 0;
}
else {
k -= y&-y;
y -= y&-y;
}
}
}
return {x, y};
}
bool compare(pii a, pii b) {
ll raz = (a.fi + a.se) - (b.fi + b.se);
if (raz > 0) {
a = movek(a.fi, a.se, raz);
}
if (raz < 0) {
b = movek(b.fi, b.se, -raz);
}
if (a.fi > b.fi) {
return true;
}
else if (b.fi > a.fi) {
return false;
}
else {
if (raz > 0) {
return false;
}
else {
return true;
}
}
}
pii lca(pii a, pii b) {
ll raz = (a.fi + a.se) - (b.fi + b.se);
if (raz > 0) {
a = movek(a.fi, a.se, raz);
}
if (raz < 0) {
b = movek(b.fi, b.se, -raz);
}
if (a == b) {
return a;
}
for (ll i = 30; i >= 0; i--) {
pii pa = movek(a.fi, a.se, (1 << i));
pii pb = movek(b.fi, b.se, (1 << i));
if (pa == pb) continue;
a = pa;
b = pb;
}
return movek(a.fi, a.se, 1);
}
ll rek(ll pos) {
ll zbr = 0;
for (auto e : veze[pos]) {
if (e == pos) continue;
zbr += rek(e);
}
if (pos < n) zbr++;
black[pos] = zbr;
return zbr;
}
void tree() {
vector <pair<pii, ll>> st;
for (ll i = 0; i < n; i++) {
if (st.empty()) {
parent[i] = i;
st.push_back({v[i], i});
continue;
}
pii p = lca(st.back().fi, v[i]);
ll bla = -1;
while (!st.empty() && st.back().fi.fi + st.back().fi.se > p.fi + p.se) {
bla = st.back().se;
st.pop_back();
}
if (!st.empty() && st.back().fi.fi + st.back().fi.se < p.fi + p.se) {
parent[id] = st.back().se;
parent[bla] = id;
st.push_back({p, id});
v.push_back(p);
id++;
}
else if (st.empty()) {
parent[id] = id;
parent[bla] = id;
st.push_back({p, id});
v.push_back(p);
id++;
}
parent[i] = st.back().se;
st.push_back({v[i], i});
}
for (ll i = 0; i < id; i++) {
if (parent[i] == i) continue;
veze[parent[i]].push_back(i);
}
head = st[0].se;
}
void walk(ll now, ll pos) {
sol = min(sol, now);
for (auto e : veze[pos]) {
ll lvl = (v[e].fi + v[e].se) - (v[pos].fi + v[pos].se);
walk(now - (black[e] * 2 - n) * lvl, e);
}
}
int main() {
cin >> n;
id = n;
for (ll i = 1; i <= n; i++) {
cin >> x >> y;
v.push_back({x, y});
}
sort(v.begin(), v.end(), compare);
tree();
rek(head);
ll zbr = 0;
for (ll i = 0; i < n; i++) {
zbr += v[i].fi + v[i].se;
zbr -= v[head].fi + v[head].se;
}
sol = 1e18;
walk(zbr, head);
cout << sol << "\n";
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 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 |
3 ms |
5000 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 |
Runtime error |
110 ms |
13988 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
520 ms |
16336 KB |
Output is correct |
2 |
Correct |
517 ms |
16308 KB |
Output is correct |
3 |
Correct |
126 ms |
18820 KB |
Output is correct |
4 |
Correct |
121 ms |
15756 KB |
Output is correct |
5 |
Correct |
121 ms |
14984 KB |
Output is correct |