QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#201431 | #5157. High-quality Tree | BoulevardDust# | WA | 487ms | 33384kb | C++20 | 2.2kb | 2023-10-05 14:18:45 | 2023-10-05 14:18:46 |
Judging History
answer
#include<bits/stdc++.h>
#define N 300005
#define re
using namespace std;
int n,m,K,q,T;
inline void Rd(int &res){
re char c;res=0;
while(c=getchar(),c<48);
do res=(res<<3)+(res<<1)+(c^48);
while(c=getchar(),c>47);
}
int head[N],to[N<<1],nxt[N<<1],cnt1;
inline void adde(int x,int y){to[++cnt1]=y;nxt[cnt1]=head[x];head[x]=cnt1;}
int fa[N],dep[N],totid,L[N],R[N],dfn[N];
int Lson[N],Rson[N],cnt[N];
void dfs(int x,int f){
fa[x]=f;dep[x]=dep[f]+1;
L[x]=++totid;dfn[totid]=x;
for(re int i=head[x];i;i=nxt[i]){
int y=to[i];
if(y==f)continue;
if(Lson[x]==0)Lson[x]=y;
else Rson[x]=y;
cnt[x]++;
dfs(y,x);
}
R[x]=totid;
}
int tree[N<<2];
void Build(int l,int r,int p){
if(l==r){
tree[p]=dep[dfn[l]];
return;
}
int mid=(l+r)>>1;
Build(l,mid,p<<1);
Build(mid+1,r,p<<1|1);
tree[p]=max(tree[p<<1],tree[p<<1|1]);
}
int query(int l,int r,int L,int R,int p){
if(l==L&&r==R)return tree[p];
int mid=(l+r)>>1;
if(R<=mid)return query(l,mid,L,R,p<<1);
else if(L>mid)return query(mid+1,r,L,R,p<<1|1);
else return max(query(l,mid,L,mid,p<<1),query(mid+1,r,mid+1,R,p<<1|1));
}
void update(int l,int r,int x,int p){
if(l==r){tree[p]=0;return;}
int mid=(l+r)>>1;
if(x<=mid)update(l,mid,x,p<<1);
else update(mid+1,r,x,p<<1|1);
tree[p]=max(tree[p<<1],tree[p<<1|1]);
}
int a[N];
bool cmp(int x,int y){return dep[x]>dep[y];}
bool in(int x,int y){return L[x]<=L[y]&&R[x]>=L[y];}
bool check(int x){
int t=fa[x];
while(t){
int d1=dep[t],d2=dep[t];
if(Lson[t]!=0)d1=max(d1,query(1,n,L[Lson[t]],R[Lson[t]],1));
if(Rson[t]!=0)d2=max(d2,query(1,n,L[Rson[t]],R[Rson[t]],1));
if(dep[x]>min(d1,d2)+1)return 0;
t=fa[t];
}
return 1;
}
int ans;
struct node{
int x,d;
bool operator<(const node&res)const{return d>res.d;}
};
priority_queue<node>Q;
void Del(int x){
update(1,n,L[x],1);
ans++;
if(x==1)return;
x=fa[x];cnt[x]--;
if(cnt[x]==0)Q.push((node){x,dep[x]});
}
int main(){
Rd(n);
for(re int i=1;i<n;i++){
int x,y;
Rd(x),Rd(y);
adde(x,y);
adde(y,x);
}
dfs(1,0);
Build(1,n,1);
for(re int i=1;i<=n;i++)
if(cnt[i]==0)Q.push((node){i,dep[i]});
while(!Q.empty()){
int x=Q.top().x;Q.pop();
if(!check(x))Del(x);
}
printf("%d\n",ans);
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 14012kb
input:
6 1 2 1 3 3 4 3 5 5 6
output:
1
result:
ok single line: '1'
Test #2:
score: 0
Accepted
time: 0ms
memory: 12020kb
input:
12 1 2 2 3 3 4 3 5 1 6 6 7 7 8 7 9 9 10 6 11 11 12
output:
3
result:
ok single line: '3'
Test #3:
score: 0
Accepted
time: 253ms
memory: 25944kb
input:
200000 167246 158246 40931 40296 178588 27974 35171 899 4204 163250 101422 9230 55420 93371 16012 140142 28866 154497 33519 180725 50361 52348 46923 175364 126599 169575 15138 34958 164256 64770 63123 130169 154172 168301 127476 54744 199964 81879 173765 69220 178225 73653 59861 46415 138112 17507 8...
output:
199998
result:
ok single line: '199998'
Test #4:
score: 0
Accepted
time: 92ms
memory: 33384kb
input:
200000 144434 24107 75087 108465 38670 156657 31235 30143 40544 44213 51188 21788 170574 164351 14169 155909 120876 119956 196361 140453 197958 142813 23944 62568 12098 71652 162226 122184 123783 86178 70076 115586 74439 94246 83296 36713 182500 16937 174946 154091 97484 194764 179943 61793 114439 1...
output:
199998
result:
ok single line: '199998'
Test #5:
score: 0
Accepted
time: 487ms
memory: 20348kb
input:
200000 42469 8516 3910 143673 129125 150433 170053 160404 147325 66173 130784 195620 183508 43943 90940 88012 187183 803 139576 36677 190280 71191 107959 177664 14308 20402 93449 130555 80315 75413 178265 104526 4428 8875 151397 91172 181321 47276 105060 81973 196326 19584 44364 56143 187070 195424 ...
output:
199998
result:
ok single line: '199998'
Test #6:
score: 0
Accepted
time: 251ms
memory: 19904kb
input:
131071 94531 87688 119005 53065 70725 126770 61026 82294 114384 270 98205 38915 61461 14652 123122 36872 37639 52311 17774 89648 79899 59785 6033 52465 15449 93250 43849 18174 2665 82543 26740 15199 71645 14339 45549 119270 22896 70677 126250 23614 5796 85715 92715 25280 119740 8911 17923 5547 47703...
output:
0
result:
ok single line: '0'
Test #7:
score: 0
Accepted
time: 0ms
memory: 14000kb
input:
7 1 3 3 4 1 7 7 2 7 6 3 5
output:
0
result:
ok single line: '0'
Test #8:
score: 0
Accepted
time: 107ms
memory: 16108kb
input:
75026 12155 64806 40053 74785 70103 1220 72989 33966 74199 66365 52024 24358 54545 52118 52572 28566 68873 41146 10161 67848 41221 63589 72291 44013 51515 14784 12150 33009 3919 23413 61773 13741 21172 17759 27774 65766 58702 13619 11690 19263 45469 30662 33296 45184 51641 13235 11413 52734 74437 57...
output:
2
result:
ok single line: '2'
Test #9:
score: 0
Accepted
time: 7ms
memory: 14400kb
input:
10947 7184 5103 1433 10766 3794 8428 1438 8926 2493 7796 6753 7135 3304 4497 9148 8680 4013 2259 3067 8641 2809 9523 9557 2452 8392 3411 1121 6418 5150 133 8893 3701 7864 3044 7152 705 3856 5325 10943 4760 9792 7866 6959 6282 1120 7627 2952 9675 10407 9119 2489 1131 907 4948 4175 3572 4178 337 226 7...
output:
2
result:
ok single line: '2'
Test #10:
score: 0
Accepted
time: 2ms
memory: 14400kb
input:
8375 5605 5852 7762 3219 1669 4378 341 6410 1502 1920 706 8356 5088 5723 1326 6305 2433 5341 5185 948 7639 5745 6173 7572 4736 7204 8081 3452 2414 6798 156 7332 6627 2209 876 5078 2666 292 5041 7782 7118 807 6897 5220 5865 1273 6546 1506 4306 7980 1119 6488 4795 5942 6219 7729 8119 1572 4027 4817 46...
output:
701
result:
ok single line: '701'
Test #11:
score: 0
Accepted
time: 17ms
memory: 14828kb
input:
19450 13860 10518 15222 9423 8628 4061 13172 14144 10621 1876 14867 11492 5902 19300 11313 2895 2777 6935 6948 18381 13897 14220 11979 19134 5771 10820 19025 16787 8909 7140 10163 19125 4204 5969 8802 3293 11379 17457 4788 6749 14771 10567 5201 18207 3410 7595 12521 4698 19184 15244 10662 7902 16998...
output:
732
result:
ok single line: '732'
Test #12:
score: 0
Accepted
time: 173ms
memory: 28188kb
input:
199999 42470 186792 84838 99410 115027 161613 35565 77810 72472 47859 180671 162382 32852 67468 75811 198709 124926 126090 54877 26903 165267 13544 8081 157453 152632 92738 145016 76659 74572 183100 116308 42324 140949 129632 170934 122224 10244 34160 88908 198457 124270 136554 190537 124534 137981 ...
output:
199994
result:
ok single line: '199994'
Test #13:
score: 0
Accepted
time: 187ms
memory: 27360kb
input:
199999 32647 44026 42853 57810 175394 58242 95892 8293 2439 15285 112251 57100 187050 83100 112980 29377 157012 134211 135596 33147 85472 59785 139169 125631 153085 165140 82629 73365 25158 16327 191064 93990 123231 32916 130815 20323 129599 77035 144632 98686 67473 3578 172156 98862 21894 195995 16...
output:
199994
result:
ok single line: '199994'
Test #14:
score: 0
Accepted
time: 189ms
memory: 27848kb
input:
199999 37321 183353 197048 89193 114486 34848 82027 85518 62564 117961 17663 28259 91838 124561 188988 46866 156756 75225 105968 183481 118948 67500 75409 123761 107128 52670 171953 102720 62773 165219 194620 173567 31552 88489 97494 15048 189108 36762 11031 1741 64889 67129 158657 157875 191291 359...
output:
199994
result:
ok single line: '199994'
Test #15:
score: 0
Accepted
time: 449ms
memory: 20316kb
input:
200000 196903 77452 27188 55527 102207 165320 134712 55341 162994 81141 85731 30299 75243 18518 23639 84881 197033 143822 120492 51146 46281 145275 99830 195228 185002 53761 54098 31449 60141 191308 193012 177578 67355 11089 66265 166383 34969 194717 175543 128704 40124 39801 196897 185270 34468 798...
output:
5234
result:
ok single line: '5234'
Test #16:
score: -100
Wrong Answer
time: 300ms
memory: 21692kb
input:
200000 164768 68803 153609 72233 28630 173584 188468 26064 147938 153547 106394 130342 153098 185806 157156 94496 141556 40929 79526 192838 66642 19962 39033 118375 82614 132264 116065 11968 2498 145405 27683 44830 188353 171809 40025 55356 95932 76953 71476 192804 36377 176226 150808 112053 62032 2...
output:
83156
result:
wrong answer 1st lines differ - expected: '87285', found: '83156'