Submission #1043333
Source Code Expand
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <cassert>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
const ll mod=1000000007;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
// head
const int N=201000;
int dep[N],p[N][22];
int n,u,v,mc,md,pu,pv,maxd[N],mad[N],l[N],shav[N];
ll ret;
VI e[N];
char fav[N];
void dfs(int u,int f,int dis) {
p[u][0]=f; dep[u]=dis;
if (dis>md) md=dis,mc=u;
for (auto v:e[u]) if (v!=f) {
dfs(v,u,dis+1);
}
}
#define LOGN 18
int lca(int u,int v) {
if (dep[u]>dep[v]) swap(u,v);
per(i,0,LOGN) if (dep[p[v][i]]>=dep[u]) v=p[v][i];
if (u==v) return u;
per(i,0,LOGN) if (p[v][i]!=p[u][i]) u=p[u][i],v=p[v][i];
return p[u][0];
}
int dist(int u,int v) {
return dep[u]+dep[v]-2*dep[lca(u,v)];
}
void solve(int u,int f) {
mad[u]=0;
for (auto v:e[u]) if (v!=f) {
solve(v,u);
mad[u]=max(mad[u],mad[v]+1);
}
shav[u]=mad[u]+2; // if (u,d) d>=shav[u] -> (f,d-1)
if (fav[u]=='1') l[u]=0;
// printf("gg %d %d\n",u,maxd[u]);
if (f!=0) {
if (maxd[u]>maxd[f]) {
l[f]=min(l[f],max(l[u]-1,shav[u]-1));
// printf("ff %d %d %d\n",u,shav[u],l[u]);
ret+=max(0,shav[u]-l[u]);
} else {
// double center
shav[u]=maxd[u]; // d>=shav[u] -> (f,d)
l[f]=min(l[f],max(l[u],shav[u]));
ret+=max(0,shav[u]-l[u]);
}
} else ret+=max(0,maxd[u]-l[u]+1);
}
int main() {
scanf("%d",&n);
rep(i,1,n) {
scanf("%d%d",&u,&v);
e[u].pb(v); e[v].pb(u);
}
dfs(1,0,1);
md=0;
pu=mc;
dfs(pu,0,1);
rep(j,1,LOGN) rep(i,1,n+1) p[i][j]=p[p[i][j-1]][j-1];
pv=mc;
rep(i,1,n+1) maxd[i]=max(dist(i,pu),dist(i,pv));
// printf("ss %d %d\n",pu,pv);
// rep(i,1,n+1) printf("%d ",maxd[i]); puts("");
int rt=min_element(maxd+1,maxd+n+1)-maxd;
// printf("root %d\n",rt);
scanf("%s",fav+1);
rep(i,1,n+1) l[i]=1<<30;
solve(rt,0);
printf("%lld\n",ret);
}
Submission Info
Submission Time |
|
Task |
F - Black Radius |
User |
apiad |
Language |
C++14 (GCC 5.4.1) |
Score |
1900 |
Code Size |
2320 Byte |
Status |
AC |
Exec Time |
382 ms |
Memory |
41856 KB |
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:74:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
^
./Main.cpp:76:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&u,&v);
^
./Main.cpp:90:19: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%s",fav+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 |
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 |
5120 KB |
1_01.txt |
AC |
346 ms |
41856 KB |
1_02.txt |
AC |
355 ms |
38784 KB |
1_03.txt |
AC |
301 ms |
32512 KB |
1_04.txt |
AC |
219 ms |
32888 KB |
1_05.txt |
AC |
173 ms |
33268 KB |
1_06.txt |
AC |
237 ms |
32896 KB |
1_07.txt |
AC |
237 ms |
32768 KB |
1_08.txt |
AC |
291 ms |
33664 KB |
1_09.txt |
AC |
324 ms |
37248 KB |
1_10.txt |
AC |
287 ms |
37504 KB |
1_11.txt |
AC |
326 ms |
40192 KB |
1_12.txt |
AC |
316 ms |
34048 KB |
1_13.txt |
AC |
343 ms |
36352 KB |
1_14.txt |
AC |
267 ms |
33920 KB |
1_15.txt |
AC |
295 ms |
34048 KB |
1_16.txt |
AC |
344 ms |
35328 KB |
1_17.txt |
AC |
370 ms |
37504 KB |
1_18.txt |
AC |
274 ms |
32256 KB |
1_19.txt |
AC |
243 ms |
32384 KB |
1_20.txt |
AC |
269 ms |
32256 KB |
1_21.txt |
AC |
297 ms |
33024 KB |
1_22.txt |
AC |
217 ms |
32636 KB |
1_23.txt |
AC |
231 ms |
32636 KB |
1_24.txt |
AC |
278 ms |
33280 KB |
1_25.txt |
AC |
261 ms |
33912 KB |
1_26.txt |
AC |
213 ms |
31996 KB |
1_27.txt |
AC |
204 ms |
32760 KB |
1_28.txt |
AC |
211 ms |
33144 KB |
1_29.txt |
AC |
283 ms |
35836 KB |
2_00.txt |
AC |
7 ms |
4992 KB |
2_01.txt |
AC |
339 ms |
41856 KB |
2_02.txt |
AC |
368 ms |
41856 KB |
2_03.txt |
AC |
352 ms |
41856 KB |
2_04.txt |
AC |
367 ms |
38784 KB |
2_05.txt |
AC |
382 ms |
38784 KB |
2_06.txt |
AC |
360 ms |
38784 KB |
2_07.txt |
AC |
286 ms |
32512 KB |
2_08.txt |
AC |
298 ms |
32512 KB |
2_09.txt |
AC |
288 ms |
32512 KB |
2_10.txt |
AC |
219 ms |
32888 KB |
2_11.txt |
AC |
219 ms |
32888 KB |
2_12.txt |
AC |
207 ms |
32888 KB |
2_13.txt |
AC |
181 ms |
33268 KB |
2_14.txt |
AC |
178 ms |
33268 KB |
2_15.txt |
AC |
183 ms |
33268 KB |
2_16.txt |
AC |
226 ms |
32768 KB |
2_17.txt |
AC |
224 ms |
32768 KB |
2_18.txt |
AC |
231 ms |
32768 KB |
2_19.txt |
AC |
232 ms |
32768 KB |
2_20.txt |
AC |
243 ms |
32768 KB |
2_21.txt |
AC |
238 ms |
32768 KB |
2_22.txt |
AC |
293 ms |
33664 KB |
2_23.txt |
AC |
303 ms |
33664 KB |
2_24.txt |
AC |
303 ms |
33664 KB |
2_25.txt |
AC |
327 ms |
37248 KB |
2_26.txt |
AC |
333 ms |
37248 KB |
2_27.txt |
AC |
321 ms |
37248 KB |
2_28.txt |
AC |
283 ms |
36352 KB |
2_29.txt |
AC |
342 ms |
41216 KB |
2_30.txt |
AC |
339 ms |
38144 KB |
2_31.txt |
AC |
351 ms |
37632 KB |
2_32.txt |
AC |
242 ms |
33024 KB |
2_33.txt |
AC |
313 ms |
34176 KB |
2_34.txt |
AC |
332 ms |
35072 KB |
2_35.txt |
AC |
339 ms |
37376 KB |
2_36.txt |
AC |
276 ms |
32256 KB |
2_37.txt |
AC |
262 ms |
32384 KB |
2_38.txt |
AC |
294 ms |
33024 KB |
2_39.txt |
AC |
287 ms |
32512 KB |
2_40.txt |
AC |
217 ms |
32760 KB |
2_41.txt |
AC |
222 ms |
32384 KB |
2_42.txt |
AC |
227 ms |
32376 KB |
2_43.txt |
AC |
306 ms |
36096 KB |
2_44.txt |
AC |
201 ms |
32632 KB |
2_45.txt |
AC |
195 ms |
33016 KB |
2_46.txt |
AC |
191 ms |
33140 KB |
2_47.txt |
AC |
272 ms |
35320 KB |