QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#839994 | #8806. Summer Driving | oceeff | 10 | 2721ms | 98296kb | C++14 | 2.8kb | 2025-01-02 13:30:59 | 2025-01-02 13:31:00 |
Judging History
answer
#include<bits/stdc++.h>
#include<ext/pb_ds/priority_queue.hpp>
#include<ext/pb_ds/assoc_container.hpp>
#ifdef ONLINE_JUDGE
#define getchar()(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1<<21],*p1=buf,*p2=buf;
#endif
using namespace std;using namespace __gnu_pbds;int read(){int num=0,f=1;char c;while(!isdigit(c=getchar()))if(c=='-')f=-1;while(isdigit(c))num=num*10+(c&15),c=getchar();return num*f;}void write(int x,char ch=' '){int F[20],cnt=0;if(!x)putchar('0');if(x<0)putchar('-'),x=-x;while(x)F[cnt++]=x%10+'0',x/=10;while(cnt)putchar(F[--cnt]);putchar(ch);}
namespace Main
{
const int N=300010,inf=1e9;int n,k,L,R,rt,A,B,f[N],g[N],h[N],dfn[N],low[N],ti,id[N],dep[N],fa[N],head[N],to[N<<1],nxt[N<<1],tag[N<<2],pl[N],pr[N],tot,x,y,z,xx,yy,zz;vector<int>b[N];__gnu_pbds::priority_queue<int,greater<int>,pairing_heap_tag>q[N];void link(int x,int y){to[++tot]=y,nxt[tot]=head[x],head[x]=tot;}
void dfs0(int x){int mn=x,se=inf;dep[x]=dep[fa[x]]+1,dfn[x]=++ti,id[ti]=x,b[dep[x]].emplace_back(dfn[x]),q[x].push(x);for(int i=head[x],y;i;i=nxt[i])if((y=to[i])!=fa[x]){fa[y]=x,dfs0(y);for(;dep[q[y].top()]-dep[x]>B;q[y].pop());if((z=q[y].top())<mn)se=mn,mn=z;else se=min(se,z);}low[x]=ti,g[x]=mn;for(int i=head[x],y;i;i=nxt[i])if((y=to[i])!=fa[x])h[y]=(q[y].top()==mn?se:mn),q[x].join(q[y]);if((y=dep[x]+A-1)<=n)pl[x]=lower_bound(b[y].begin(),b[y].end(),dfn[x])-b[y].begin(),pr[x]=lower_bound(b[y].begin(),b[y].end(),low[x]+1)-b[y].begin();}
void upd(int k,int l,int r,int L,int R,int z){if(L<=l&&r<=R)tag[k]=max(tag[k],z);else{int mid=(l+r)>>1;if(L<=mid)upd(k<<1,l,mid,L,R,z);if(mid<R)upd(k<<1|1,mid+1,r,L,R,z);}}int qry(int k,int l,int r,int p){if(l==r)return tag[k];int mid=(l+r)>>1;return max(tag[k],(p<=mid?qry(k<<1,l,mid,p):qry(k<<1|1,mid+1,r,p)));}
void dfs(int x){int mn=inf,se=inf,p1=0,p2=0,t1=0,t2=0;for(int i=head[x];i;i=nxt[i])if(to[i]!=fa[x]){dfs(to[i]);if(f[to[i]]<mn)se=mn,mn=f[to[i]];else se=min(se,f[to[i]]);}f[x]=mn+1,yy=dep[x]+A;for(int i=head[x],y;i;i=nxt[i])if((y=to[i])!=fa[x]){if(pl[y]<pr[y]){t2=t1,t1=y;
for(int j=pl[y];j<pr[y];++j){xx=id[b[yy][j]];if(f[xx]>B&&dep[xx]>qry(1,1,n,dfn[xx])){p1=p2,p1=y;break;}}}upd(1,1,n,dfn[y],low[y],dep[x]+B-1-(f[to[i]]==mn?se:mn));}
for(int i=head[x],y;i;i=nxt[i])if((y=to[i])!=fa[x]&&((t1==y?t2:t1)?!(p1==y?p2:p1):(h[y]<=k)))upd(1,1,n,dfn[y],low[y],dep[x]+B);if(t1?!p1:(g[x]<=k))f[x]=0;}
bool check(){return memset(tag,0,(n+1)<<4),dfs(rt),!f[rt];}
void main()
{
n=read(),rt=read(),A=read(),B=read();if(A<=B)return write(1,'\n');for(int i=n;--i;)x=read(),y=read(),link(x,y),link(y,x);
dfs0(rt),L=1,R=n;for(;L<R;)k=(L+R)>>1,(check()?(R=k):(L=k+1));write(L,'\n');
}
}
int main()
{
const bool base=0,IO=1;int T;if(!base)T=1;else if(IO)T=read();else ios::sync_with_stdio(0),cin>>T;for(;T--;)Main::main();
return 0;
}
详细
Subtask #1:
score: 1
Accepted
Test #1:
score: 1
Accepted
time: 0ms
memory: 21500kb
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: 2ms
memory: 21492kb
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: 21560kb
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: 21560kb
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: 21756kb
input:
2 1 1 2 2 1
output:
1
result:
ok single line: '1'
Subtask #2:
score: 4
Accepted
Test #6:
score: 4
Accepted
time: 2370ms
memory: 98296kb
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:
1
result:
ok single line: '1'
Test #7:
score: 4
Accepted
time: 2689ms
memory: 98236kb
input:
299999 92073 2999 11 262905 260944 140896 162257 22797 193473 248112 247445 217760 68693 156294 167586 42291 233355 280566 247233 171395 239795 126564 179464 208554 185755 201665 156263 74786 85307 116366 163760 57326 143227 243541 149484 287792 283934 293052 265098 294245 296048 14582 36967 202999 ...
output:
245417
result:
ok single line: '245417'
Test #8:
score: 4
Accepted
time: 1044ms
memory: 98176kb
input:
298989 2 303 302 291949 291950 71254 71253 32103 32104 194290 194289 155694 155693 178665 178664 278674 278675 63793 63794 280321 280320 209075 209074 141282 141283 298423 298424 145067 145068 115803 115802 88974 88975 199766 199767 73340 73339 106776 106777 20786 20787 57085 57086 51034 51035 88299...
output:
3
result:
ok single line: '3'
Test #9:
score: 4
Accepted
time: 1030ms
memory: 98112kb
input:
298989 2 30001 30000 227255 227254 149938 149939 159449 159448 6194 6193 239990 239989 95657 95658 280931 280932 65015 65014 221854 221855 65661 65662 36912 36911 184778 184779 74520 74521 217578 217577 234314 234315 266126 266125 96469 96470 158616 158615 12920 12919 207237 207236 72167 72166 20226...
output:
3
result:
ok single line: '3'
Test #10:
score: 4
Accepted
time: 2533ms
memory: 96240kb
input:
289898 68514 42345 35 247935 196903 238347 177303 95489 261552 14797 183922 175677 109839 85928 186661 124668 74629 172100 214045 217602 46031 73083 257282 268102 276634 94408 248387 202292 208128 250155 61752 240022 256152 281659 223534 18580 272515 36 46287 247306 163047 90365 36426 241702 92561 6...
output:
289093
result:
ok single line: '289093'
Test #11:
score: 4
Accepted
time: 1973ms
memory: 98052kb
input:
298765 191954 298765 29876 158145 67683 17628 136757 153101 176403 952 52270 139224 227583 289601 4565 200272 19860 139873 277812 229381 251631 55892 22383 102701 27390 252623 286705 27875 223439 180032 271744 28933 296138 97573 294210 108654 126487 31902 223049 180647 68619 9869 147781 255029 23743...
output:
14
result:
ok single line: '14'
Test #12:
score: 4
Accepted
time: 2071ms
memory: 98140kb
input:
298765 33562 298764 29876 110929 69221 276688 201887 264415 65460 166102 272335 248892 186840 206217 296235 283621 86931 238780 122705 200845 137749 30491 75339 159784 24393 240809 7087 193364 245493 287660 2903 214506 285716 181040 49286 37334 6088 276968 3658 52998 220919 289624 131115 274518 6204...
output:
1
result:
ok single line: '1'
Test #13:
score: 4
Accepted
time: 2223ms
memory: 98252kb
input:
300000 1 150000 149999 139488 266956 75499 115106 197111 266846 75931 86565 243441 135464 194765 22597 286803 214206 236086 46031 227314 88097 71817 83460 61640 293618 211868 156133 1709 4302 274196 125332 204068 41865 21111 98062 21173 99704 125957 168343 251218 116725 230029 252274 195016 31148 11...
output:
2
result:
ok single line: '2'
Test #14:
score: 4
Accepted
time: 0ms
memory: 21496kb
input:
291234 289232 2 291234 56299 134830 146619 165289 230113 123453 264835 93343 140869 286284 36462 175435 204256 11688 180367 256764 193570 229161 64489 177626 22842 55205 118191 162946 194148 194973 96663 95195 157427 215291 227692 47027 219226 31692 198993 60149 39787 77693 127485 148991 216628 1999...
output:
1
result:
ok single line: '1'
Test #15:
score: 4
Accepted
time: 2297ms
memory: 98248kb
input:
300000 5 12 1 104098 71288 155929 237155 194885 110614 288708 131509 260955 5677 152237 222368 152814 51702 131846 277511 32293 143328 95240 144359 158319 206926 95983 78186 223795 104895 179277 77519 247023 263601 141002 229603 168689 271469 125125 273621 143596 40101 112050 30987 268143 178476 249...
output:
78
result:
ok single line: '78'
Test #16:
score: 4
Accepted
time: 2721ms
memory: 98232kb
input:
300000 18710 912 1 193195 34459 260311 292739 133324 164168 66161 138261 49021 172781 285599 274251 46667 124835 249174 273094 57936 232787 100855 137993 117133 208961 204288 165919 118007 11717 209150 1905 122223 56208 170266 110094 203532 80994 281756 254059 648 18645 264367 270340 276680 247873 2...
output:
246042
result:
ok single line: '246042'
Test #17:
score: 4
Accepted
time: 5ms
memory: 20300kb
input:
2 2 1 1 2 1
output:
1
result:
ok single line: '1'
Subtask #3:
score: 5
Accepted
Test #18:
score: 5
Accepted
time: 3ms
memory: 30388kb
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: 0ms
memory: 30668kb
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: 17764kb
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: 3ms
memory: 17764kb
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: 30944kb
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: 7ms
memory: 30572kb
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: 5
Accepted
time: 3ms
memory: 30664kb
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:
2
result:
ok single line: '2'
Test #25:
score: 5
Accepted
time: 6ms
memory: 20940kb
input:
300 203 300 10 2 182 179 26 120 101 281 271 236 75 260 242 121 271 32 66 277 14 98 47 152 83 231 39 145 93 23 127 203 76 76 252 65 31 33 62 60 201 154 147 42 83 13 203 203 2 265 292 96 30 23 85 23 64 220 30 189 277 296 44 63 110 107 202 61 93 134 286 65 122 133 241 152 142 97 84 209 202 267 47 255 8...
output:
1
result:
ok single line: '1'
Test #26:
score: 5
Accepted
time: 0ms
memory: 20524kb
input:
123 33 3 3 63 85 6 68 37 58 78 86 111 69 36 110 115 56 41 63 112 15 99 61 55 96 123 88 45 16 37 54 95 41 54 24 26 108 40 83 60 36 83 25 71 19 83 7 56 53 123 30 46 93 20 104 99 23 52 84 49 31 110 109 53 97 33 18 90 94 80 3 82 58 108 100 97 14 32 99 8 60 54 119 101 35 23 48 42 8 54 5 10 73 35 18 113 1...
output:
1
result:
ok single line: '1'
Test #27:
score: 5
Accepted
time: 3ms
memory: 21484kb
input:
231 165 100 50 114 20 131 183 182 20 31 36 210 93 13 188 175 5 154 63 48 24 205 90 146 153 129 186 156 106 27 82 49 198 89 42 111 146 203 142 87 20 98 188 65 63 196 118 15 102 137 75 101 67 143 160 130 197 186 209 50 172 47 224 4 220 59 41 148 16 32 182 131 90 87 225 177 77 149 30 93 33 51 106 185 1...
output:
1
result:
ok single line: '1'
Test #28:
score: 5
Accepted
time: 0ms
memory: 31288kb
input:
300 11 30 16 90 227 152 287 67 39 165 50 242 139 278 177 51 148 129 214 94 124 37 201 53 254 84 202 267 183 95 171 251 32 45 170 161 275 272 268 209 49 34 272 106 75 223 285 42 72 130 138 91 263 230 158 31 59 80 209 262 45 136 131 162 121 297 287 32 207 228 171 112 58 273 70 173 176 169 34 155 54 37...
output:
29
result:
ok single line: '29'
Subtask #4:
score: 0
Wrong Answer
Dependency #3:
100%
Accepted
Test #29:
score: 0
Wrong Answer
time: 6ms
memory: 19484kb
input:
3000 63 3 2 2155 250 1688 831 522 631 1755 1764 55 2251 2127 1756 1135 387 600 1437 182 1020 1802 1849 399 2974 1809 574 402 2032 2147 2561 1186 830 829 2804 1086 1237 82 414 892 375 107 2688 1857 1972 1162 324 1758 1763 1255 918 1553 908 849 1670 132 2126 2503 861 1906 1836 305 1063 922 6 2068 1435...
output:
756
result:
wrong answer 1st lines differ - expected: '878', found: '756'
Subtask #5:
score: 0
Wrong Answer
Test #49:
score: 0
Wrong Answer
time: 439ms
memory: 39392kb
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:
36290
result:
wrong answer 1st lines differ - expected: '43056', found: '36290'
Subtask #6:
score: 0
Skipped
Dependency #4:
0%
Subtask #7:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
100%
Accepted
Dependency #4:
0%