Submission #1052546
Source Code Expand
#include <bits/stdc++.h> #define SZ(x) ((int) (x).size()) using namespace std; typedef long long i64; const int NMAX = 200005; vector<int> G[NMAX]; int values[NMAX]; int subtree[NMAX]; int h[NMAX], low[NMAX]; int total = 0; int64_t ans = 1; void dfs1(int node, int prev) { subtree[node] = values[node]; for (int to: G[node]) { if (to != prev) { dfs1(to, node); h[node] = max(h[node], h[to]); subtree[node] += subtree[to]; } } ++h[node]; } void dfs2(int node, int prev, int hup) { int hmax1 = hup, hmax2 = 0; int hnode = prev; int hmin = NMAX; for (int to: G[node]) { if (to != prev) { if (h[to] > hmax1) { hmax2 = hmax1; hmax1 = h[to]; hnode = to; } else if (h[to] > hmax2) { hmax2 = h[to]; } if (subtree[to] > 0) { hmin = min(hmin, h[to]); } } } hmax1++; hmax2++; // cerr << node << ' ' << hmax1 << ' ' << hmax2 << endl; int ch; if (hmax1 == hmax2) { ch = hmax2 - 1; } else { ch = hmax2; if (hmax1 > hmax2 + 1) { ch++; } } if (total - subtree[node] > 0) { hmin = min(hmin, hup); } hmin++; int vis = -1; if (values[node] != 1) { if (hmin == hmax1) { low[node] = hmax2 + 2; if (hnode == prev) { low[node] = max(low[node], low[hnode] + 2); } else { vis = hnode; dfs2(hnode, node, hmax2); low[node] = max(low[node], low[hnode] + 2); } } else { low[node] = hmin; } } else { low[node] = 1; } ans += max(ch - low[node] + 1, 0); // cerr << node + 1 << ' ' << hmin << ' ' << low[node] << ' ' << ch << endl; for (int to: G[node]) { if (to != prev && to != vis) { if (h[to] == hmax1 - 1) { dfs2(to, node, hmax2); } else { dfs2(to, node, hmax1); } } } } int main() { #ifdef LOCAL_RUN freopen("task.in", "r", stdin); freopen("task.out", "w", stdout); //freopen("task.err", "w", stderr); #endif // ONLINE_JUDGE ios::sync_with_stdio(false); cin.tie(0); int n; cin >> n; for (int i = 1; i < n; ++i) { int x, y; cin >> x >> y; x--; y--; G[x].push_back(y); G[y].push_back(x); } string s; cin >> s; for (int i = 0; i < n; ++i) { values[i] = s[i] - '0'; total += values[i]; } dfs1(0, -1); dfs2(0, -1, 0); cout << ans << '\n'; }
Submission Info
Submission Time | |
---|---|
Task | F - Black Radius |
User | AndreiNet |
Language | C++14 (GCC 5.4.1) |
Score | 1900 |
Code Size | 2900 Byte |
Status | AC |
Exec Time | 164 ms |
Memory | 28944 KB |
Judge Result
Set Name | Sample | Subtask | All | ||||||
---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 1300 / 1300 | 600 / 600 | ||||||
Status |
|
|
|
Set Name | Test Cases |
---|---|
Sample | 0_00.txt, 0_01.txt, 0_02.txt |
Subtask | 0_01.txt, 1_00.txt, 1_01.txt, 1_02.txt, 1_03.txt, 1_04.txt, 1_05.txt, 1_06.txt, 1_07.txt, 1_08.txt, 1_09.txt, 1_10.txt, 1_11.txt, 1_12.txt, 1_13.txt, 1_14.txt, 1_15.txt, 1_16.txt, 1_17.txt, 1_18.txt, 1_19.txt, 1_20.txt, 1_21.txt, 1_22.txt, 1_23.txt, 1_24.txt, 1_25.txt, 1_26.txt, 1_27.txt, 1_28.txt, 1_29.txt |
All | 0_00.txt, 0_01.txt, 0_02.txt, 1_00.txt, 1_01.txt, 1_02.txt, 1_03.txt, 1_04.txt, 1_05.txt, 1_06.txt, 1_07.txt, 1_08.txt, 1_09.txt, 1_10.txt, 1_11.txt, 1_12.txt, 1_13.txt, 1_14.txt, 1_15.txt, 1_16.txt, 1_17.txt, 1_18.txt, 1_19.txt, 1_20.txt, 1_21.txt, 1_22.txt, 1_23.txt, 1_24.txt, 1_25.txt, 1_26.txt, 1_27.txt, 1_28.txt, 1_29.txt, 2_00.txt, 2_01.txt, 2_02.txt, 2_03.txt, 2_04.txt, 2_05.txt, 2_06.txt, 2_07.txt, 2_08.txt, 2_09.txt, 2_10.txt, 2_11.txt, 2_12.txt, 2_13.txt, 2_14.txt, 2_15.txt, 2_16.txt, 2_17.txt, 2_18.txt, 2_19.txt, 2_20.txt, 2_21.txt, 2_22.txt, 2_23.txt, 2_24.txt, 2_25.txt, 2_26.txt, 2_27.txt, 2_28.txt, 2_29.txt, 2_30.txt, 2_31.txt, 2_32.txt, 2_33.txt, 2_34.txt, 2_35.txt, 2_36.txt, 2_37.txt, 2_38.txt, 2_39.txt, 2_40.txt, 2_41.txt, 2_42.txt, 2_43.txt, 2_44.txt, 2_45.txt, 2_46.txt, 2_47.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
0_00.txt | AC | 7 ms | 4992 KB |
0_01.txt | AC | 7 ms | 4992 KB |
0_02.txt | AC | 7 ms | 4992 KB |
1_00.txt | AC | 7 ms | 4992 KB |
1_01.txt | AC | 133 ms | 28944 KB |
1_02.txt | AC | 124 ms | 23824 KB |
1_03.txt | AC | 107 ms | 14736 KB |
1_04.txt | AC | 93 ms | 15096 KB |
1_05.txt | AC | 76 ms | 15604 KB |
1_06.txt | AC | 104 ms | 14864 KB |
1_07.txt | AC | 108 ms | 14988 KB |
1_08.txt | AC | 108 ms | 16016 KB |
1_09.txt | AC | 118 ms | 21776 KB |
1_10.txt | AC | 113 ms | 20744 KB |
1_11.txt | AC | 131 ms | 28692 KB |
1_12.txt | AC | 106 ms | 17928 KB |
1_13.txt | AC | 118 ms | 21268 KB |
1_14.txt | AC | 107 ms | 17544 KB |
1_15.txt | AC | 110 ms | 16264 KB |
1_16.txt | AC | 111 ms | 18700 KB |
1_17.txt | AC | 117 ms | 20232 KB |
1_18.txt | AC | 110 ms | 14736 KB |
1_19.txt | AC | 103 ms | 14736 KB |
1_20.txt | AC | 105 ms | 14736 KB |
1_21.txt | AC | 108 ms | 15624 KB |
1_22.txt | AC | 98 ms | 14988 KB |
1_23.txt | AC | 98 ms | 14864 KB |
1_24.txt | AC | 104 ms | 15880 KB |
1_25.txt | AC | 101 ms | 17400 KB |
1_26.txt | AC | 96 ms | 14844 KB |
1_27.txt | AC | 93 ms | 15224 KB |
1_28.txt | AC | 87 ms | 15736 KB |
1_29.txt | AC | 104 ms | 18184 KB |
2_00.txt | AC | 7 ms | 4992 KB |
2_01.txt | AC | 143 ms | 28304 KB |
2_02.txt | AC | 131 ms | 26128 KB |
2_03.txt | AC | 130 ms | 25488 KB |
2_04.txt | AC | 120 ms | 21520 KB |
2_05.txt | AC | 119 ms | 21776 KB |
2_06.txt | AC | 123 ms | 22800 KB |
2_07.txt | AC | 111 ms | 14732 KB |
2_08.txt | AC | 108 ms | 14736 KB |
2_09.txt | AC | 108 ms | 14736 KB |
2_10.txt | AC | 94 ms | 15096 KB |
2_11.txt | AC | 93 ms | 15096 KB |
2_12.txt | AC | 94 ms | 15096 KB |
2_13.txt | AC | 77 ms | 15604 KB |
2_14.txt | AC | 76 ms | 15604 KB |
2_15.txt | AC | 77 ms | 15604 KB |
2_16.txt | AC | 103 ms | 14864 KB |
2_17.txt | AC | 103 ms | 14864 KB |
2_18.txt | AC | 104 ms | 14864 KB |
2_19.txt | AC | 104 ms | 14864 KB |
2_20.txt | AC | 105 ms | 14864 KB |
2_21.txt | AC | 105 ms | 14864 KB |
2_22.txt | AC | 107 ms | 15884 KB |
2_23.txt | AC | 108 ms | 16656 KB |
2_24.txt | AC | 109 ms | 16400 KB |
2_25.txt | AC | 120 ms | 22288 KB |
2_26.txt | AC | 118 ms | 20880 KB |
2_27.txt | AC | 120 ms | 22284 KB |
2_28.txt | AC | 114 ms | 20232 KB |
2_29.txt | AC | 128 ms | 26632 KB |
2_30.txt | AC | 132 ms | 24584 KB |
2_31.txt | AC | 164 ms | 20360 KB |
2_32.txt | AC | 114 ms | 15240 KB |
2_33.txt | AC | 109 ms | 17808 KB |
2_34.txt | AC | 117 ms | 19848 KB |
2_35.txt | AC | 119 ms | 23176 KB |
2_36.txt | AC | 108 ms | 14604 KB |
2_37.txt | AC | 109 ms | 14732 KB |
2_38.txt | AC | 107 ms | 16136 KB |
2_39.txt | AC | 108 ms | 14868 KB |
2_40.txt | AC | 96 ms | 15096 KB |
2_41.txt | AC | 101 ms | 14856 KB |
2_42.txt | AC | 97 ms | 14968 KB |
2_43.txt | AC | 117 ms | 21524 KB |
2_44.txt | AC | 90 ms | 15096 KB |
2_45.txt | AC | 83 ms | 15476 KB |
2_46.txt | AC | 84 ms | 15608 KB |
2_47.txt | AC | 102 ms | 19192 KB |