| 18785 | 2025-11-04 18:10:50 | algopro | Fire on a Tree | cpp17 | Hibás válasz 0/100 | 328ms | 35192 KiB |
// UUID: 9f182b31-2d46-4c91-afd7-85686188c4b3
#include <bits/stdc++.h>
using namespace std;
void dfs1(int i, int l, vector<vector<int>> & g, vector<int> & x) {
int maxi = 0, sum = 1;
for (int j : g[i]) {
if (j == l) continue;
dfs1(j, i, g, x);
maxi = max(maxi, x[j]);
sum += x[j];
}
x[i] = sum - maxi;
}
void dfs2(int i, int l, vector<vector<int>> & g, vector<int> & x, vector<int> & y, vector<int> & z) {
int max1 = 200000, max2 = 200000, sum = 1 + y[i];
for (int j : g[i]) {
if (j == l) continue;
if (x[j] > x[max1]) {
max2 = max1;
max1 = j;
} else if (x[j] > x[max2]) max2 = j;
sum += x[j];
}
z[i] = sum - max(x[max1], y[i]);
for (int j : g[i]) {
if (j == l) continue;
int maxi = x[max1];
if (j == max1) maxi = x[max2];
if (y[i] > maxi) maxi = y[i];
y[j] = sum - maxi;
dfs2(j, i, g, x, y, z);
}
}
int main() {
int n;
cin >> n;
vector<vector<int>> g(n);
for (int i = 0; i < n - 1; i++) {
int a, b;
cin >> a >> b;
g[a].push_back(b);
g[b].push_back(a);
}
vector<int> x(200001), y(n), z(n);
dfs1(0, -1, g, x);
dfs2(0, -1, g, x, y, z);
for (int a : z) cout << a << " ";
}
| Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
|---|---|---|---|---|---|---|---|
| subtask1 | 0/0 | ||||||
| 1 | Elfogadva | 2ms | 1320 KiB | ||||
| 2 | Elfogadva | 1ms | 1076 KiB | ||||
| subtask2 | 0/35 | ||||||
| 3 | Hibás válasz | 2ms | 1076 KiB | ||||
| 4 | Hibás válasz | 2ms | 1080 KiB | ||||
| 5 | Elfogadva | 2ms | 1076 KiB | ||||
| 6 | Hibás válasz | 2ms | 1076 KiB | ||||
| 7 | Hibás válasz | 1ms | 1076 KiB | ||||
| subtask3 | 0/25 | ||||||
| 8 | Hibás válasz | 2ms | 1076 KiB | ||||
| 9 | Hibás válasz | 3ms | 1076 KiB | ||||
| 10 | Elfogadva | 4ms | 1332 KiB | ||||
| 11 | Hibás válasz | 4ms | 1076 KiB | ||||
| 12 | Hibás válasz | 3ms | 1076 KiB | ||||
| 13 | Hibás válasz | 3ms | 1076 KiB | ||||
| subtask4 | 0/40 | ||||||
| 14 | Hibás válasz | 152ms | 8836 KiB | ||||
| 15 | Hibás válasz | 216ms | 11536 KiB | ||||
| 16 | Elfogadva | 317ms | 35192 KiB | ||||
| 17 | Hibás válasz | 263ms | 14428 KiB | ||||
| 18 | Hibás válasz | 300ms | 13108 KiB | ||||
| 19 | Hibás válasz | 296ms | 14072 KiB | ||||
| 20 | Hibás válasz | 266ms | 14552 KiB | ||||
| 21 | Hibás válasz | 328ms | 14288 KiB | ||||
| 22 | Hibás válasz | 300ms | 13876 KiB | ||||