Submission #1070551
Source Code Expand
#include <cstdio> #include <cstdlib> #include <algorithm> #include <vector> #include <iostream> #include <cassert> using namespace std; const int N = 2e5 + 7; const int INF = 1e9 + 7; int n; int upper[N], lower[N]; vector<int> adj[N]; pair<int, int> farest[N][2], up[N]; void fresh(pair<int, int> far[2], pair<int, int> tmp) { if (tmp > far[0]) { far[1] = far[0]; far[0] = tmp; } else if (tmp > far[1]) { far[1] = tmp; } } void dfs_down(int u, int from) { for (int i = 0; i < 2; i++) { farest[u][i] = {0, 0}; } for (auto v : adj[u]) { if (v == from) continue; dfs_down(v, u); auto tmp = make_pair(farest[v][0].first + 1, v); fresh(farest[u], tmp); } } void dfs_up(int u, int from) { for (auto v : adj[u]) { if (v == from) continue; up[v].first = max(up[u].first + 1, v == farest[u][0].second ? farest[u][1].first + 1 : farest[u][0].first + 1); up[v].second = u; dfs_up(v, u); } fresh(farest[u], up[u]); upper[u] = min(farest[u][1].first + 1, farest[u][0].first - 1); } vector<int> queue[N]; int finish[N]; void go(int i, int u) { for (auto v : adj[u]) { int duv = farest[u][0].second == v ? farest[u][1].first : farest[u][0].first; int dvu = farest[v][0].second == u ? farest[v][1].first : farest[v][0].first; //printf("v = %d\n", v); int t = min(max(duv + 1, lower[u] - 1), max(dvu + 1, lower[u]) + 1); queue[t].push_back(v); } } int main() { scanf("%d", &n); for (int i = 1; i < n; i++) { int u, v; scanf("%d %d", &u, &v); adj[u].push_back(v); adj[v].push_back(u); } dfs_down(1, 0); up[1] = make_pair(0, 0); dfs_up(1, 0); { static char buffer[N]; scanf("%s", buffer + 1); for (int i = 1; buffer[i]; i++) { if (buffer[i] == '1') { lower[i] = 0; queue[0].push_back(i); } } } for (int i = 0; i <= n; ) { if (i > 0 && queue[i - 1].size()) { i--; } else if (queue[i].size() == 0) { i++; } else { int top = queue[i].back(); queue[i].pop_back(); if (!finish[top] || i < lower[top]) { lower[top] = i; finish[top] = true; go(i, top); } } } long long ans = 0; assert(queue[0].size() == 0); for (int i = 1; i <= n; i++) { if (upper[i] >= lower[i]) ans += upper[i] - lower[i] + 1; //printf("i = %d lower = %d upper = %d\n", i, lower[i], upper[i]); assert(queue[i].size() == 0); assert(finish[i]); } cout << ans + 1 << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | F - Black Radius |
User | Miceren |
Language | C++14 (GCC 5.4.1) |
Score | 1900 |
Code Size | 2487 Byte |
Status | AC |
Exec Time | 256 ms |
Memory | 36472 KB |
Compile Error
./Main.cpp: In function ‘int main()’: ./Main.cpp:65:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d", &n); ^ ./Main.cpp:68:25: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d %d", &u, &v); ^ ./Main.cpp:77:26: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%s", buffer + 1); ^
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 | 12 ms | 9600 KB |
0_01.txt | AC | 12 ms | 9600 KB |
0_02.txt | AC | 13 ms | 9600 KB |
1_00.txt | AC | 12 ms | 9600 KB |
1_01.txt | AC | 194 ms | 36472 KB |
1_02.txt | AC | 185 ms | 33656 KB |
1_03.txt | AC | 149 ms | 25848 KB |
1_04.txt | AC | 128 ms | 26868 KB |
1_05.txt | AC | 110 ms | 26868 KB |
1_06.txt | AC | 142 ms | 26616 KB |
1_07.txt | AC | 143 ms | 26740 KB |
1_08.txt | AC | 147 ms | 27380 KB |
1_09.txt | AC | 169 ms | 31476 KB |
1_10.txt | AC | 165 ms | 30328 KB |
1_11.txt | AC | 186 ms | 36084 KB |
1_12.txt | AC | 155 ms | 28148 KB |
1_13.txt | AC | 168 ms | 30964 KB |
1_14.txt | AC | 152 ms | 28148 KB |
1_15.txt | AC | 151 ms | 27384 KB |
1_16.txt | AC | 162 ms | 29296 KB |
1_17.txt | AC | 178 ms | 31096 KB |
1_18.txt | AC | 146 ms | 26104 KB |
1_19.txt | AC | 143 ms | 26100 KB |
1_20.txt | AC | 149 ms | 26100 KB |
1_21.txt | AC | 152 ms | 26744 KB |
1_22.txt | AC | 132 ms | 26612 KB |
1_23.txt | AC | 137 ms | 26996 KB |
1_24.txt | AC | 146 ms | 27380 KB |
1_25.txt | AC | 140 ms | 28660 KB |
1_26.txt | AC | 133 ms | 26356 KB |
1_27.txt | AC | 136 ms | 27380 KB |
1_28.txt | AC | 126 ms | 27380 KB |
1_29.txt | AC | 149 ms | 28404 KB |
2_00.txt | AC | 12 ms | 9600 KB |
2_01.txt | AC | 181 ms | 35712 KB |
2_02.txt | AC | 179 ms | 33920 KB |
2_03.txt | AC | 189 ms | 33916 KB |
2_04.txt | AC | 173 ms | 31616 KB |
2_05.txt | AC | 206 ms | 30848 KB |
2_06.txt | AC | 213 ms | 32508 KB |
2_07.txt | AC | 160 ms | 24064 KB |
2_08.txt | AC | 163 ms | 24064 KB |
2_09.txt | AC | 169 ms | 25216 KB |
2_10.txt | AC | 135 ms | 24696 KB |
2_11.txt | AC | 136 ms | 24696 KB |
2_12.txt | AC | 137 ms | 25208 KB |
2_13.txt | AC | 113 ms | 24820 KB |
2_14.txt | AC | 117 ms | 25076 KB |
2_15.txt | AC | 116 ms | 26484 KB |
2_16.txt | AC | 148 ms | 24192 KB |
2_17.txt | AC | 149 ms | 24192 KB |
2_18.txt | AC | 151 ms | 24448 KB |
2_19.txt | AC | 150 ms | 24448 KB |
2_20.txt | AC | 149 ms | 24320 KB |
2_21.txt | AC | 160 ms | 26488 KB |
2_22.txt | AC | 191 ms | 25472 KB |
2_23.txt | AC | 210 ms | 25856 KB |
2_24.txt | AC | 217 ms | 26488 KB |
2_25.txt | AC | 245 ms | 30720 KB |
2_26.txt | AC | 256 ms | 29568 KB |
2_27.txt | AC | 222 ms | 30964 KB |
2_28.txt | AC | 160 ms | 29952 KB |
2_29.txt | AC | 180 ms | 34176 KB |
2_30.txt | AC | 170 ms | 32128 KB |
2_31.txt | AC | 170 ms | 30464 KB |
2_32.txt | AC | 145 ms | 24704 KB |
2_33.txt | AC | 174 ms | 27132 KB |
2_34.txt | AC | 163 ms | 28928 KB |
2_35.txt | AC | 171 ms | 31744 KB |
2_36.txt | AC | 151 ms | 23936 KB |
2_37.txt | AC | 150 ms | 25212 KB |
2_38.txt | AC | 148 ms | 25596 KB |
2_39.txt | AC | 158 ms | 24832 KB |
2_40.txt | AC | 134 ms | 24444 KB |
2_41.txt | AC | 140 ms | 24700 KB |
2_42.txt | AC | 127 ms | 24440 KB |
2_43.txt | AC | 165 ms | 29824 KB |
2_44.txt | AC | 125 ms | 24440 KB |
2_45.txt | AC | 116 ms | 25720 KB |
2_46.txt | AC | 118 ms | 25460 KB |
2_47.txt | AC | 149 ms | 29428 KB |