| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1036326 |
2024-07-27T08:50:21 Z |
adaawf |
Hard route (IZhO17_road) |
C++17 |
|
5 ms |
12248 KB |
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> g[500005];
int dd[500005], da[500005], d[500005], z = 0;
long long int lazy[2000005], f[500005], t[2000005];
void push(int v) {
t[v * 2] += lazy[v];
t[v * 2 + 1] += lazy[v];
lazy[v * 2] += lazy[v];
lazy[v * 2 + 1] += lazy[v];
lazy[v] = 0;
}
void update(int v, int tl, int tr, int l, int r, int y) {
if (l > r) return;
if (tl == l && tr == r) {
t[v] += y;
lazy[v] += y;
return;
}
push(v);
int mid = (tl + tr) / 2;
update(v * 2, tl, mid, l, min(r, mid), y);
update(v * 2 + 1, mid + 1, tr, max(l, mid + 1), r, y);
t[v] = max(t[v * 2], t[v * 2 + 1]);
}
int sum(int v, int tl, int tr, int l, int r) {
if (l > r) return 0;
if (tl == l && tr == r) {
return t[v];
}
push(v);
int mid = (tl + tr) / 2;
return max(sum(v * 2, tl, mid, l, min(r, mid)), sum(v * 2 + 1, mid + 1, tr, max(l, mid + 1), r));
}
long long int res = 0, h = 0;
void dfs(int x, int p) {
dd[x] = ++z;
for (int w : g[x]) {
if (w == p) continue;
d[w] = d[x] + 1;
dfs(w, x);
}
da[x] = z;
}
void dfs2(int x, int p) {
vector<long long int> v;
vector<pair<long long int, long long int>> vv;
for (int w : g[x]) {
if (w == p) continue;
update(1, 1, z, dd[w], da[w], -2);
update(1, 1, z, 1, z, 1);
dfs2(w, x);
update(1, 1, z, dd[w], da[w], 2);
update(1, 1, z, 1, z, -1);
f[x] = max(f[x], f[w] + 1);
v.push_back(f[w] + 1);
}
if (v.size() < 2) return;
sort(v.begin(), v.end(), greater<long long int>());
long long int c = 0, k = v[0], d = max(sum(1, 1, z, 1, dd[x] - 1), sum(1, 1, z, da[x] + 1, z));
for (long long int w : v) {
if (w != k) {
vv.push_back({k, c});
c = 0;
}
k = w;
c++;
}
vv.push_back({k, c});
long long int hh, kk;
hh = d * (v[0] + v[1]);
if (vv[0].second >= 2) {
kk = (vv[0].second * (vv[0].second - 1) / 2);
}
else {
kk = vv[0].second * vv[1].second;
}
if (res < hh) {
res = hh;
h = kk;
}
else if (res == hh) h += kk;
if (v.size() < 3) return;
hh = v[0] * (v[1] + v[2]);
if (vv[0].second >= 3) {
kk = vv[0].second * (vv[0].second - 1) / 2;
}
else if (vv[0].second + vv[1].second >= 3) {
if (vv[0].second == 1) {
kk = vv[1].second * (vv[1].second - 1) / 2;
}
else {
kk = vv[1].second * 2;
}
}
else {
kk = vv[2].second;
}
if (res < hh) {
res = hh;
h = kk;
}
else if (res == hh) h += kk;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int n, r = 1;
cin >> n;
for (int i = 1; i < n; i++) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
for (int i = 1; i <= n; i++) {
if (g[i].size() > 1) {
r = i;
break;
}
}
dfs(r, 0);
for (int i = 1; i <= n; i++) {
update(1, 1, n, dd[i], dd[i], d[i]);
}
dfs2(r, 0);
cout << res << " " << h;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
12120 KB |
Output is correct |
| 2 |
Correct |
5 ms |
12124 KB |
Output is correct |
| 3 |
Correct |
5 ms |
12124 KB |
Output is correct |
| 4 |
Correct |
5 ms |
12124 KB |
Output is correct |
| 5 |
Correct |
5 ms |
12248 KB |
Output is correct |
| 6 |
Incorrect |
4 ms |
12124 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
12120 KB |
Output is correct |
| 2 |
Correct |
5 ms |
12124 KB |
Output is correct |
| 3 |
Correct |
5 ms |
12124 KB |
Output is correct |
| 4 |
Correct |
5 ms |
12124 KB |
Output is correct |
| 5 |
Correct |
5 ms |
12248 KB |
Output is correct |
| 6 |
Incorrect |
4 ms |
12124 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
12120 KB |
Output is correct |
| 2 |
Correct |
5 ms |
12124 KB |
Output is correct |
| 3 |
Correct |
5 ms |
12124 KB |
Output is correct |
| 4 |
Correct |
5 ms |
12124 KB |
Output is correct |
| 5 |
Correct |
5 ms |
12248 KB |
Output is correct |
| 6 |
Incorrect |
4 ms |
12124 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
