QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #617056 | #1960. Logical Warehouse 2 | AnotherDayofSun# | AC ✓ | 441ms | 20392kb | C++14 | 1.8kb | 2024-10-06 13:44:12 | 2024-10-06 13:44:14 |
Judging History
answer
#include<bits/stdc++.h>
#define re
#define N 300005
#define ll long long
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 fak[N],fa[N],dep[N],stk[N],top;
void dfs(int x,int f){
fa[x]=f;
stk[++top]=x;
if(top>K)fak[x]=stk[top-K];
else fak[x]=stk[1];
dep[x]=dep[f]+1;
for(int i=head[x];i;i=nxt[i]){
int y=to[i];
if(y==f)continue;
dfs(y,x);
}
top--;
}
struct node{
int x,d;
}A[N];
bool cmp(node a,node b){return a.d>b.d;}
bool mk[N],ts[N],now[N];
int Q[N],D[N];
void bfs(int st){
ts[st]=1;
int l=0,r=0;
Q[++r]=st;D[r]=0;
while(l<r){
int x=Q[++l];
int d=D[l];
if(l!=1&&ts[x])continue;
now[x]=1;mk[x]=1;
// printf("mark: %d\n",x);
if(d==K)continue;
for(int i=head[x];i;i=nxt[i]){
int y=to[i];
if(now[y])continue;
Q[++r]=y;D[r]=d+1;
}
}
for(int i=1;i<=r;i++)now[Q[i]]=0;
}
int main(){
Rd(n),Rd(K);
for(int i=1;i<n;i++){
int x,y;
Rd(x),Rd(y);
adde(x,y);
adde(y,x);
}
dfs(1,0);
for(int i=1;i<=n;i++)A[i]=(node){i,dep[i]};
sort(A+1,A+n+1,cmp);
int ans=0;
for(int i=1;i<=n;i++){
int x=A[i].x;
if(mk[x])continue;
// printf("mark: %d %d\n",x,fak[x]);
bfs(fak[x]);
ans++;
}
printf("%d\n",ans);
return 0;
}
/*
9 1
2 1
7 3
3 4
4 5
6 5
7 8
3 2
8 9
mark: 6 5
mark: 9 8
mark: 4 3
mark: 7 6
mark: 2 1
5
*/
詳細信息
Test #1:
score: 100
Accepted
time: 2ms
memory: 11964kb
input:
100 1 1 63 2 45 3 28 4 60 5 92 6 91 7 2 8 44 9 22 10 21 11 97 12 21 13 63 14 92 15 74 16 97 17 80 18 28 19 63 20 71 21 39 22 24 23 44 24 21 25 63 26 16 27 31 28 31 29 2 30 6 31 21 32 92 33 73 34 63 35 2 36 90 37 1 38 45 39 80 40 75 41 63 42 63 43 20 44 81 45 21 46 63 47 24 48 18 49 92 50 57 51 4 52 ...
output:
30
result:
ok single line: '30'
Test #2:
score: 0
Accepted
time: 0ms
memory: 12040kb
input:
1000 3 1 358 2 426 3 505 4 528 5 778 6 713 7 719 8 811 9 8 10 499 11 53 12 78 13 375 14 476 15 464 16 651 17 509 18 997 19 370 20 430 21 516 22 526 23 303 24 426 25 303 26 521 27 515 28 690 29 499 30 563 31 705 32 188 33 719 34 20 35 100 36 738 37 135 38 64 39 577 40 449 41 682 42 135 43 282 44 521 ...
output:
76
result:
ok single line: '76'
Test #3:
score: 0
Accepted
time: 0ms
memory: 12120kb
input:
10000 100 1 7746 2 5319 3 436 4 2144 5 6630 6 5400 7 5552 8 4613 9 7779 10 4152 11 3212 12 942 13 7710 14 7888 15 4792 16 1304 17 8229 18 6952 19 2421 20 605 21 1213 22 2704 23 5982 24 189 25 9274 26 5928 27 1221 28 659 29 9360 30 7578 31 770 32 5230 33 6327 34 1555 35 7610 36 3332 37 8214 38 5724 3...
output:
5
result:
ok single line: '5'
Test #4:
score: 0
Accepted
time: 12ms
memory: 15124kb
input:
100000 3 1 30441 2 9582 3 55511 4 73649 5 70310 6 8880 7 76079 8 81690 9 31895 10 82263 11 80212 12 55527 13 90303 14 34890 15 36246 16 5048 17 82441 18 87955 19 94122 20 54713 21 64199 22 93506 23 48278 24 99255 25 31162 26 87849 27 85349 28 44207 29 18448 30 99210 31 63408 32 48337 33 93602 34 891...
output:
7440
result:
ok single line: '7440'
Test #5:
score: 0
Accepted
time: 7ms
memory: 15256kb
input:
100000 60 1 50024 2 24703 3 5489 4 30417 5 33180 6 41854 7 24160 8 33478 9 28830 10 26478 11 45166 12 81183 13 85160 14 90160 15 91068 16 85544 17 31051 18 17311 19 77242 20 99971 21 11586 22 55977 23 30968 24 41315 25 43769 26 21652 27 8521 28 13407 29 10342 30 45568 31 98655 32 84071 33 91007 34 2...
output:
76
result:
ok single line: '76'
Test #6:
score: 0
Accepted
time: 3ms
memory: 10188kb
input:
10000 2 1 5691 2 187 3 756 4 4927 5 5900 6 1299 7 1692 8 9410 9 6866 10 3647 11 3885 12 527 13 3225 14 4222 15 2 16 81 18 9720 19 46 20 3601 21 9082 22 1242 23 1286 24 5249 25 4074 26 422 28 9841 29 8261 30 9075 31 2177 32 756 33 3768 34 3556 35 5058 36 4037 37 2309 38 3369 39 982 41 5909 42 7854 43...
output:
1482
result:
ok single line: '1482'
Test #7:
score: 0
Accepted
time: 12ms
memory: 13932kb
input:
100000 1 1 82490 2 56262 3 14223 4 21203 5 3593 6 1846 7 49412 8 89099 9 13642 10 90949 11 96927 12 41006 13 5947 14 40471 15 78297 16 9521 17 65820 18 98572 19 88103 20 93475 21 31366 22 54355 23 13097 24 27617 25 77612 26 56717 27 28369 28 6720 29 38941 30 86614 31 12801 32 42542 33 63415 34 69623...
output:
32569
result:
ok single line: '32569'
Test #8:
score: 0
Accepted
time: 12ms
memory: 12440kb
input:
100000 100 1 33799 2 63643 3 57753 4 16139 5 89528 6 11313 7 72331 8 78177 9 64508 10 7334 11 72871 12 2135 13 64310 14 85008 15 28791 16 11118 17 71522 18 1824 19 9154 20 86931 21 71904 22 37120 23 99250 24 37455 25 88871 26 99921 27 40193 28 79946 29 37985 30 53216 31 80023 32 21301 33 54512 34 15...
output:
47
result:
ok single line: '47'
Test #9:
score: 0
Accepted
time: 15ms
memory: 16024kb
input:
100000 100 1 82064 2 47713 3 2798 4 83700 5 95971 6 75999 8 96895 9 64767 10 93922 11 11112 12 97491 13 44110 14 44396 16 5509 17 96991 18 52527 19 76847 20 60545 22 59527 23 37664 24 98417 25 78243 26 90274 28 44628 29 80948 30 99888 31 58034 32 42820 33 61508 34 95311 35 26096 36 67799 38 18815 39...
output:
132
result:
ok single line: '132'
Test #10:
score: 0
Accepted
time: 13ms
memory: 16200kb
input:
100000 1000 2 9741 3 35988 4 67282 6 45940 8 18322 10 59170 16 76587 18 48225 24 33682 25 7248 26 92848 28 45449 30 70965 31 90737 32 11903 33 65999 38 96679 39 52090 40 21166 44 55107 45 10897 46 10126 47 24905 49 72722 50 99451 54 53118 55 29436 58 75438 61 75191 66 94070 68 17004 69 87159 70 1825...
output:
25
result:
ok single line: '25'
Test #11:
score: 0
Accepted
time: 14ms
memory: 13616kb
input:
100000 2 1 75007 2 91380 3 61696 4 3880 5 63044 6 67825 7 81582 8 9637 9 62771 10 50679 11 40052 12 88452 13 59553 14 98649 15 19504 16 77681 17 20769 18 40465 19 72497 20 49248 21 73041 22 91530 23 40529 24 55075 25 26515 26 74021 27 52398 28 92781 29 20778 30 66705 31 73791 32 82252 33 38060 34 81...
output:
14043
result:
ok single line: '14043'
Test #12:
score: 0
Accepted
time: 21ms
memory: 15376kb
input:
100000 2 1 41509 2 99131 3 10219 4 27802 5 47344 6 61157 7 2908 8 82716 9 15161 10 53925 11 33994 12 30641 13 44429 14 85400 15 9110 16 47691 17 86862 18 83776 19 81527 20 53000 21 45016 22 89820 23 98152 24 41561 25 23874 26 71464 27 90834 28 44679 29 62714 30 72866 31 50880 32 14141 33 52541 34 31...
output:
14210
result:
ok single line: '14210'
Test #13:
score: 0
Accepted
time: 21ms
memory: 13152kb
input:
100000 2 1 30207 3 454 4 75557 7 25987 8 1584 9 87016 12 76544 15 30902 16 26605 17 63839 18 44677 19 90660 20 27048 21 64373 22 2189 23 59439 24 38184 25 99271 27 3393 30 69814 31 526 32 77122 33 24477 34 17314 35 84466 37 69263 38 78306 39 38582 41 6699 42 99444 43 92244 44 40764 45 91280 46 92254...
output:
16877
result:
ok single line: '16877'
Test #14:
score: 0
Accepted
time: 2ms
memory: 10052kb
input:
30 2 30 15 3 12 4 28 6 4 9 25 10 12 11 4 17 6 24 12 29 24 1 2 2 5 5 7 7 8 8 12 12 13 13 14 14 15 15 16 16 18 18 19 19 20 20 21 21 22 22 23 23 25 25 26 26 27 27 28
output:
6
result:
ok single line: '6'
Test #15:
score: 0
Accepted
time: 2ms
memory: 12096kb
input:
50 3 1 49 2 49 3 17 6 9 9 18 12 29 13 43 15 31 18 43 19 50 20 49 23 43 35 42 40 14 43 17 44 49 45 39 46 39 49 17 50 6 4 5 5 7 7 8 8 10 10 11 11 14 14 16 16 17 17 21 21 22 22 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 36 36 37 37 38 38 39 39 41 41 42 42 47 47 48
output:
6
result:
ok single line: '6'
Test #16:
score: 0
Accepted
time: 9ms
memory: 12996kb
input:
50000 111 1 35731 2 18939 3 48620 4 31015 5 22318 7 47596 8 34387 9 2452 10 1241 11 17324 13 23500 14 6827 15 34327 16 26382 17 38206 18 47056 19 39266 20 15482 21 16877 22 11295 23 47801 24 25742 25 46098 26 39586 27 26816 28 3836 31 26063 32 47102 33 177 34 34631 35 40248 36 33118 37 6786 38 35162...
output:
60
result:
ok single line: '60'
Test #17:
score: 0
Accepted
time: 17ms
memory: 13564kb
input:
80000 2 1 73752 2 41168 3 66064 4 7844 5 67806 6 30341 7 12373 8 847 9 79147 10 78551 11 62285 12 78176 13 79090 14 58444 15 55109 16 28035 17 47053 18 45301 19 78194 20 2187 21 59803 22 52120 23 15094 24 12514 25 60070 26 27383 27 20198 28 26972 29 55611 30 16311 31 48458 32 56842 33 70489 34 38299...
output:
11194
result:
ok single line: '11194'
Test #18:
score: 0
Accepted
time: 17ms
memory: 14564kb
input:
80000 2 2 44200 3 53398 4 15503 5 3877 7 67482 9 36350 11 70014 13 70787 14 29730 15 14600 16 24443 17 37239 18 50363 21 69004 22 46702 23 5835 24 10356 26 63756 27 23638 28 35061 29 13741 31 58817 34 4743 35 13809 36 43896 37 69546 39 12255 41 37949 42 38918 43 50504 44 41736 45 17062 46 24089 47 2...
output:
13760
result:
ok single line: '13760'
Test #19:
score: 0
Accepted
time: 3ms
memory: 12716kb
input:
11111 11 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 52...
output:
484
result:
ok single line: '484'
Test #20:
score: 0
Accepted
time: 0ms
memory: 12008kb
input:
20 3 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20
output:
3
result:
ok single line: '3'
Test #21:
score: 0
Accepted
time: 10ms
memory: 10932kb
input:
50000 5 1 43836 2 23844 3 43980 4 16046 5 30880 6 12368 7 47303 8 2249 9 2330 10 26181 11 9361 12 4308 13 21178 14 12388 15 6432 16 49529 17 44808 18 49463 19 31687 20 11147 21 10015 22 6808 23 36502 24 5118 25 9496 26 21756 27 16863 28 16076 29 15070 30 7396 31 27032 32 4289 33 12378 34 47202 35 21...
output:
1522
result:
ok single line: '1522'
Test #22:
score: 0
Accepted
time: 8ms
memory: 20392kb
input:
99999 5 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 52 ...
output:
9091
result:
ok single line: '9091'
Test #23:
score: 0
Accepted
time: 2ms
memory: 12020kb
input:
100 2 1 50 2 50 3 50 4 32 5 50 6 85 7 50 8 85 9 53 10 50 11 50 12 25 13 50 14 27 15 50 16 50 17 50 18 94 19 53 20 94 21 69 22 65 23 65 24 50 25 50 26 6 27 50 28 53 29 73 30 77 31 50 32 50 33 83 34 50 35 50 36 32 37 50 38 50 39 79 40 32 41 79 42 79 43 94 44 71 45 40 46 68 47 25 48 94 49 85 51 50 52 7...
output:
8
result:
ok single line: '8'
Test #24:
score: 0
Accepted
time: 0ms
memory: 12120kb
input:
1000 100 1 646 2 726 3 460 4 174 5 339 6 77 7 51 8 760 9 339 10 726 11 310 12 224 13 923 14 339 15 339 16 339 17 339 18 339 19 325 20 860 21 339 22 339 23 753 24 165 25 339 26 145 27 140 28 199 29 339 30 179 31 634 32 339 33 885 34 187 35 760 36 339 37 339 38 542 39 967 40 339 41 29 42 964 43 754 44...
output:
1
result:
ok single line: '1'
Test #25:
score: 0
Accepted
time: 0ms
memory: 12324kb
input:
10000 4 1 9963 2 9963 3 9958 4 6064 5 4169 6 6838 7 4248 8 4410 9 541 10 9963 11 9963 12 951 13 4216 14 3172 15 9963 16 9963 17 9963 18 8015 19 9963 20 323 21 3145 22 9963 23 9963 24 9963 25 9963 26 6484 27 5209 28 9963 29 3364 30 9963 31 9963 32 8421 33 8685 34 9963 35 9963 36 9963 37 6088 38 8344 ...
output:
16
result:
ok single line: '16'
Test #26:
score: 0
Accepted
time: 10ms
memory: 14052kb
input:
100000 11 1 60822 2 24991 3 36312 4 74884 5 36312 6 71731 7 36312 8 57685 9 36312 10 36312 11 36312 12 36312 13 36312 14 36312 15 36312 16 72015 17 25973 18 70755 19 36312 20 58343 21 89154 22 80047 23 36312 24 36312 25 78017 26 36312 27 70220 28 19287 29 36312 30 57581 31 84691 32 89017 33 36312 34...
output:
1
result:
ok single line: '1'
Test #27:
score: 0
Accepted
time: 441ms
memory: 13620kb
input:
100000 2 1 47045 2 12074 3 32094 4 47045 5 47045 6 40135 7 47045 8 47045 9 64582 10 73086 11 74862 12 47045 13 20190 14 69577 15 64803 16 47045 17 47045 18 83621 19 47045 20 68821 21 47045 22 30586 23 49403 24 22251 25 47045 26 61523 27 60317 28 42185 29 47045 30 95606 31 47045 32 85274 33 47045 34 ...
output:
4836
result:
ok single line: '4836'
Test #28:
score: 0
Accepted
time: 2ms
memory: 12004kb
input:
30 10 1 2 2 10 3 27 4 2 5 2 6 2 7 27 8 17 9 10 11 20 12 2 13 2 14 10 15 10 16 10 17 10 18 17 19 10 20 10 21 26 22 10 23 10 24 10 25 10 26 10 27 10 28 10 29 10 30 27
output:
1
result:
ok single line: '1'