Submission #1690987
Source Code Expand
#include"bits/stdc++.h" #define PB push_back #define PF push_front #define LB lower_bound #define UB upper_bound #define fr(x) freopen(x,"r",stdin) #define fw(x) freopen(x,"w",stdout) #define iout(x) printf("%d\n",x) #define lout(x) printf("%lld\n",x) #define REP(x,l,u) for(ll x = (l);x<=(u);x++) #define RREP(x,l,u) for(ll x = (l);x>=(u);x--) #define mst(x,a) memset(x,a,sizeof(x)) #define PII pair<int,int> #define PLL pair<ll,ll> #define MP make_pair #define se second #define fi first #define dbg(x) cout<<#x<<" = "<<(x)<<endl; #define sz(x) ((int)x.size()) #define cl(x) x.clear() typedef long long ll; typedef unsigned long long ull; typedef double db; typedef long double ld; using namespace std; const int maxn = 200010; const int mod = 1e9+7; const double eps = 1e-6; const double PI = acos(-1); template<typename T> inline void read(T &x){ x=0;T f=1;char ch;do{ch=getchar();if(ch=='-')f=-1;}while(ch<'0'||ch>'9');do x=x*10+ch-'0',ch=getchar();while(ch<='9'&&ch>='0');x*=f; } template<typename A,typename B> inline void read(A&x,B&y){read(x);read(y);} template<typename A,typename B,typename C> inline void read(A&x,B&y,C&z){read(x);read(y);read(z);} template<typename A,typename B,typename C,typename D> inline void read(A&x,B&y,C&z,D&w){read(x);read(y);read(z);read(w);} template<typename A,typename B> inline A fexp(A x,B p){A ans=1;for(;p;p>>=1,x=1LL*x*x%mod)if(p&1)ans=1LL*ans*x%mod;return ans;} template<typename A,typename B> inline A fexp(A x,B p,A mo){A ans=1;for(;p;p>>=1,x=1LL*x*x%mo)if(p&1)ans=1LL*ans*x%mo;return ans;} int n; char st[maxn]; vector<int> G[maxn]; int f[maxn],g[maxn],low[maxn],high[maxn]; void dfs1(int u,int fa){ low[u]=st[u]=='1'?0:n; for(auto v:G[u])if(v!=fa){ dfs1(v,u); f[u]=max(f[u],f[v]+1); low[u]=min(low[u],max(low[v],f[v])+1);//move down and touch the bottom } } void dfs2(int u,int fa){ int mx=g[u],se=0; for(auto v:G[u])if(v!=fa){ se=max(se,f[v]+1); if(se>mx)swap(mx,se); } high[u]=min(se+1,max(f[u],g[u])-1); for(auto v:G[u])if(v!=fa){ if(f[v]==mx-1)g[v]=se+1,low[v]=min(low[v],max(low[u],se)+1); else g[v]=mx+1,low[v]=min(low[v],max(low[u],mx)+1); dfs2(v,u); } } void Work(){ dfs1(1,0); dfs2(1,0); ll ans=0; REP(i,1,n)ans+=max(0,high[i]-low[i]+1); cout<<ans+1<<endl; } void Init(){ read(n); REP(i,2,n){ int u,v;read(u,v); G[u].PB(v);G[v].PB(u); } scanf("%s",st+1); } int main(){ Init(); Work(); return 0; }
Submission Info
Submission Time | |
---|---|
Task | F - Black Radius |
User | yanQval |
Language | C++14 (GCC 5.4.1) |
Score | 1900 |
Code Size | 2513 Byte |
Status | AC |
Exec Time | 110 ms |
Memory | 26368 KB |
Compile Error
./Main.cpp: In function ‘void Init()’: ./Main.cpp:90:18: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%s",st+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 | 3 ms | 6016 KB |
0_01.txt | AC | 3 ms | 6016 KB |
0_02.txt | AC | 3 ms | 6016 KB |
1_00.txt | AC | 3 ms | 6016 KB |
1_01.txt | AC | 106 ms | 26368 KB |
1_02.txt | AC | 94 ms | 22144 KB |
1_03.txt | AC | 82 ms | 14592 KB |
1_04.txt | AC | 71 ms | 14840 KB |
1_05.txt | AC | 50 ms | 15348 KB |
1_06.txt | AC | 78 ms | 14720 KB |
1_07.txt | AC | 78 ms | 14720 KB |
1_08.txt | AC | 80 ms | 15744 KB |
1_09.txt | AC | 87 ms | 20480 KB |
1_10.txt | AC | 85 ms | 19584 KB |
1_11.txt | AC | 96 ms | 26240 KB |
1_12.txt | AC | 77 ms | 17152 KB |
1_13.txt | AC | 93 ms | 20096 KB |
1_14.txt | AC | 79 ms | 17024 KB |
1_15.txt | AC | 88 ms | 15872 KB |
1_16.txt | AC | 99 ms | 17920 KB |
1_17.txt | AC | 95 ms | 19200 KB |
1_18.txt | AC | 80 ms | 14592 KB |
1_19.txt | AC | 75 ms | 14592 KB |
1_20.txt | AC | 80 ms | 14592 KB |
1_21.txt | AC | 82 ms | 15360 KB |
1_22.txt | AC | 70 ms | 14844 KB |
1_23.txt | AC | 80 ms | 14716 KB |
1_24.txt | AC | 77 ms | 15488 KB |
1_25.txt | AC | 74 ms | 16632 KB |
1_26.txt | AC | 75 ms | 14588 KB |
1_27.txt | AC | 67 ms | 14968 KB |
1_28.txt | AC | 64 ms | 15352 KB |
1_29.txt | AC | 79 ms | 17404 KB |
2_00.txt | AC | 3 ms | 6016 KB |
2_01.txt | AC | 110 ms | 25856 KB |
2_02.txt | AC | 93 ms | 24064 KB |
2_03.txt | AC | 97 ms | 23552 KB |
2_04.txt | AC | 96 ms | 20352 KB |
2_05.txt | AC | 89 ms | 20480 KB |
2_06.txt | AC | 91 ms | 21376 KB |
2_07.txt | AC | 84 ms | 14592 KB |
2_08.txt | AC | 82 ms | 14592 KB |
2_09.txt | AC | 83 ms | 14592 KB |
2_10.txt | AC | 71 ms | 14840 KB |
2_11.txt | AC | 87 ms | 14840 KB |
2_12.txt | AC | 82 ms | 14840 KB |
2_13.txt | AC | 62 ms | 15348 KB |
2_14.txt | AC | 52 ms | 15348 KB |
2_15.txt | AC | 50 ms | 15348 KB |
2_16.txt | AC | 82 ms | 14720 KB |
2_17.txt | AC | 98 ms | 14720 KB |
2_18.txt | AC | 84 ms | 14720 KB |
2_19.txt | AC | 83 ms | 14720 KB |
2_20.txt | AC | 82 ms | 14720 KB |
2_21.txt | AC | 83 ms | 14720 KB |
2_22.txt | AC | 78 ms | 15616 KB |
2_23.txt | AC | 81 ms | 16128 KB |
2_24.txt | AC | 80 ms | 16000 KB |
2_25.txt | AC | 95 ms | 20992 KB |
2_26.txt | AC | 87 ms | 19712 KB |
2_27.txt | AC | 84 ms | 20864 KB |
2_28.txt | AC | 88 ms | 19200 KB |
2_29.txt | AC | 93 ms | 24448 KB |
2_30.txt | AC | 87 ms | 22784 KB |
2_31.txt | AC | 83 ms | 19200 KB |
2_32.txt | AC | 82 ms | 15104 KB |
2_33.txt | AC | 82 ms | 17152 KB |
2_34.txt | AC | 82 ms | 18816 KB |
2_35.txt | AC | 99 ms | 21632 KB |
2_36.txt | AC | 85 ms | 14464 KB |
2_37.txt | AC | 82 ms | 14592 KB |
2_38.txt | AC | 83 ms | 15744 KB |
2_39.txt | AC | 81 ms | 14720 KB |
2_40.txt | AC | 69 ms | 14840 KB |
2_41.txt | AC | 75 ms | 14720 KB |
2_42.txt | AC | 63 ms | 14712 KB |
2_43.txt | AC | 91 ms | 20224 KB |
2_44.txt | AC | 65 ms | 14840 KB |
2_45.txt | AC | 56 ms | 15096 KB |
2_46.txt | AC | 58 ms | 15348 KB |
2_47.txt | AC | 72 ms | 18168 KB |