QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#505724 | #8806. Summer Driving | lyx123886a123886 | 1 | 404ms | 37548kb | C++14 | 4.4kb | 2024-08-05 10:05:18 | 2024-08-05 10:05:18 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
template<class T> void chkmin(T &x,T y) {x=(y<x)?y:x;}
template<class T> void chkmax(T &x,T y) {x=(y>x)?y:x;}
#define pb emplace_back
#define LOCAL 0
#define open_file if(LOCAL) {freopen("a.in","r",stdin);freopen("a.out","w",stdout);}
const int MAXN=3e5+50;
int Ex[MAXN],Dp[MAXN];// Dp:(u->v:u) Ex:(u->all-{v'}:v')
int Fb[MAXN];
vector<int> g[MAXN],e[MAXN];int n,Root,A,B;
int dep[MAXN],rv[MAXN],dfn[MAXN],siz[MAXN],par[MAXN],son[MAXN],top[MAXN];
#define bro(v,u) for(int v:g[par[u]]) if(v!=u)
namespace part0 { //(1) get edges (2) initalize Dp,Ex
int stk[MAXN],fmx[MAXN],fmx2[MAXN];
void dfs1(int u,int fa) {
par[u]=fa;dep[u]=dep[fa]+1;
siz[u]=1;
stk[dep[u]]=u;
if(dep[u]-1>=A) {
// e[stk[dep[u]]-(A-1)].pb(u);
e[ stk[dep[u]-(A-1)] ].pb(u);
}
fmx[u]=0;
for(int v:g[u]) if(v!=fa) {
dfs1(v,u);siz[u]+=siz[v];
chkmax(fmx[u],fmx[v]+1);
if(siz[v]>siz[son[u]]) son[u]=v;
}
}
void dfs2(int u,int fa) {
rv[dfn[u]=++dfn[0]]=u;
top[u]=(son[fa]==u)?top[fa]:u;
if(son[u]) dfs2(son[u],u);
for(int v:g[u]) if(v!=fa&&v!=son[u]) {
dfs2(v,u);
}
}
namespace dsu {
int fa[MAXN];
int get_fa(int x) {return (fa[x]==x)?x:(fa[x]=get_fa(fa[x]));}
int del(int x) {
// assert(x!=Root);
fa[x]=par[x];
return get_fa(x);
}
void init() {
for(int i=1;i<=n;++i) fa[i]=i;
}
};
void work() {
dfs1(Root,0);
dfs2(Root,0);
for(int u=1;u<=n;++u) {
sort(g[u].begin(),g[u].end(),[&] (auto i,auto j){return dep[i]>dep[j];});
if(dep[g[u].back()]<dep[u]) g[u].pop_back();
}
for(int u=1;u<=n;++u)
bro(v,u) chkmax(fmx2[u],fmx[v]+1);
// for(int u=1;u<=n;++u) {
// printf("[%d]",dep[u]);
// for(auto v:g[u]) printf("%d,",dep[v]);puts("");
// }
dsu::init();
for(int i=1;i<=n;++i) {
// cerr<<i<<"\n";
if(!Dp[i]&&fmx[i]<A) Dp[i]=i;
for(int v:g[i]) if(!Ex[v]&&fmx2[v]<A) Ex[v]=i;
for(int u=dsu::get_fa(i);u!=Root&&dep[i]-dep[par[u]]<=B;u=dsu::del(u)) {//it's B's turn
bro(v,u) if(!Ex[v]&&fmx2[v]<A) Ex[v]=i;//bf heres
if(!Dp[par[u]]&&fmx[par[u]]<A) Dp[par[u]]=i;
// cerr<<u<<"\n";
}
}
for(int i=1;i<=n;++i) if(i!=Root&&fmx2[i]<A) {
assert(Ex[i]);
}
}
};
using part0::fmx;
using part0::fmx2;
namespace part1 {
#define For(v,u) for(int my_id=dfn[u],v=rv[my_id];my_id<=dfn[u]+siz[u]-1;++my_id,v=rv[my_id])
void get_g(int u) {
For(v,u) if(dep[v]-dep[u]<=B) chkmin(Fb[u],Dp[v]);
// if(u==1) {
// printf("[%d]\n",dep[u]-dep[par[par[u]]]<=B);
// }
for(int y=u;(y!=Root)&&(dep[u]-dep[par[y]]<=B);y=par[y]) {
// if(u==1) printf("*%d*\n",y);
chkmin(Fb[u],Ex[y]);
bro(v,u)
For(c,v) if(dep[c]+dep[u]-2*dep[par[y]]<=B)//!!
chkmin(Fb[u],Dp[c]);
}
}
};
using part1::get_g ;
void gen() {
scanf("%d%d%d%d",&n,&Root,&A,&B);
if(A<=B) {
puts("1");return ;
}
for(int i=1,u,v;i<n;++i) {
scanf("%d%d",&u,&v);
g[u].pb(v);
g[v].pb(u);
}
for(int i=1;i<=n;++i) {
Fb[i]=n+1;
Dp[i]=Ex[i]=0;
}
part0::work();
// return ;
// printf("{%d}\n",Ex[1]);
// return ;
vector<int> perm;
for(int i=1;i<=n;++i) perm.pb(i);
sort(perm.begin(),perm.end(),[&] (auto i,auto j){return dep[i]>dep[j];});
for(auto rt:perm) {
if(fmx[rt]<A) continue;
for(auto u:g[rt]) {
if(fmx[u]<A-1) continue;
int res=0;
for(auto v:e[u]) {
get_g(v);//the most hard one
chkmax(res,Fb[v]);
}
chkmax(Dp[rt],res);
bro(v,u) chkmax(Ex[v],res);
}
}
// for(int i=1;i<=n;++i) printf("[%d,%d,%d]\n",Dp[i],Fb[i],Ex[i]);
// printf("{%d}",Fb[1]);
int ans=Dp[Root];
printf("%d",ans);
}
int main() {
open_file
gen() ;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 1
Accepted
Test #1:
score: 1
Accepted
time: 0ms
memory: 20328kb
input:
300000 110732 1 1 54285 169439 18968 45543 130988 134682 162292 70081 212010 121474 128140 292466 209394 38279 91706 225569 67647 188578 265505 84279 161782 137098 27472 221980 284973 79104 230628 268631 69945 205947 153720 168119 230161 32244 138981 44376 165008 136947 125742 123375 209131 122038 8...
output:
1
result:
ok single line: '1'
Test #2:
score: 1
Accepted
time: 4ms
memory: 19960kb
input:
300000 123141 300000 300000 35459 173656 6934 241069 183095 87288 269195 16957 19492 242321 24470 81747 25697 172188 171424 220229 160473 69937 172168 99268 220664 39397 8212 2407 46718 94855 279515 295195 205222 167038 185958 111515 172553 45818 141322 214355 61335 64490 183502 105408 234540 245525...
output:
1
result:
ok single line: '1'
Test #3:
score: 1
Accepted
time: 0ms
memory: 19980kb
input:
298765 30225 2 3 265195 252069 113697 255482 227617 218688 279488 136408 179394 139291 86777 211320 255097 13136 68860 173342 178971 175020 278041 278319 285893 289677 194438 44163 56223 283058 110392 123602 20729 89517 152134 176747 121481 243463 297305 139297 244189 117068 181785 39468 154302 1860...
output:
1
result:
ok single line: '1'
Test #4:
score: 1
Accepted
time: 0ms
memory: 18276kb
input:
299987 224030 2 2 177674 20066 211112 287348 150440 136779 131528 209570 208840 36580 3395 152219 89118 44403 120439 274280 267578 80200 17796 257578 229408 211795 122773 147368 139779 842 94469 299092 211457 29057 9040 117449 216268 88141 40844 98163 183412 221031 230933 237086 147633 135982 282224...
output:
1
result:
ok single line: '1'
Test #5:
score: 1
Accepted
time: 0ms
memory: 19980kb
input:
2 1 1 2 2 1
output:
1
result:
ok single line: '1'
Subtask #2:
score: 0
Time Limit Exceeded
Test #6:
score: 0
Time Limit Exceeded
input:
300000 226344 300 9 32176 183340 249597 14851 145160 92372 30564 242505 1140 169463 279867 14442 266653 32911 168819 26009 138049 133460 5327 103921 262703 112512 204338 84304 98144 9089 98632 238236 79093 101104 50327 237759 61236 275195 241153 116369 86842 272794 25675 121176 110170 225753 199931 ...
output:
result:
Subtask #3:
score: 0
Wrong Answer
Test #18:
score: 5
Accepted
time: 0ms
memory: 30424kb
input:
300 42 3 2 114 268 132 105 187 17 191 127 14 62 162 126 39 143 72 159 199 184 295 138 71 277 293 103 288 54 231 196 57 220 110 117 38 136 295 258 41 76 291 8 59 131 161 278 244 233 81 76 12 236 21 240 228 262 255 159 236 60 277 33 29 123 170 290 89 154 220 139 193 81 31 53 163 77 148 274 181 76 15 2...
output:
83
result:
ok single line: '83'
Test #19:
score: 5
Accepted
time: 2ms
memory: 24296kb
input:
300 178 3 2 277 106 123 105 235 290 273 34 300 180 43 55 239 74 19 138 110 201 295 18 207 97 238 177 114 24 195 219 154 186 151 294 143 291 47 293 33 99 2 46 101 39 109 240 15 256 43 121 205 261 267 257 81 167 82 23 300 182 13 46 195 221 163 17 109 93 144 23 110 17 153 129 91 243 281 74 135 72 145 1...
output:
4
result:
ok single line: '4'
Test #20:
score: 5
Accepted
time: 0ms
memory: 32460kb
input:
300 130 4 2 74 70 137 178 142 56 106 137 154 190 162 96 218 173 261 37 206 72 136 93 293 159 145 94 221 97 76 189 149 282 79 62 258 37 35 20 215 8 143 207 216 38 262 241 37 68 221 258 156 8 213 50 180 238 132 300 256 136 79 281 179 128 177 202 20 229 43 12 290 230 26 105 135 20 146 84 10 184 254 27 ...
output:
126
result:
ok single line: '126'
Test #21:
score: 5
Accepted
time: 0ms
memory: 26364kb
input:
300 49 4 2 199 123 264 232 60 265 215 2 226 189 160 11 200 217 194 175 295 203 20 165 203 63 132 127 42 259 170 293 230 269 20 166 141 96 149 210 246 122 5 185 90 156 297 21 300 78 24 94 139 154 268 258 53 15 267 67 221 248 298 154 136 254 192 234 142 170 56 217 90 25 228 216 216 186 61 90 14 221 27...
output:
26
result:
ok single line: '26'
Test #22:
score: 5
Accepted
time: 3ms
memory: 32484kb
input:
300 250 3 1 91 120 269 191 244 235 202 92 3 146 190 210 175 190 243 20 280 75 81 296 179 85 278 283 123 134 98 35 29 65 219 268 242 135 143 238 274 127 99 243 141 231 285 68 269 76 15 61 179 157 165 139 52 49 247 50 151 50 262 161 132 270 224 15 228 144 56 100 293 35 80 98 188 65 263 43 267 234 243 ...
output:
149
result:
ok single line: '149'
Test #23:
score: 5
Accepted
time: 3ms
memory: 26336kb
input:
300 205 3 1 43 211 182 106 31 159 33 141 50 122 33 108 65 275 218 285 263 71 39 211 41 91 264 151 211 286 298 228 84 96 292 176 78 239 107 28 247 265 132 182 225 257 70 58 165 61 162 35 221 23 168 234 279 130 111 261 157 34 61 47 299 97 129 233 247 245 280 60 137 252 241 248 275 91 251 178 288 181 2...
output:
45
result:
ok single line: '45'
Test #24:
score: 0
Wrong Answer
time: 0ms
memory: 30716kb
input:
300 151 10 4 106 66 88 78 279 12 92 142 298 168 98 117 8 108 104 192 50 216 227 176 77 297 149 195 94 11 72 69 235 267 261 11 131 35 115 146 140 73 132 251 185 145 29 193 52 90 287 39 261 300 24 206 223 59 270 35 225 35 32 95 184 244 52 164 276 118 220 268 249 251 187 217 288 71 297 34 171 198 178 2...
output:
44
result:
wrong answer 1st lines differ - expected: '2', found: '44'
Subtask #4:
score: 0
Skipped
Dependency #3:
0%
Subtask #5:
score: 0
Wrong Answer
Test #49:
score: 4
Accepted
time: 71ms
memory: 36128kb
input:
100000 20749 3 2 89778 51257 2293 75317 20142 42260 55350 69024 2419 90402 2248 71914 60607 94307 33933 57799 79884 93934 9788 53542 18109 28742 7700 93763 12102 78825 34580 61577 84344 12887 63610 12371 30988 75638 47533 66209 95296 22495 12638 545 36347 57495 41813 49592 60342 1881 38899 62345 524...
output:
43056
result:
ok single line: '43056'
Test #50:
score: 4
Accepted
time: 77ms
memory: 33800kb
input:
100000 81436 3 2 30487 98338 75456 42340 35081 95919 14744 79324 12767 72910 10330 15285 18425 40190 49306 55115 27041 60644 82901 10649 43365 29415 57822 86861 83007 50520 39798 89642 44146 63575 29824 89809 23549 45972 89791 83570 13656 1315 63396 74190 21244 80244 90922 97110 38966 92339 84884 89...
output:
717
result:
ok single line: '717'
Test #51:
score: 4
Accepted
time: 77ms
memory: 35944kb
input:
100000 8852 4 2 40452 57256 17799 88040 60724 53958 13290 90136 19267 49330 97135 48815 91159 71145 11677 334 6176 11175 2311 36476 80261 78319 22343 42921 53692 9431 20138 8540 15962 57516 66603 41779 22916 82799 36377 26000 46797 3889 5764 3600 76457 13146 41675 46067 65577 93967 3461 31914 46191 ...
output:
66085
result:
ok single line: '66085'
Test #52:
score: 4
Accepted
time: 75ms
memory: 33208kb
input:
100000 16035 4 2 43071 56048 63171 4393 98259 47823 2561 96442 9238 88690 85973 58025 9308 88080 16242 96064 88566 55956 57022 90692 84895 82151 27964 28817 24774 35654 35624 93885 37408 43501 89095 11303 1737 8666 378 67623 56302 11639 22263 32297 12188 72428 49974 80854 29579 370 70340 55421 4511 ...
output:
13134
result:
ok single line: '13134'
Test #53:
score: 4
Accepted
time: 65ms
memory: 37548kb
input:
100000 85235 3 1 94738 24340 59327 27917 90855 27869 97393 55723 50462 24028 27405 59525 40629 84195 41269 21311 97793 12448 94822 90533 96359 70118 59964 12798 51098 68286 58527 7816 41817 19034 10924 54535 63191 97115 60743 79349 6864 76498 29085 92310 8063 41260 11214 91868 23225 2976 50822 99018...
output:
86829
result:
ok single line: '86829'
Test #54:
score: 4
Accepted
time: 72ms
memory: 36340kb
input:
100000 96572 3 1 36159 41653 67667 34037 37976 63963 45201 5393 52221 59416 54961 13650 28764 99209 60804 67606 48624 79765 41041 83510 51667 65582 53730 45676 22269 64403 52565 21021 64941 4761 62855 69936 67203 18060 91572 33888 52593 86981 38287 22045 72710 6674 19970 36871 12501 91926 14428 9425...
output:
12008
result:
ok single line: '12008'
Test #55:
score: 4
Accepted
time: 77ms
memory: 33060kb
input:
100000 73324 10 4 71933 28912 87834 88149 44971 99521 60861 82846 97055 92782 56244 87280 53155 84157 70530 70324 79371 71634 21639 40110 75095 53060 6988 96059 21201 57449 65138 12755 88230 54355 87152 56089 86570 76587 79256 65685 16310 13946 41916 10874 9161 88963 90203 58683 76300 29464 25230 30...
output:
513
result:
ok single line: '513'
Test #56:
score: 4
Accepted
time: 48ms
memory: 32348kb
input:
100000 15636 100000 10 10243 50231 32391 7992 18149 2934 33787 51982 96445 22322 41361 80285 17777 24611 69149 49364 87021 54306 89564 43531 90973 83603 85869 90213 27390 88410 38427 49151 77811 41575 32541 86212 92924 21286 47549 65738 76763 15623 17786 10339 32880 76070 9809 67114 91819 43885 7140...
output:
1
result:
ok single line: '1'
Test #57:
score: 4
Accepted
time: 149ms
memory: 34824kb
input:
100000 42996 20 10 74902 50663 7097 23701 45735 7288 52375 46377 46724 63127 89073 24467 29104 28729 83469 85669 70860 88962 78797 72790 27570 86063 24686 20963 90850 57413 17431 29758 84798 67397 74951 85193 37009 12044 56862 33692 23929 61577 18914 38454 58446 32853 69649 68901 55638 59986 47751 1...
output:
221
result:
ok single line: '221'
Test #58:
score: 4
Accepted
time: 65ms
memory: 33824kb
input:
100000 98739 100 10 85414 42813 17848 77599 42506 71989 1918 745 9097 91249 79539 71491 71938 77961 66338 99594 19970 52870 38371 91469 69665 44311 13354 45803 56738 89880 46844 51870 38831 48646 37471 66852 2177 16313 35195 71674 8625 70549 1856 78239 9309 43203 4214 95780 29103 47895 69129 78296 4...
output:
14017
result:
ok single line: '14017'
Test #59:
score: 4
Accepted
time: 57ms
memory: 33676kb
input:
100000 29573 10000 10 54397 69025 83525 16322 69843 91831 18296 65353 43293 19327 70856 30469 80150 62236 40232 32171 68933 90628 66837 2965 54776 47328 62998 65584 23455 70312 34594 26099 90702 38631 99042 75615 83802 53660 60219 72548 22411 34554 71451 67910 31284 17953 55582 86186 80488 79094 180...
output:
4314
result:
ok single line: '4314'
Test #60:
score: 4
Accepted
time: 34ms
memory: 34472kb
input:
100000 80902 11 10 90717 1067 6057 7613 33217 91418 62156 49414 35712 58370 3406 3782 14422 36383 13121 54659 75065 82970 75833 76063 45137 74130 15269 84206 55939 35132 58683 99724 10608 64362 97967 78859 87661 3406 18955 76762 80678 25453 18179 44046 76792 92120 94865 94823 41467 53099 16426 15081...
output:
1
result:
ok single line: '1'
Test #61:
score: 4
Accepted
time: 0ms
memory: 20052kb
input:
100000 10278 10 10 22080 78739 83644 60650 84023 10536 67793 39227 64817 3246 95349 11887 32894 95918 57769 72231 70181 74963 19829 86171 64925 17589 77353 21140 73018 75509 80759 72751 77187 23048 67991 3801 84230 36205 67544 76682 47475 7799 55601 5047 33506 35435 84123 96632 55627 68456 12697 632...
output:
1
result:
ok single line: '1'
Test #62:
score: 4
Accepted
time: 0ms
memory: 20088kb
input:
56789 52146 3 3 5472 30471 5612 23037 21888 4725 9673 14647 40053 18588 21170 12453 8765 7882 10193 30274 4849 41647 31241 54244 14257 31966 15987 54036 16735 44259 53171 6717 55365 38027 42958 27812 48238 1399 3252 46229 5390 16924 29962 31185 34680 46655 43807 6253 1971 15286 53171 8341 8324 41346...
output:
1
result:
ok single line: '1'
Test #63:
score: 0
Wrong Answer
time: 404ms
memory: 33800kb
input:
87654 33545 100 10 76907 51162 2915 42413 34214 66794 26541 46255 64067 84944 39351 71693 45020 7870 24345 49823 43523 68748 18308 78976 46430 4311 73739 13607 4941 68811 33354 64770 22269 605 65058 33589 73005 12430 4881 65990 15196 24871 74977 64963 26162 16647 25414 25820 62913 18924 45927 6426 5...
output:
1454
result:
wrong answer 1st lines differ - expected: '312', found: '1454'
Subtask #6:
score: 0
Skipped
Dependency #4:
0%
Subtask #7:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
0%