QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#86019 | #5659. Watching Cowflix | AFewSuns | 16.666667 | 125ms | 24444kb | C++14 | 4.2kb | 2023-03-09 07:53:01 | 2023-03-09 07:53:04 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
namespace my_std{
#define ll long long
#define bl bool
ll my_pow(ll a,ll b,ll mod){
ll res=1;
if(!b) return 1;
while(b){
if(b&1) res=(res*a)%mod;
a=(a*a)%mod;
b>>=1;
}
return res;
}
ll qpow(ll a,ll b){
ll res=1;
if(!b) return 1;
while(b){
if(b&1) res*=a;
a*=a;
b>>=1;
}
return res;
}
#define db double
#define pf printf
#define pc putchar
#define fr(i,x,y) for(register ll i=(x);i<=(y);i++)
#define pfr(i,x,y) for(register ll i=(x);i>=(y);i--)
#define go(u) for(ll i=head[u];i;i=e[i].nxt)
#define enter pc('\n')
#define space pc(' ')
#define fir first
#define sec second
#define MP make_pair
#define il inline
#define inf 1e9
#define random(x) rand()*rand()%(x)
#define inv(a,mod) my_pow((a),(mod-2),(mod))
il ll read(){
ll sum=0,f=1;
char ch=0;
while(!isdigit(ch)){
if(ch=='-') f=-1;
ch=getchar();
}
while(isdigit(ch)){
sum=sum*10+(ch^48);
ch=getchar();
}
return sum*f;
}
il void write(ll x){
if(x<0){
x=-x;
pc('-');
}
if(x>9) write(x/10);
pc(x%10+'0');
}
il void writeln(ll x){
write(x);
enter;
}
il void writesp(ll x){
write(x);
space;
}
}
using namespace my_std;
vector<ll> vec[200020];
ll n,fa[200020],son[200020],pre[200020],suf[200020],w[200020];
ll siz[200020],st[200020],top=0,dp[200020][2];
char s[200020];
bl ck[200020];
void dfs0(ll u){
ll lst=0;
siz[u]=1;
fr(i,0,(ll)vec[u].size()-1){
ll v=vec[u][i];
if(v==fa[u]) continue;
fa[v]=u;
if(lst){
pre[v]=lst;
suf[lst]=v;
}
else son[u]=v;
dfs0(v);
lst=v;
}
}
void del(ll u,ll v){
if(son[u]==v) son[u]=suf[v];
if(pre[v]) suf[pre[v]]=suf[v];
if(suf[v]) pre[suf[v]]=pre[v];
}
void ins(ll u,ll v){
pre[son[u]]=v;
suf[v]=son[u];
pre[v]=0;
son[u]=v;
fa[v]=u;
}
void cut(ll u){
for(ll v=son[u];v;v=suf[v]){
cut(v);
if(ck[v]) continue;
if(!son[v]||!suf[son[v]]){
ll vv=son[v];
del(u,v);
if(vv){
ins(u,vv);
w[vv]+=w[v]+siz[v];
}
}
}
}
void dfs1(ll u,ll k){
dp[u][0]=dp[u][1]=inf;
ll sum0=0,sum1=0,minn=inf;
for(ll v=son[u];v;v=suf[v]){
dfs1(v,k);
ll tmp=min(dp[v][0],dp[v][1]);
sum0+=tmp;
if((dp[v][1]+w[v]-k)<=tmp) sum1+=dp[v][1]+w[v]-tmp-k;
minn=min(minn,dp[v][1]+w[v]-tmp-k);
}
dp[u][0]=sum0;
dp[u][1]=sum0+siz[u]+k;
if(minn<=0) dp[u][1]=min(dp[u][1],sum0+sum1+siz[u]+k);
else dp[u][1]=min(dp[u][1],sum0+minn+siz[u]+k);
if(ck[u]) dp[u][0]=inf;
}
void dfs2(ll u,ll col,ll k){
ll sum0=0,sum1=0,minn=inf,pos;
for(ll v=son[u];v;v=suf[v]){
ll tmp=min(dp[v][0],dp[v][1]);
sum0+=tmp;
if((dp[v][1]+w[v]-k)<=tmp) sum1+=dp[v][1]+w[v]-tmp-k;
if(minn>(dp[v][1]+w[v]-tmp-k)){
minn=dp[v][1]+w[v]-tmp-k;
pos=v;
}
}
if(!col){
for(ll v=son[u];v;v=suf[v]){
if(dp[v][0]<=dp[v][1]) dfs2(v,0,k);
else dfs2(v,1,k);
}
}
else{
if(dp[u][1]==(sum0+siz[u]+k)){
for(ll v=son[u];v;v=suf[v]){
if(dp[v][0]<=dp[v][1]) dfs2(v,0,k);
else dfs2(v,1,k);
}
}
else if(minn<=0){
for(ll v=son[u];v;v=suf[v]){
ll tmp=min(dp[v][0],dp[v][1]);
if((dp[v][1]+w[v])<=tmp){
dfs2(v,1,k);
st[++top]=v;
}
else{
if(dp[v][0]<=dp[v][1]) dfs2(v,0,k);
else dfs2(v,1,k);
}
}
}
else{
for(ll v=son[u];v;v=suf[v]){
if(v==pos){
dfs2(v,1,k);
st[++top]=v;
}
else{
if(dp[v][0]<=dp[v][1]) dfs2(v,0,k);
else dfs2(v,1,k);
}
}
}
}
}
void print(ll u){
pf("%lld %lld : %lld\n",fa[u],u,w[u]);
for(ll v=son[u];v;v=suf[v]) print(v);
}
int main(){
n=read();
scanf("%s",s+1);
fr(i,1,n) if(s[i]=='1') ck[i]=1;
fr(i,2,n){
ll u=read(),v=read();
vec[u].push_back(v);
vec[v].push_back(u);
}
dfs0(1);
cut(1);
// pf("-----------------\n");
// print(1);
fr(k,1,n){
dfs1(1,k);
writeln(min(dp[1][0],dp[1][1]));
if(dp[1][0]<=dp[1][1]) dfs2(1,0,k);
else dfs2(1,1,k);
fr(i,1,top){
ll u=st[i],nxt;
for(ll v=son[u];v;v=nxt){
nxt=suf[v];
del(u,v);
ins(fa[u],v);
w[v]+=w[u]+siz[u];
}
siz[fa[u]]+=siz[u]+w[u];
ck[fa[u]]|=ck[u];
del(fa[u],u);
}
top=0;
cut(1);
// pf("-----------------\n");
// print(1);
}
}
詳細信息
Test #1:
score: 4.16667
Accepted
time: 2ms
memory: 8348kb
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: 5ms
memory: 8432kb
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: 9064kb
input:
5000 0100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000000000000000000000000000000000000000000000010000000...
output:
711 840 954 1055 1144 1219 1280 1344 1395 1443 1485 1527 1566 1605 1644 1682 1719 1755 1790 1823 1855 1887 1919 1950 1980 2009 2038 2066 2094 2122 2149 2176 2203 2228 2252 2275 2297 2319 2341 2363 2384 2404 2423 2441 2459 2477 2494 2511 2527 2542 2557 2571 2584 2596 2607 2618 2628 2638 2648 2658 266...
result:
wrong answer 2nd numbers differ - expected: '837', found: '840'
Test #4:
score: 0
Wrong Answer
time: 47ms
memory: 8676kb
input:
5000 0100000000000000000000000000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010000000000000000000000000000000000000000000000000000000000000000000...
output:
890 1228 1488 1728 1898 2030 2118 2200 2263 2321 2374 2426 2473 2521 2567 2610 2650 2689 2728 2765 2800 2834 2867 2899 2930 2961 2990 3018 3046 3073 3098 3122 3145 3167 3189 3211 3232 3252 3271 3290 3309 3327 3345 3362 3378 3394 3410 3425 3439 3452 3464 3475 3485 3494 3503 3512 3521 3529 3536 3542 3...
result:
wrong answer 2nd numbers differ - expected: '1226', found: '1228'
Test #5:
score: 0
Wrong Answer
time: 33ms
memory: 8972kb
input:
5000 0100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000000000000000000000000000000000000000000000000000000000000001000000000000000001000000000000000000000000000000000000000000000000...
output:
794 1040 1241 1428 1590 1695 1782 1864 1924 1985 2049 2096 2139 2179 2218 2257 2295 2332 2367 2401 2435 2469 2503 2536 2568 2600 2632 2663 2694 2724 2753 2781 2808 2834 2859 2883 2906 2929 2951 2973 2994 3014 3033 3052 3070 3087 3103 3118 3133 3147 3160 3172 3183 3193 3202 3210 3218 3225 3231 3236 3...
result:
wrong answer 2nd numbers differ - expected: '1025', found: '1040'
Test #6:
score: 0
Time Limit Exceeded
input:
200000 01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
30804 41826 49653 54274 55677 56398 56997 57451 57879 58279 58662 59039 59412 59779 60140 60500 60859 61216 61572 61927 62281 62634 62986 63338 63689 64039 64388 64736 65083 65429 65774 66118 66461 66803 67144 67484 67823 68161 68499 68836 69172 69507 69841 70175 70508 70840 71171 71501 71831 72160 ...
result:
Test #7:
score: 0
Time Limit Exceeded
input:
200000 01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
30644 41684 49594 54270 55626 56302 56868 57316 57744 58156 58547 58931 59312 59689 60058 60426 60794 61161 61527 61891 62254 62617 62979 63340 63699 64057 64414 64770 65125 65479 65832 66184 66536 66887 67237 67586 67934 68281 68627 68972 69316 69659 70001 70342 70682 71022 71361 71699 72036 72372 ...
result:
Test #8:
score: 0
Time Limit Exceeded
input:
200000 01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
30736 41767 49608 54272 55596 56275 56843 57295 57728 58135 58520 58901 59277 59649 60016 60382 60747 61111 61473 61832 62191 62549 62907 63264 63620 63974 64327 64679 65030 65380 65729 66077 66424 66770 67115 67459 67803 68146 68488 68830 69171 69512 69852 70192 70531 70869 71206 71543 71879 72214 ...
result:
Test #9:
score: 0
Time Limit Exceeded
input:
100000 01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
12231 13894 15260 16410 17329 18081 18711 19256 19690 20089 20427 20733 21022 21290 21546 21787 22018 22241 22454 22661 22860 23061 23254 23446 23635 23820 24003 24183 24362 24539 24714 24888 25063 25234 25405 25578 25748 25918 26087 26255 26423 26590 26756 26922 27087 27252 27417 27581 27744 27907 ...
result:
Test #10:
score: 0
Time Limit Exceeded
input:
100000 01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
15993 21898 26347 29982 32510 34166 35314 36110 36758 37292 37747 38156 38509 38843 39143 39426 39699 39955 40202 40438 40667 40891 41112 41326 41532 41734 41934 42127 42319 42508 42693 42877 43060 43242 43423 43603 43782 43959 44134 44308 44482 44655 44827 44998 45168 45336 45502 45667 45832 45997 ...
result:
Test #11:
score: 0
Time Limit Exceeded
input:
100000 01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
14608 18793 22574 25563 28423 30569 32349 33751 34896 35835 36643 37429 38141 38796 39413 40010 40582 41133 41667 42189 42698 43190 43663 44126 44578 45023 45462 45891 46314 46731 47129 47518 47901 48282 48658 49026 49390 49749 50102 50451 50793 51130 51463 51787 52107 52425 52735 53041 53342 53638 ...
result:
Test #12:
score: 0
Time Limit Exceeded
input:
100000 01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
12198 13850 15185 16296 17231 18010 18646 19184 19642 20058 20447 20788 21104 21404 21681 21951 22213 22468 22710 22946 23179 23409 23643 23872 24096 24314 24528 24741 24951 25163 25371 25578 25782 25986 26189 26391 26592 26794 26993 27192 27391 27590 27789 27987 28184 28381 28577 28772 28966 29160 ...
result:
Test #13:
score: 0
Time Limit Exceeded
input:
100000 01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
16072 21985 26409 30149 32614 34327 35542 36418 37106 37677 38181 38620 39015 39385 39714 40024 40327 40617 40886 41149 41404 41644 41872 42096 42316 42532 42746 42957 43167 43377 43584 43789 43991 44190 44389 44585 44779 44968 45155 45340 45525 45709 45893 46077 46261 46443 46624 46803 46980 47156 ...
result:
Test #14:
score: 0
Time Limit Exceeded
input:
100000 01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
14721 18966 22776 25919 28900 31013 32885 34366 35628 36650 37613 38406 39167 39798 40389 40944 41476 41981 42462 42922 43362 43793 44215 44621 45016 45397 45767 46122 46473 46812 47139 47452 47753 48045 48327 48605 48875 49140 49397 49647 49888 50125 50357 50588 50815 51041 51266 51488 51705 51922 ...
result:
Test #15:
score: 0
Time Limit Exceeded
input:
100000 01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
12121 13789 15149 18696 20498 22146 23629 25008 26299 27553 28764 29933 31084 32201 33299 34388 35467 36536 37600 38664 39722 40773 41821 42866 43909 44944 45976 47006 48040 49068 50096 51121 52147 53170 54193 55216 56238 57259 58279 59298 60316 61333 62350 63367 64383 65398 66413 67427 68441 69454 ...
result:
Test #16:
score: 0
Time Limit Exceeded
input:
100000 01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
16192 22132 26632 30286 32897 34684 35864 36714 37404 37945 38416 38811 39170 39491 39791 40065 40330 40582 40828 41070 41301 41530 41755 41976 42195 42410 42619 42826 43033 43238 43441 43642 43842 44041 44240 44438 44634 44827 45019 45210 45399 45587 45774 45959 46141 46322 46500 46677 46852 47026 ...
result:
Test #17:
score: 0
Time Limit Exceeded
input:
100000 01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
14705 18950 22799 25946 29000 31239 33115 34594 35922 36985 37968 38868 39685 40464 41223 41960 42675 43371 44054 44720 45377 46027 46667 47300 47925 48544 49159 49769 50374 50972 51568 52161 52749 53333 53915 54495 55073 55648 56221 56793 57361 57926 58487 59044 59599 60154 60708 61261 61811 62359 ...
result:
Test #18:
score: 0
Time Limit Exceeded
input:
100000 01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
12282 13921 15273 16418 17379 18142 18766 19303 19779 20175 20539 20881 21170 21437 21694 21943 22168 22384 22594 22806 23013 23213 23411 23607 23802 23993 24181 24366 24548 24729 24907 25085 25260 25435 25608 25780 25951 26121 26291 26461 26631 26800 26968 27135 27301 27466 27630 27794 27957 28119 ...
result:
Test #19:
score: 4.16667
Accepted
time: 29ms
memory: 17112kb
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 43819 52537 59813 64875 68127 70393 71968 73193 74192 75014 75719 76318 76860 77365 77851 78311 78737 79145 79539 79915 80269 80600 80920 81234 81544 81849 82150 82449 82742 83032 83315 83596 83875 84148 84419 84688 84956 85219 85481 85741 85999 86257 86512 86767 87019 87270 87520 87768 88013 ...
result:
Test #21:
score: 0
Time Limit Exceeded
input:
200000 01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
29187 37637 45119 51274 56769 61241 64744 67538 69782 71679 73274 74736 76106 77309 78437 79509 80532 81526 82494 83435 84349 85244 86125 86990 87837 88670 89491 90292 91079 91852 92614 93357 94094 94826 95551 96269 96977 97677 98372 99061 99739 100410 101072 101723 102364 102997 103620 104229 10482...
result:
Test #22:
score: 0
Time Limit Exceeded
input:
200000 01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
24124 27295 29803 36595 39967 43038 45875 48469 50942 53300 55574 57757 59896 62000 64066 66101 68118 70121 72102 74068 76026 77979 79919 81853 83785 85711 87632 89549 91467 93381 95291 97200 99108 101014 102920 104825 106730 108634 110538 112441 114344 116246 118147 120048 121948 123848 125747 1276...
result:
Test #23:
score: 0
Time Limit Exceeded
input:
200000 01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
32229 44031 52843 60297 65336 68505 70757 72350 73551 74473 75267 75929 76521 77053 77548 77997 78425 78842 79234 79611 79976 80328 80670 81010 81342 81668 81984 82296 82603 82902 83197 83491 83782 84073 84360 84646 84930 85212 85492 85770 86045 86319 86592 86862 87128 87391 87650 87908 88165 88420 ...
result:
Test #24:
score: 4.16667
Accepted
time: 125ms
memory: 24444kb
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:
ok 200000 numbers