Submission #1045330
Source Code Expand
#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <limits>
#include <memory>
#include <queue>
#include <sstream>
#include <string>
#include <vector>
using namespace std;
#define all(a) (a).begin(), (a).end()
#define sz(a) static_cast<int>((a).size())
#define fillchar(a, x) memset(a, x, sizeof(a))
#define rep(i, a, b) for(int i=int(a); i<=int(b); ++i)
#define irep(i, a, b) for(int i=int(a); i>=int(b); --i)
#define replr(i, a, b) rep(i, a, (b)-1)
#define reprl(i, a, b) irep(i, (b)-1, a)
#define repn(i, n) rep(i, 0, (n)-1)
#define irepn(i, n) irep(i, (n)-1, 0)
#define fi first
#define se second
#define pb push_back
#define mp make_pair
typedef long long LL;
typedef pair<LL,LL> PLL;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
typedef vector<LL> VL;
typedef vector<int> VI;
typedef vector<PII> VPI;
typedef vector<string> VS;
template<class T, class S> ostream& operator<<(ostream& os, const pair<T, S>& v) { return os<<"("<<v.first<<", "<<v.second<<")"; }
template<class T> ostream& operator<<(ostream& os, const vector<T>& v) { os<<"["; repn(i, sz(v)) { if(i) os<<", "; os<<v[i]; } return os<<"]"; }
template<class T> bool setmax(T &_a, T _b) { if(_b>_a) { _a=_b; return true; } return false; }
template<class T> bool setmin(T &_a, T _b) { if(_b<_a) { _a=_b; return true; } return false; }
template<class T> T gcd(T _a, T _b) { return _b==0?_a:gcd(_b,_a%_b); }
const int N=200000;
VI es[N];
bool liked[N];
int n;
LL ans;
PII f[N];
PII merge(PII a, PII b) {
PII c;
c.fi=max(a.fi, b.fi);
c.se=a.se|b.se;
return c;
}
void dfs(int x, int fa) {
f[x]=mp(0, liked[x]);
for(int y: es[x]) if(y!=fa) {
dfs(y, x);
f[x]=merge(f[x], f[y]);
}
++f[x].fi;
}
void dfs2(int x, int fa, PII top) {
VI ys;
for(int y: es[x]) if(y!=fa) ys.pb(y);
vector<PII> l(sz(ys)+1), r(sz(ys)+1);
repn(i, sz(ys)) l[i+1]=merge(l[i], f[ys[i]]);
irepn(i, sz(ys)) r[i]=merge(r[i+1], f[ys[i]]);
repn(i, sz(ys)) {
PII tmp=merge(top, merge(l[i], r[i+1]));
if(liked[x]) tmp.se=1;
++tmp.fi;
dfs2(ys[i], x, tmp);
}
VPI vs;
for(int y: es[x]) {
vs.pb(y==fa ? top : f[y]);
}
sort(all(vs), greater<PII>());
if(!vs.empty()) {
int ubound=min(vs[0].fi-1, sz(vs)>1 ? vs[1].fi+1 : 1);
int lbound=0;
if(!liked[x]) {
int i=sz(vs)-1;
while(i>=0 && !vs[i].se) --i;
if(i>=0) lbound=vs[i].fi;
else lbound=ubound+1;
}
if(lbound<=ubound) {
ans+=ubound-lbound+1;
}
}
}
int main() {
scanf("%d", &n);
repn(i, n-1) {
int a, b; scanf("%d%d", &a,&b);
--a, --b;
es[a].pb(b), es[b].pb(a);
}
static char buf[N+1];
scanf("%s", buf);
repn(i, n) {
liked[i]=(buf[i]=='1');
}
dfs(0, -1);
ans=0;
dfs2(0, -1, mp(0, 0));
if(count(liked, liked+n, true)>0) ++ans;
cout<<ans<<endl;
return 0;
}
Submission Info
Submission Time
2016-12-26 15:22:52+0900
Task
F - Black Radius
User
fqw
Language
C++14 (GCC 5.4.1)
Score
1900
Code Size
3194 Byte
Status
AC
Exec Time
330 ms
Memory
53632 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:102:20: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
^
./Main.cpp:104:39: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
int a, b; scanf("%d%d", &a,&b);
^
./Main.cpp:109:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%s", buf);
^
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
9 ms
4992 KB
0_01.txt
AC
9 ms
4992 KB
0_02.txt
AC
9 ms
4992 KB
1_00.txt
AC
9 ms
4992 KB
1_01.txt
AC
330 ms
53632 KB
1_02.txt
AC
261 ms
39296 KB
1_03.txt
AC
172 ms
13312 KB
1_04.txt
AC
164 ms
16632 KB
1_05.txt
AC
148 ms
19956 KB
1_06.txt
AC
168 ms
13312 KB
1_07.txt
AC
159 ms
13440 KB
1_08.txt
AC
187 ms
17152 KB
1_09.txt
AC
242 ms
33792 KB
1_10.txt
AC
245 ms
30592 KB
1_11.txt
AC
283 ms
53376 KB
1_12.txt
AC
195 ms
22784 KB
1_13.txt
AC
234 ms
32256 KB
1_14.txt
AC
187 ms
21376 KB
1_15.txt
AC
175 ms
17664 KB
1_16.txt
AC
218 ms
24448 KB
1_17.txt
AC
245 ms
29184 KB
1_18.txt
AC
158 ms
13312 KB
1_19.txt
AC
161 ms
13312 KB
1_20.txt
AC
168 ms
13696 KB
1_21.txt
AC
186 ms
16000 KB
1_22.txt
AC
162 ms
15356 KB
1_23.txt
AC
154 ms
14972 KB
1_24.txt
AC
182 ms
16628 KB
1_25.txt
AC
182 ms
21240 KB
1_26.txt
AC
153 ms
14844 KB
1_27.txt
AC
148 ms
16504 KB
1_28.txt
AC
143 ms
18084 KB
1_29.txt
AC
198 ms
22652 KB
2_00.txt
AC
9 ms
4992 KB
2_01.txt
AC
311 ms
51968 KB
2_02.txt
AC
303 ms
45696 KB
2_03.txt
AC
316 ms
43648 KB
2_04.txt
AC
312 ms
32768 KB
2_05.txt
AC
279 ms
33408 KB
2_06.txt
AC
265 ms
36352 KB
2_07.txt
AC
186 ms
13312 KB
2_08.txt
AC
195 ms
13312 KB
2_09.txt
AC
190 ms
13312 KB
2_10.txt
AC
166 ms
16632 KB
2_11.txt
AC
165 ms
16632 KB
2_12.txt
AC
172 ms
16632 KB
2_13.txt
AC
127 ms
19956 KB
2_14.txt
AC
125 ms
19956 KB
2_15.txt
AC
126 ms
19956 KB
2_16.txt
AC
164 ms
13312 KB
2_17.txt
AC
167 ms
13312 KB
2_18.txt
AC
161 ms
13312 KB
2_19.txt
AC
172 ms
13440 KB
2_20.txt
AC
174 ms
13440 KB
2_21.txt
AC
166 ms
13440 KB
2_22.txt
AC
203 ms
16640 KB
2_23.txt
AC
185 ms
18944 KB
2_24.txt
AC
188 ms
18176 KB
2_25.txt
AC
260 ms
35328 KB
2_26.txt
AC
235 ms
31104 KB
2_27.txt
AC
245 ms
35072 KB
2_28.txt
AC
215 ms
28928 KB
2_29.txt
AC
292 ms
47104 KB
2_30.txt
AC
258 ms
41344 KB
2_31.txt
AC
264 ms
29312 KB
2_32.txt
AC
164 ms
14592 KB
2_33.txt
AC
187 ms
21888 KB
2_34.txt
AC
212 ms
28032 KB
2_35.txt
AC
244 ms
37632 KB
2_36.txt
AC
187 ms
13184 KB
2_37.txt
AC
174 ms
13312 KB
2_38.txt
AC
186 ms
17536 KB
2_39.txt
AC
170 ms
13952 KB
2_40.txt
AC
166 ms
15992 KB
2_41.txt
AC
157 ms
14208 KB
2_42.txt
AC
145 ms
16504 KB
2_43.txt
AC
242 ms
33280 KB
2_44.txt
AC
171 ms
16632 KB
2_45.txt
AC
136 ms
19068 KB
2_46.txt
AC
138 ms
19572 KB
2_47.txt
AC
214 ms
25136 KB