QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #85925 | #5659. Watching Cowflix | Bird | 12.5 | 137ms | 37496kb | C++14 | 2.2kb | 2023-03-08 21:17:44 | 2023-03-08 21:17:47 |
Judging History
answer
#include<bits/stdc++.h>
#include<queue>
#define N 200000
using namespace std;
const int inf=1e9;
int n,deep[N+5],dfn[N+5],edfn[N+5],f[N+5][18],fa[N+5],st[N+5],top,ans,dp[N+5][2],k;
bool vis[N+5];
vector<int> e[N+5],v,now,E[N+5];
char s[N+5];
inline void dfs(int x,int fa)
{
static int tot;
deep[x]=deep[fa]+1,dfn[x]=++tot,f[x][0]=fa;
for(int i=1;i<18;++i) f[x][i]=f[f[x][i-1]][i-1];
for(int y:e[x]) if(y!=fa) dfs(y,x);
edfn[x]=tot;
}
inline int lca(int u,int v)
{
if(deep[u]<deep[v]) swap(u,v);
for(int i=17,k=deep[u]-deep[v];~i;--i) if(k>>i&1) u=f[u][i];
if(u==v) return u;
for(int i=17;~i;--i) if(f[u][i]!=f[v][i]) u=f[u][i],v=f[v][i];
return f[u][0];
}
inline void dfs1(int x,bool p)
{
s[x]='0'^p,vis[x]=s[x]=='1' && s[fa[x]]=='1' && deep[x]-deep[fa[x]]-1<=k;
for(int y:E[x])
{
if(p==1) dp[y][1]+=min(0,deep[y]-deep[x]-1-k);
dfs1(y,dp[y][1]<=dp[y][0]);
}
}
int main()
{
scanf("%d %s",&n,s+1);
for(int i=1,u,v;i<n;++i)
{
scanf("%d %d",&u,&v);
e[u].push_back(v);
e[v].push_back(u);
}
for(int i=1;i<=n;++i) if(s[i]=='1') v.push_back(i),++ans;
if(v.empty())
{
for(int i=1;i<=n;++i) puts("0");
return 0;
}
dfs(1,0);
sort(v.begin(),v.end(),[&](int a,int b) {return dfn[a]<dfn[b];});
for(int i=(int)v.size()-1;i;--i) v.push_back(lca(v[i-1],v[i]));
sort(v.begin(),v.end(),[&](int a,int b) {return dfn[a]<dfn[b];});
v.erase(unique(v.begin(),v.end()),v.end());
for(int x:v)
{
while(top && edfn[st[top]]<dfn[x]) --top;
if(top) E[fa[x]=st[top]].push_back(x);
st[++top]=x;
}
now=v,reverse(now.begin(),now.end());
for(k=1;k<=n;++k)
{
vector<int> root,nxt;
for(int x:now)
if(s[x]=='0') dp[x][0]=0,dp[x][1]=k+1;
else dp[x][0]=inf,dp[x][1]=1;
for(int x:now)
if(!fa[x] || s[fa[x]]=='1') root.push_back(x);
else dp[fa[x]][0]+=min(dp[x][0],dp[x][1]),
dp[fa[x]][1]+=min(dp[x][0],dp[x][1]+min(0,deep[x]-deep[fa[x]]-1-k));
for(int x:root)
{
if(fa[x]) dp[x][1]+=min(0,deep[x]-deep[fa[x]]-1-k);
ans+=min(dp[x][0],dp[x][1]);
dfs1(x,dp[x][1]<=dp[x][0]);
}
for(int x:now) if(!vis[x]) nxt.push_back(x);
now=nxt;
printf("%d\n",ans);
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 4.16667
Accepted
time: 4ms
memory: 13040kb
input:
5 10001 1 2 2 3 3 4 4 5
output:
4 6 8 9 10
result:
ok 5 number(s): "4 6 8 9 10"
Test #2:
score: 4.16667
Accepted
time: 2ms
memory: 12992kb
input:
7 0001010 7 4 5 6 7 2 5 1 6 3 2 5
output:
4 6 8 9 10 11 12
result:
ok 7 numbers
Test #3:
score: 0
Wrong Answer
time: 25ms
memory: 13852kb
input:
5000 0100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000000000000000000000000000000000000000000000010000000...
output:
711 836 943 1039 1118 1187 1244 1294 1341 1384 1425 1465 1504 1543 1582 1620 1657 1693 1728 1761 1793 1825 1857 1888 1918 1947 1976 2004 2032 2059 2085 2111 2136 2160 2183 2206 2228 2250 2272 2294 2315 2335 2354 2372 2390 2408 2425 2442 2458 2473 2488 2502 2515 2527 2538 2549 2559 2569 2579 2589 259...
result:
wrong answer 2nd numbers differ - expected: '837', found: '836'
Test #4:
score: 0
Wrong Answer
time: 39ms
memory: 13924kb
input:
5000 0100000000000000000000000000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010000000000000000000000000000000000000000000000000000000000000000000...
output:
890 1226 1422 1534 1604 1661 1712 1760 1806 1850 1893 1935 1974 2012 2049 2085 2121 2156 2191 2225 2258 2290 2321 2351 2380 2409 2437 2464 2491 2517 2542 2566 2589 2611 2633 2655 2676 2696 2715 2734 2753 2771 2789 2806 2822 2838 2854 2869 2883 2896 2908 2919 2929 2938 2947 2956 2965 2973 2980 2986 2...
result:
wrong answer 3rd numbers differ - expected: '1433', found: '1422'
Test #5:
score: 0
Wrong Answer
time: 31ms
memory: 13832kb
input:
5000 0100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000000000000000000000000000000000000000000000000000000000000001000000000000000001000000000000000000000000000000000000000000000000...
output:
794 1022 1175 1277 1345 1398 1449 1493 1535 1576 1616 1655 1693 1730 1766 1802 1837 1871 1904 1936 1968 2000 2032 2064 2095 2126 2157 2187 2217 2246 2274 2301 2327 2352 2377 2401 2424 2447 2469 2491 2512 2532 2551 2570 2588 2605 2621 2636 2650 2664 2677 2689 2700 2710 2719 2727 2735 2742 2748 2753 2...
result:
wrong answer 2nd numbers differ - expected: '1025', found: '1022'
Test #6:
score: 0
Time Limit Exceeded
input:
200000 01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
result:
Test #7:
score: 0
Time Limit Exceeded
input:
200000 01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
result:
Test #8:
score: 0
Time Limit Exceeded
input:
200000 01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
result:
Test #9:
score: 0
Time Limit Exceeded
input:
100000 01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
12231 13860 15148 16183 17002 17655 18214 18696 19102 19456 19775 20072 20347 20606 20851 21087 21314 21532 21742 21949 22148 22345 22538 22729 22917 23102 23284 23464 23643 23820 23995 24169 24342 24513 24684 24855 25025 25195 25364 25532 25700 25867 26033 26199 26364 26529 26694 26858 27021 27184 ...
result:
Test #10:
score: 0
Time Limit Exceeded
input:
100000 01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
15993 21806 24974 26419 27202 27701 28065 28351 28594 28810 29016 29217 29414 29607 29798 29987 30176 30364 30550 30735 30920 31104 31287 31470 31652 31833 32013 32192 32371 32549 32726 32902 33077 33251 33424 33596 33767 33937 34106 34275 34444 34613 34781 34949 35116 35283 35449 35614 35779 35944 ...
result:
Test #11:
score: 0
Time Limit Exceeded
input:
100000 01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
14608 18444 21205 22991 23778 24191 24497 24733 24939 25133 25321 25507 25692 25877 26062 26246 26430 26614 26797 26980 27163 27346 27528 27710 27891 28072 28252 28432 28612 28791 28969 29147 29324 29501 29677 29852 30027 30202 30377 30551 30724 30896 31068 31239 31410 31581 31751 31920 32088 32256 ...
result:
Test #12:
score: 0
Time Limit Exceeded
input:
100000 01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
12198 13813 15081 16124 16978 17662 18240 18733 19155 19543 19898 20226 20527 20815 21087 21347 21601 21847 22086 22318 22549 22776 23001 23224 23444 23661 23875 24088 24298 24506 24713 24920 25124 25328 25531 25733 25934 26134 26333 26532 26731 26930 27129 27327 27524 27721 27917 28112 28306 28500 ...
result:
Test #13:
score: 0
Time Limit Exceeded
input:
100000 01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
16072 21895 25013 26500 27330 27832 28203 28499 28755 28985 29198 29405 29605 29802 29997 30192 30386 30579 30771 30962 31152 31341 31529 31717 31904 32090 32276 32461 32645 32829 33012 33194 33375 33555 33735 33914 34092 34269 34445 34620 34795 34969 35143 35317 35491 35664 35836 36007 36177 36346 ...
result:
Test #14:
score: 0
Time Limit Exceeded
input:
100000 01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
14721 18667 21478 23280 24154 24648 24990 25263 25502 25727 25944 26159 26373 26586 26798 27009 27219 27429 27638 27846 28053 28260 28466 28671 28876 29080 29283 29485 29686 29886 30085 30283 30480 30676 30872 31068 31264 31459 31653 31846 32039 32231 32422 32613 32803 32993 33182 33370 33557 33744 ...
result:
Test #15:
score: 0
Time Limit Exceeded
input:
100000 01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
12121 13751 15052 16070 16874 17540 18087 18556 18962 19327 19660 19965 20252 20511 20755 20990 21220 21441 21657 21869 22077 22281 22480 22676 22870 23058 23243 23426 23609 23790 23969 24147 24324 24500 24676 24852 25027 25201 25374 25546 25717 25887 26057 26227 26396 26564 26732 26899 27066 27232 ...
result:
Test #16:
score: 0
Time Limit Exceeded
input:
100000 01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
16192 22044 25126 26594 27412 27894 28249 28526 28771 28991 29199 29401 29596 29790 29980 30169 30356 30543 30730 30917 31102 31286 31469 31651 31832 32012 32191 32369 32547 32724 32901 33078 33255 33431 33607 33782 33956 34129 34301 34472 34643 34814 34984 35153 35321 35488 35654 35819 35983 36146 ...
result:
Test #17:
score: 0
Time Limit Exceeded
input:
100000 01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
14705 18631 21402 23190 24070 24558 24916 25198 25453 25698 25940 26181 26422 26662 26902 27141 27380 27618 27855 28091 28326 28561 28795 29028 29261 29493 29724 29954 30184 30413 30642 30870 31097 31323 31548 31772 31996 32219 32441 32662 32882 33102 33321 33540 33758 33976 34193 34409 34624 34838 ...
result:
Test #18:
score: 0
Time Limit Exceeded
input:
100000 01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
12282 13869 15131 16178 17003 17668 18232 18711 19131 19501 19834 20136 20414 20671 20916 21150 21372 21583 21791 21998 22202 22401 22598 22791 22983 23171 23358 23543 23725 23906 24084 24260 24435 24610 24783 24955 25126 25296 25466 25636 25806 25975 26143 26310 26476 26641 26805 26969 27132 27294 ...
result:
Test #19:
score: 4.16667
Accepted
time: 63ms
memory: 25780kb
input:
100000 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
6 9 12 15 18 21 24 27 30 33 36 39 42 45 48 51 54 57 60 63 66 69 72 75 78 81 84 87 90 93 96 99 102 105 108 111 114 117 120 123 126 129 132 135 138 141 144 147 150 153 156 159 162 165 168 171 174 177 180 183 186 189 192 195 198 201 204 207 210 213 216 219 222 225 228 231 234 237 240 243 246 249 252 25...
result:
ok 100000 numbers
Test #20:
score: 0
Time Limit Exceeded
input:
200000 01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
32208 43696 49713 52520 53998 54886 55513 55976 56358 56691 57001 57294 57579 57856 58127 58394 58660 58925 59190 59455 59720 59984 60247 60509 60771 61032 61292 61551 61809 62066 62322 62577 62831 63085 63338 63590 63841 64091 64340 64589 64837 65084 65331 65578 65824 66069 66313 66556 66798 67039 ...
result:
Test #21:
score: 0
Time Limit Exceeded
input:
200000 01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
29187 37000 42415 45938 47448 48238 48758 49142 49465 49759 50040 50318 50594 50869 51142 51415 51687 51958 52229 52500 52771 53041 53311 53581 53851 54121 54390 54659 54927 55194 55460 55725 55990 56254 56517 56779 57041 57303 57565 57826 58086 58346 58605 58863 59120 59377 59633 59888 60143 60398 ...
result:
Test #22:
score: 0
Time Limit Exceeded
input:
200000 01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
24124 27216 29570 31464 32986 34215 35228 36084 36829 37487 38057 38553 39004 39434 39835 40216 40580 40928 41259 41578 41886 42186 42482 42774 43062 43346 43623 43898 44172 44443 44711 44978 45244 45508 45772 46035 46298 46560 46822 47083 47344 47604 47863 48122 48380 48638 48895 49151 49407 49662 ...
result:
Test #23:
score: 0
Time Limit Exceeded
input:
200000 01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
32229 43868 49981 52833 54293 55151 55732 56171 56548 56889 57198 57493 57774 58047 58318 58587 58856 59125 59393 59660 59926 60191 60455 60719 60983 61247 61510 61772 62034 62295 62556 62816 63075 63334 63592 63849 64106 64362 64618 64873 65127 65380 65632 65883 66133 66382 66630 66877 67124 67370 ...
result:
Test #24:
score: 0
Wrong Answer
time: 137ms
memory: 37496kb
input:
200000 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
6 9 12 15 18 21 24 27 30 33 36 39 42 45 48 51 54 57 60 63 66 69 72 75 78 81 84 87 90 93 96 99 102 105 108 111 114 117 120 123 126 129 132 135 138 141 144 147 150 153 156 159 162 165 168 171 174 177 180 183 186 189 192 195 198 201 204 207 210 213 216 219 222 225 228 231 234 237 240 243 246 249 252 25...
result:
wrong answer 6239th numbers differ - expected: '18720', found: '18719'