Submission #1370895
Source Code Expand
#include <bits/stdc++.h> using namespace std; typedef signed long long ll; #undef _P #define _P(...) (void)printf(__VA_ARGS__) #define FOR(x,to) for(x=0;x<(to);x++) #define FORR(x,arr) for(auto& x:arr) #define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++) #define ALL(a) (a.begin()),(a.end()) #define ZERO(a) memset(a,0,sizeof(a)) #define MINUS(a) memset(a,0xff,sizeof(a)) //------------------------------------------------------- int N; string S; vector<int> E[202020]; vector<pair<int,int>> V[202020]; vector<pair<int,int>> L[202020],R[202020]; int A[202020],B[202020]; ll ret=0; map<int,pair<int,int>> memo[202020]; pair<int,int> dfs(int cur,int pre) { V[cur].resize(E[cur].size()); int D=0, is=S[cur], i; FOR(i,E[cur].size()) { int r=E[cur][i]; if(r!=pre) { V[cur][i]=dfs(r,cur); V[cur][i].first++; D=max(D,V[cur][i].first); is|=V[cur][i].second; } } return memo[cur][pre] = make_pair(D,is); } void dfs2(int cur,int pre,pair<int,int> par) { par.first++; int i; FOR(i,E[cur].size()) { int r=E[cur][i]; if(r==pre) V[cur][i]=par; } L[cur].resize(E[cur].size()); R[cur].resize(E[cur].size()); L[cur][0].second = R[cur].back().second = S[cur]; for(i=1;i<L[cur].size();i++) { L[cur][i].first=max(L[cur][i-1].first,V[cur][i-1].first); L[cur][i].second=L[cur][i-1].second | V[cur][i-1].second; } for(i=R[cur].size()-2;i>=0;i--) { R[cur][i].first=max(R[cur][i+1].first,V[cur][i+1].first); R[cur][i].second=R[cur][i+1].second | V[cur][i+1].second; } FOR(i,E[cur].size()) { int r=E[cur][i]; if(r!=pre) { pair<int,int> p={max(L[cur][i].first,R[cur][i].first),L[cur][i].second|R[cur][i].second}; memo[cur][r]=p; dfs2(r,cur,p); } } } void centerv(int a) { vector<pair<int,int>> C=V[a]; C.push_back({0,S[a]}); C.push_back({0,S[a]}); sort(ALL(C)); reverse(ALL(C)); int Rmax=C[1].first; int Rmin=201010; FORR(v,C) if(v.second) Rmin=min(Rmin,v.first); if(Rmin<=Rmax) { ret+=Rmax-Rmin+1; } } void centere(int a,int b) { pair<int,int> p[2]={memo[a][b],memo[b][a]}; if(p[0].first<p[1].first) { ret+=p[0].second; } else if(p[0].first>p[1].first) { ret+=p[1].second; } else { ret++; } } void solve() { int i,j,k,l,r,x,y; string s; cin>>N; FOR(i,N-1) { cin>>A[i]>>B[i]; A[i]--, B[i]--; E[A[i]].push_back(B[i]); E[B[i]].push_back(A[i]); } cin>>S; FORR(c,S) c-='0'; auto p=dfs(0,-1); dfs2(0,-1,{0,0}); FOR(i,N) centerv(i); FOR(i,N-1) centere(A[i],B[i]); cout<<ret<<endl; } int main(int argc,char** argv){ string s;int i; if(argc==1) ios::sync_with_stdio(false), cin.tie(0); FOR(i,argc-1) s+=argv[i+1],s+='\n'; FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin); solve(); return 0; }
Submission Info
Submission Time | |
---|---|
Task | F - Black Radius |
User | kmjp |
Language | C++14 (GCC 5.4.1) |
Score | 1900 |
Code Size | 2842 Byte |
Status | AC |
Exec Time | 610 ms |
Memory | 99472 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 | 11 ms | 30208 KB |
0_01.txt | AC | 11 ms | 30208 KB |
0_02.txt | AC | 12 ms | 30208 KB |
1_00.txt | AC | 11 ms | 30208 KB |
1_01.txt | AC | 395 ms | 99472 KB |
1_02.txt | AC | 389 ms | 92688 KB |
1_03.txt | AC | 362 ms | 80528 KB |
1_04.txt | AC | 571 ms | 84728 KB |
1_05.txt | AC | 597 ms | 89716 KB |
1_06.txt | AC | 398 ms | 82192 KB |
1_07.txt | AC | 392 ms | 82316 KB |
1_08.txt | AC | 408 ms | 83728 KB |
1_09.txt | AC | 422 ms | 90768 KB |
1_10.txt | AC | 387 ms | 88456 KB |
1_11.txt | AC | 400 ms | 98836 KB |
1_12.txt | AC | 379 ms | 84360 KB |
1_13.txt | AC | 402 ms | 89876 KB |
1_14.txt | AC | 386 ms | 85000 KB |
1_15.txt | AC | 386 ms | 83592 KB |
1_16.txt | AC | 401 ms | 86284 KB |
1_17.txt | AC | 407 ms | 88072 KB |
1_18.txt | AC | 372 ms | 80528 KB |
1_19.txt | AC | 382 ms | 81168 KB |
1_20.txt | AC | 367 ms | 80144 KB |
1_21.txt | AC | 364 ms | 81800 KB |
1_22.txt | AC | 431 ms | 83468 KB |
1_23.txt | AC | 411 ms | 82960 KB |
1_24.txt | AC | 503 ms | 83464 KB |
1_25.txt | AC | 437 ms | 86648 KB |
1_26.txt | AC | 400 ms | 82044 KB |
1_27.txt | AC | 551 ms | 84856 KB |
1_28.txt | AC | 567 ms | 86776 KB |
1_29.txt | AC | 437 ms | 87816 KB |
2_00.txt | AC | 12 ms | 30208 KB |
2_01.txt | AC | 396 ms | 98704 KB |
2_02.txt | AC | 396 ms | 95760 KB |
2_03.txt | AC | 396 ms | 94864 KB |
2_04.txt | AC | 395 ms | 89616 KB |
2_05.txt | AC | 398 ms | 90000 KB |
2_06.txt | AC | 396 ms | 91408 KB |
2_07.txt | AC | 384 ms | 80524 KB |
2_08.txt | AC | 365 ms | 80528 KB |
2_09.txt | AC | 370 ms | 80528 KB |
2_10.txt | AC | 567 ms | 84728 KB |
2_11.txt | AC | 551 ms | 84728 KB |
2_12.txt | AC | 567 ms | 84728 KB |
2_13.txt | AC | 610 ms | 89076 KB |
2_14.txt | AC | 597 ms | 89076 KB |
2_15.txt | AC | 593 ms | 89844 KB |
2_16.txt | AC | 391 ms | 82192 KB |
2_17.txt | AC | 392 ms | 82192 KB |
2_18.txt | AC | 396 ms | 82192 KB |
2_19.txt | AC | 395 ms | 82320 KB |
2_20.txt | AC | 394 ms | 82320 KB |
2_21.txt | AC | 399 ms | 82320 KB |
2_22.txt | AC | 398 ms | 83596 KB |
2_23.txt | AC | 395 ms | 84496 KB |
2_24.txt | AC | 404 ms | 84240 KB |
2_25.txt | AC | 413 ms | 91536 KB |
2_26.txt | AC | 410 ms | 89616 KB |
2_27.txt | AC | 419 ms | 91404 KB |
2_28.txt | AC | 400 ms | 88456 KB |
2_29.txt | AC | 412 ms | 96264 KB |
2_30.txt | AC | 395 ms | 93960 KB |
2_31.txt | AC | 432 ms | 88200 KB |
2_32.txt | AC | 388 ms | 82696 KB |
2_33.txt | AC | 395 ms | 85520 KB |
2_34.txt | AC | 384 ms | 87432 KB |
2_35.txt | AC | 387 ms | 91016 KB |
2_36.txt | AC | 365 ms | 80140 KB |
2_37.txt | AC | 379 ms | 80780 KB |
2_38.txt | AC | 395 ms | 82952 KB |
2_39.txt | AC | 371 ms | 80660 KB |
2_40.txt | AC | 552 ms | 83832 KB |
2_41.txt | AC | 397 ms | 82184 KB |
2_42.txt | AC | 537 ms | 83704 KB |
2_43.txt | AC | 420 ms | 91156 KB |
2_44.txt | AC | 551 ms | 84856 KB |
2_45.txt | AC | 582 ms | 87412 KB |
2_46.txt | AC | 585 ms | 88568 KB |
2_47.txt | AC | 444 ms | 89080 KB |