Submission #1140109
Source Code Expand
#include <cstdio>
#include <cstring>
#include <cassert>
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
#define TRACE(x) cerr << #x << " = " << x << endl
#define REP(i, n) for (int i=0; i<n; i++)
#define FOR(i, a, b) for (int i=(a); i<(b); i++)
#define _ << " " <<
typedef long long ll;
typedef pair<int, int> P;
#define X first
#define Y second
const int MAX = 1<<18;
int dist_down[MAX], dist_up[MAX];
vector <int> V[MAX];
vector <int> Ld[MAX], Rd[MAX];
int poz_par[MAX], par[MAX];
char s[MAX];
void dfs_down(int node, int pr)
{
par[node] = pr;
for (auto it = V[node].begin(); it != V[node].end(); it++)
if (*it == pr) {
V[node].erase(it);
break;
}
Ld[node].push_back(0);
for (auto it : V[node]) {
dfs_down(it, node);
poz_par[it] = (int) Ld[node].size();
Ld[node].push_back(max(Ld[node].back(), dist_down[it] + 1));
}
dist_down[node] = Ld[node].back();
Rd[node].push_back(0);
for (int i=(int) V[node].size()-1; i>=0; i--) {
int it = V[node][i];
Rd[node].push_back(max(Rd[node].back(), dist_down[it] + 1));
}
reverse(Rd[node].begin(), Rd[node].end());
}
P presjek(P a, P b)
{
return P(max(a.X, b.X), min(a.Y, b.Y));
}
P unija(P a, P b)
{
if (a.X > a.Y) return b;
if (b.X > b.Y) return a;
P tmp = presjek(a, b);
assert(tmp.X - 1 <= tmp.Y);
return P(min(a.X, b.X), max(a.Y, b.Y));
}
P razlika(P a, P b)
{
P tmp = presjek(a, b);
if (tmp.X > tmp.Y) return a;
assert(tmp.Y == a.Y || tmp.X == a.X);
if (tmp.Y == a.Y) return P(a.X, tmp.X - 1);
return P(tmp.Y + 1, a.Y);
}
P un[MAX];
ll rje = 0;
void dfs_up(int node, int pr)
{
if (pr != -1) {
dist_up[node] = 1 + max(dist_up[pr],
max(Ld[pr][poz_par[node]-1], Rd[pr][poz_par[node]]));
}
// if (node+1 == 6)
// printf("UNPAR %d %d\n", un[pr].X, un[pr].Y);
if (pr != -1) {
if (dist_down[node] > dist_up[node] - 1) {
P tmp = presjek(P(dist_up[node], MAX), P(un[pr].X-1, un[pr].Y-1));
// if (node+1 == 5) TRACE(tmp.X _ tmp.Y);
un[node] = unija(un[node], tmp);
// un[pr] = unija(un[pr], P(tmp.X+1, tmp.Y+1));
// un[node] = unija(un[node], presjek(P(dust_up[node], MAX), P(un[pr].X-1, un[pr].Y-1)));
// un[pr] = unija(un[pr], presjek(P_P(un[node].X+1, un[node].Y+1));
}
// pres = razlika(pres, presjek(P(dist_up[node], MAX), P(un[pr].X-1, un[pr].Y-1)));
else if (dist_down[node] < dist_up[node] - 1) {
P tmp = presjek(P(dist_down[node] + 2, MAX), P(un[pr].X+1, un[pr].Y+1));
//if (node+1 == 5) { printf("AA\n"); TRACE(tmp.X _ tmp.Y); }
un[node] = unija(un[node], tmp);
// un[pr] = unija(un[pr], P(tmp.X-1, tmp.Y-1));
// un[node] = unija(un[node], P(un[pr].X+1, un[pr].Y+1));
// un[pr] = unija(un[pr], P(un[node].X-1, un[node].Y-1));
}
// pres = razlika(pres, presjek(P(dist_down[node] + 2, MAX), P(un[pr].X+1, un[pr].Y+1)));
}
P pres = P(0, max(dist_down[node], dist_up[node]) - 1);
pres = razlika(pres, un[node]);
// if (node+1 == 2)
// printf("UN %d %d %d\n", node+1, un[node].X, un[node].Y);
if (s[node] == '1') {
un[node] = unija(un[node], pres);
rje += max(0, pres.Y - pres.X + 1);
// printf("NODE %d %d %d\n", node+1, pres.X, pres.Y);
}
// if (pr != -1) {
// if (dist_down[node] > dist_up[node] - 1)
// pres = presjek(pres, P(0, dist_up[node] - 1));
// else if (dist_down[node] < dist_up[node] - 1)
// pres = presjek(pres, P(0, dist_down[node] + 1));
// }
// TRACE(node+1 _ dist_down[node] _ dist_up[node]);
//TRACE(node+1 _ pres.X _ pres.Y);
// printf("UNIJA %d %d %d\n", node+1, un[node].X, un[node].Y);
for (auto it : V[node])
dfs_up(it, node);
if (pr != -1) {
if (dist_down[node] > dist_up[node] - 1) {
P tmp = presjek(P(dist_up[node], MAX), un[node]);
// if (node+1 == 5) TRACE(tmp.X _ tmp.Y);
// un[node] = unija(un[node], tmp);
un[pr] = unija(un[pr], P(tmp.X+1, tmp.Y+1));
// un[pr] = unija(un[pr], P(tmp.X+1, tmp.Y+1));
// un[node] = unija(un[node], presjek(P(dust_up[node], MAX), P(un[pr].X-1, un[pr].Y-1)));
// un[pr] = unija(un[pr], presjek(P_P(un[node].X+1, un[node].Y+1));
}
// pres = razlika(pres, presjek(P(dist_up[node], MAX), P(un[pr].X-1, un[pr].Y-1)));
else if (dist_down[node] < dist_up[node] - 1) {
P tmp = presjek(P(dist_down[node] + 2, MAX), un[node]);
un[pr] = unija(un[pr], P(tmp.X-1, tmp.Y-1));
// if (node+1 == 5) { printf("AA\n"); TRACE(tmp.X _ tmp.Y); }
// un[node] = unija(un[node], tmp);
// un[pr] = unija(un[pr], P(tmp.X-1, tmp.Y-1));
// un[node] = unija(un[node], P(un[pr].X+1, un[pr].Y+1));
// un[pr] = unija(un[pr], P(un[node].X-1, un[node].Y-1));
}
// pres = razlika(pres, presjek(P(dist_down[node] + 2, MAX), P(un[pr].X+1, un[pr].Y+1)));
}
}
int main()
{
REP(i, MAX) un[i] = P(0, -1);
int n;
scanf("%d", &n);
REP(i, n-1) {
int a, b;
scanf("%d%d", &a, &b); a--; b--;
V[a].push_back(b);
V[b].push_back(a);
}
scanf(" %s", s);
dfs_down(0, -1);
dfs_up(0, -1);
rje++;
printf("%lld\n", rje);
return 0;
}
Submission Info
Submission Time |
|
Task |
F - Black Radius |
User |
dbradac |
Language |
C++14 (GCC 5.4.1) |
Score |
1900 |
Code Size |
5494 Byte |
Status |
AC |
Exec Time |
234 ms |
Memory |
60288 KB |
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:173:18: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
^
./Main.cpp:176:26: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &a, &b); a--; b--;
^
./Main.cpp:181:18: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf(" %s", s);
^
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 |
8 ms |
24832 KB |
0_01.txt |
AC |
8 ms |
24832 KB |
0_02.txt |
AC |
8 ms |
24832 KB |
1_00.txt |
AC |
9 ms |
24832 KB |
1_01.txt |
AC |
223 ms |
60288 KB |
1_02.txt |
AC |
223 ms |
54272 KB |
1_03.txt |
AC |
195 ms |
43648 KB |
1_04.txt |
AC |
181 ms |
45176 KB |
1_05.txt |
AC |
143 ms |
46708 KB |
1_06.txt |
AC |
194 ms |
44288 KB |
1_07.txt |
AC |
194 ms |
44288 KB |
1_08.txt |
AC |
200 ms |
45568 KB |
1_09.txt |
AC |
220 ms |
52096 KB |
1_10.txt |
AC |
210 ms |
50688 KB |
1_11.txt |
AC |
217 ms |
59904 KB |
1_12.txt |
AC |
206 ms |
47232 KB |
1_13.txt |
AC |
221 ms |
51328 KB |
1_14.txt |
AC |
194 ms |
47232 KB |
1_15.txt |
AC |
199 ms |
45824 KB |
1_16.txt |
AC |
207 ms |
48384 KB |
1_17.txt |
AC |
221 ms |
50176 KB |
1_18.txt |
AC |
192 ms |
43648 KB |
1_19.txt |
AC |
190 ms |
43904 KB |
1_20.txt |
AC |
195 ms |
43648 KB |
1_21.txt |
AC |
198 ms |
44800 KB |
1_22.txt |
AC |
183 ms |
44668 KB |
1_23.txt |
AC |
189 ms |
44284 KB |
1_24.txt |
AC |
220 ms |
45312 KB |
1_25.txt |
AC |
190 ms |
47480 KB |
1_26.txt |
AC |
175 ms |
44028 KB |
1_27.txt |
AC |
174 ms |
45304 KB |
1_28.txt |
AC |
160 ms |
45944 KB |
1_29.txt |
AC |
190 ms |
48124 KB |
2_00.txt |
AC |
8 ms |
24832 KB |
2_01.txt |
AC |
218 ms |
59520 KB |
2_02.txt |
AC |
219 ms |
56960 KB |
2_03.txt |
AC |
230 ms |
56192 KB |
2_04.txt |
AC |
217 ms |
51712 KB |
2_05.txt |
AC |
234 ms |
51840 KB |
2_06.txt |
AC |
218 ms |
53120 KB |
2_07.txt |
AC |
194 ms |
43648 KB |
2_08.txt |
AC |
214 ms |
43648 KB |
2_09.txt |
AC |
188 ms |
43648 KB |
2_10.txt |
AC |
171 ms |
45176 KB |
2_11.txt |
AC |
177 ms |
45176 KB |
2_12.txt |
AC |
170 ms |
45176 KB |
2_13.txt |
AC |
139 ms |
46708 KB |
2_14.txt |
AC |
136 ms |
46708 KB |
2_15.txt |
AC |
138 ms |
46708 KB |
2_16.txt |
AC |
187 ms |
44288 KB |
2_17.txt |
AC |
186 ms |
44288 KB |
2_18.txt |
AC |
194 ms |
44288 KB |
2_19.txt |
AC |
185 ms |
44288 KB |
2_20.txt |
AC |
195 ms |
44288 KB |
2_21.txt |
AC |
216 ms |
44288 KB |
2_22.txt |
AC |
205 ms |
45440 KB |
2_23.txt |
AC |
203 ms |
46208 KB |
2_24.txt |
AC |
223 ms |
45952 KB |
2_25.txt |
AC |
212 ms |
52608 KB |
2_26.txt |
AC |
215 ms |
50944 KB |
2_27.txt |
AC |
218 ms |
52608 KB |
2_28.txt |
AC |
201 ms |
50304 KB |
2_29.txt |
AC |
226 ms |
57472 KB |
2_30.txt |
AC |
204 ms |
55296 KB |
2_31.txt |
AC |
211 ms |
50304 KB |
2_32.txt |
AC |
197 ms |
44672 KB |
2_33.txt |
AC |
192 ms |
47488 KB |
2_34.txt |
AC |
196 ms |
49664 KB |
2_35.txt |
AC |
207 ms |
53248 KB |
2_36.txt |
AC |
200 ms |
43520 KB |
2_37.txt |
AC |
189 ms |
43776 KB |
2_38.txt |
AC |
193 ms |
45440 KB |
2_39.txt |
AC |
188 ms |
43776 KB |
2_40.txt |
AC |
178 ms |
45048 KB |
2_41.txt |
AC |
187 ms |
44288 KB |
2_42.txt |
AC |
173 ms |
44792 KB |
2_43.txt |
AC |
233 ms |
51968 KB |
2_44.txt |
AC |
161 ms |
45176 KB |
2_45.txt |
AC |
148 ms |
46328 KB |
2_46.txt |
AC |
147 ms |
46708 KB |
2_47.txt |
AC |
182 ms |
49016 KB |