Submission #2336232
Source Code Expand
#include<bits/stdc++.h> using namespace std; #define int long long #define rep(i,n) for(int i=0;i<(n);i++) #define pb push_back #define all(v) (v).begin(),(v).end() #define fi first #define se second typedef vector<int>vint; typedef pair<int,int>pint; typedef vector<pint>vpint; template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;} template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;} int N; vint G[222222]; string S; void dfs(int v,int p,int d,vint &dist){ dist[v]=d; for(auto u:G[v]){ if(u==p)continue; dfs(u,v,d+1,dist); } } /* vint lim(N); rep(i,N)lim[i]=max(distS[i],distT[i])-1; rep(i,N)chmin(lim[i],R[i]+1); */ int ans; int R[222222]; int dw[222222]; vint distS,distT; void dfs2(int v,int p){ R[v]=0; dw[v]=INT_MAX; for(auto u:G[v]){ if(u==p)continue; dfs2(u,v); chmax(R[v],R[u]+1); } if(S[v]=='1')dw[v]=0; int lim=max(distS[v],distT[v])-1; chmin(lim,R[v]+1); ans+=max(0ll,lim-dw[v]+1); if(p!=-1)chmin(dw[p],max(dw[v]-1,R[v]+1)); } signed main(){ cin>>N; rep(i,N-1){ int a,b; cin>>a>>b; a--;b--;G[a].pb(b);G[b].pb(a); } cin>>S; distS.resize(N);distT.resize(N); dfs(0,-1,0,distS); int s=0; rep(i,N)if(distS[i]>distS[s])s=i; dfs(s,-1,0,distS); int t=0; rep(i,N)if(distS[i]>distS[t])t=i; dfs(t,-1,0,distT); vint lis; rep(i,N){ if(max(distS[i],distT[i])==(distS[t]+1)/2)lis.pb(i); } if(lis.size()==1){ dfs2(lis[0],-1); } else{ dfs2(lis[0],lis[1]); dfs2(lis[1],lis[0]); } cout<<ans+1<<endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | F - Black Radius |
User | latte0119 |
Language | C++14 (GCC 5.4.1) |
Score | 1900 |
Code Size | 1801 Byte |
Status | AC |
Exec Time | 267 ms |
Memory | 31108 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 | 3 ms | 6912 KB |
0_01.txt | AC | 3 ms | 6912 KB |
0_02.txt | AC | 3 ms | 6912 KB |
1_00.txt | AC | 3 ms | 6912 KB |
1_01.txt | AC | 241 ms | 30980 KB |
1_02.txt | AC | 255 ms | 26756 KB |
1_03.txt | AC | 217 ms | 18564 KB |
1_04.txt | AC | 186 ms | 19316 KB |
1_05.txt | AC | 166 ms | 20208 KB |
1_06.txt | AC | 201 ms | 19716 KB |
1_07.txt | AC | 197 ms | 19716 KB |
1_08.txt | AC | 218 ms | 20868 KB |
1_09.txt | AC | 236 ms | 25732 KB |
1_10.txt | AC | 220 ms | 25988 KB |
1_11.txt | AC | 246 ms | 29188 KB |
1_12.txt | AC | 202 ms | 22148 KB |
1_13.txt | AC | 229 ms | 24324 KB |
1_14.txt | AC | 202 ms | 21252 KB |
1_15.txt | AC | 204 ms | 21380 KB |
1_16.txt | AC | 218 ms | 22916 KB |
1_17.txt | AC | 240 ms | 25348 KB |
1_18.txt | AC | 225 ms | 18820 KB |
1_19.txt | AC | 206 ms | 19204 KB |
1_20.txt | AC | 249 ms | 18692 KB |
1_21.txt | AC | 213 ms | 19332 KB |
1_22.txt | AC | 187 ms | 19448 KB |
1_23.txt | AC | 185 ms | 19576 KB |
1_24.txt | AC | 198 ms | 20612 KB |
1_25.txt | AC | 191 ms | 20980 KB |
1_26.txt | AC | 195 ms | 19448 KB |
1_27.txt | AC | 192 ms | 19828 KB |
1_28.txt | AC | 186 ms | 20340 KB |
1_29.txt | AC | 209 ms | 23800 KB |
2_00.txt | AC | 3 ms | 6912 KB |
2_01.txt | AC | 267 ms | 30980 KB |
2_02.txt | AC | 232 ms | 31108 KB |
2_03.txt | AC | 225 ms | 30980 KB |
2_04.txt | AC | 244 ms | 26756 KB |
2_05.txt | AC | 245 ms | 26756 KB |
2_06.txt | AC | 254 ms | 26756 KB |
2_07.txt | AC | 216 ms | 18564 KB |
2_08.txt | AC | 226 ms | 18564 KB |
2_09.txt | AC | 216 ms | 18564 KB |
2_10.txt | AC | 181 ms | 19316 KB |
2_11.txt | AC | 189 ms | 19316 KB |
2_12.txt | AC | 196 ms | 19316 KB |
2_13.txt | AC | 172 ms | 20208 KB |
2_14.txt | AC | 161 ms | 20208 KB |
2_15.txt | AC | 158 ms | 20208 KB |
2_16.txt | AC | 203 ms | 19716 KB |
2_17.txt | AC | 202 ms | 19716 KB |
2_18.txt | AC | 197 ms | 19716 KB |
2_19.txt | AC | 206 ms | 19716 KB |
2_20.txt | AC | 200 ms | 19716 KB |
2_21.txt | AC | 212 ms | 19716 KB |
2_22.txt | AC | 203 ms | 20868 KB |
2_23.txt | AC | 230 ms | 20868 KB |
2_24.txt | AC | 206 ms | 20868 KB |
2_25.txt | AC | 224 ms | 25732 KB |
2_26.txt | AC | 234 ms | 25732 KB |
2_27.txt | AC | 247 ms | 25732 KB |
2_28.txt | AC | 211 ms | 24196 KB |
2_29.txt | AC | 253 ms | 30340 KB |
2_30.txt | AC | 243 ms | 26628 KB |
2_31.txt | AC | 238 ms | 25860 KB |
2_32.txt | AC | 197 ms | 20100 KB |
2_33.txt | AC | 212 ms | 21508 KB |
2_34.txt | AC | 209 ms | 22916 KB |
2_35.txt | AC | 246 ms | 25604 KB |
2_36.txt | AC | 221 ms | 18564 KB |
2_37.txt | AC | 216 ms | 18820 KB |
2_38.txt | AC | 209 ms | 20100 KB |
2_39.txt | AC | 245 ms | 18692 KB |
2_40.txt | AC | 194 ms | 19444 KB |
2_41.txt | AC | 193 ms | 19456 KB |
2_42.txt | AC | 185 ms | 19188 KB |
2_43.txt | AC | 210 ms | 24060 KB |
2_44.txt | AC | 177 ms | 19832 KB |
2_45.txt | AC | 170 ms | 19952 KB |
2_46.txt | AC | 178 ms | 20208 KB |
2_47.txt | AC | 194 ms | 23412 KB |