QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#812002 | #8806. Summer Driving | kkkgjyismine4 | 9 | 740ms | 20132kb | C++20 | 2.2kb | 2024-12-13 10:38:06 | 2024-12-13 10:38:06 |
Judging History
answer
#include<bits/stdc++.h>
#define N 300005
#define pb push_back
using namespace std;
const int inf=1e9;
int n,rt,A,B,up[N][20],dep[N];
vector<int>rd[N],d[N];
int f[N],g[N],h[N],dh[N],sz[N],dfn[N],low[N],son[N],len[N],fa[N];
int Mx[N],Mx1[N],mx[N],mx1[N];
void dfs(int u,int f){
up[u][0]=fa[u]=f,son[u]=-1,d[dep[u]].pb(u),sz[u]=1;
for(int i=1;(1<<i)<=dep[u];++i)up[u][i]=up[up[u][i-1]][i-1];
Mx[u]=Mx1[u]=-1;
for(int v:rd[u]){
if(v==f)continue;
dep[v]=dep[u]+1,dfs(v,u),sz[u]+=sz[v],len[u]=max(len[u],len[v]+1);
if(son[u]==-1||sz[v]>sz[son[u]])son[u]=v;
if(Mx[u]==-1)Mx[u]=v;else Mx1[u]=v;
}
}
int LCA(int u,int v){
if(dep[u]<dep[v])swap(u,v);
for(int i=19;i>=0;--i)if(up[u][i]&&dep[up[u][i]]>=dep[v])u=up[u][i];
if(u==v)return u;
for(int i=19;i>=0;--i)if(up[u][i]!=up[v][i])u=up[u][i],v=up[v][i];
return up[u][0];
}
int dis(int u,int v){return dep[u]+dep[v]-2*dep[LCA(u,v)];}
int getkth(int u,int k){
for(int i=19;i>=0;--i)if((k>>i)&1)u=up[u][i];
return u;
}
void upd(int p){
int q=fa[p];
if(Mx[q]==p)return;
if(Mx1[q]==p){
if(h[p]>h[Mx[q]])swap(Mx[q],Mx1[q]);
return;
}
if(h[p]>=h[Mx[q]])Mx1[q]=Mx[q],Mx[q]=p;
else if(Mx1[q]==-1||h[p]>=h[Mx1[q]])Mx1[q]=p;
}
int main(){
ios::sync_with_stdio(0);
cin>>n>>rt>>A>>B;
for(int i=1;i<=n;++i)h[i]=0,dh[i]=inf;
if(A<=B)cout<<1<<endl,exit(0);
for(int i=1,a,b;i<n;++i)cin>>a>>b,rd[a].pb(b),rd[b].pb(a);
dfs(rt,0);
for(int i=1;i<=n;++i)if(len[i]<A)f[i]=inf;
for(int i=1;i<=n;++i){
if(len[i]<A)f[i]=min(f[i],i);
for(int x=fa[i],lst=i,c=1;c<=B&&x;++c,x=fa[x],lst=fa[lst]){
for(int v:rd[x])if(v!=fa[x]&&v!=lst)dh[v]=min(dh[v],i);
if(len[x]<A)f[x]=min(f[x],i);
}
}
for(int dd=n;dd>=0;--dd){
if(dd+A<=n){
for(int v:d[dd+A]){
g[v]=inf;
for(int i=1;i<=n;++i){
if(dep[i]<dep[v]&&getkth(v,dep[v]-dep[i])==i)continue;
if(dis(i,v)<=B)g[v]=min(g[v],f[i]);
}
for(int x=fa[v],lst=v,c=1;c<=B;++c,x=fa[x],lst=fa[lst]){
int ans=0;
if(Mx[x]!=lst)ans=h[Mx[x]];
else if(Mx1[x]!=-1)ans=h[Mx1[x]];
if(ans==0)ans=min(x,dh[lst]);
g[v]=min(g[v],ans);
}
int q=getkth(v,A),p=getkth(v,A-1);
f[q]=max(f[q],g[v]),h[p]=max(h[p],g[v]);
upd(p);
}
}
}cout<<f[rt];
return 0;
}
詳細信息
Subtask #1:
score: 1
Accepted
Test #1:
score: 1
Accepted
time: 2ms
memory: 7688kb
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: 1ms
memory: 7780kb
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: 7660kb
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: 7776kb
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: 1ms
memory: 7684kb
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: 5
Accepted
Test #18:
score: 5
Accepted
time: 5ms
memory: 16032kb
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: 5ms
memory: 18016kb
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: 7ms
memory: 17936kb
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: 15992kb
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: 7ms
memory: 15932kb
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: 4ms
memory: 20132kb
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: 4ms
memory: 15920kb
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: 3ms
memory: 16000kb
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: 2ms
memory: 7724kb
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: 0ms
memory: 17944kb
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: 6ms
memory: 18032kb
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: 3
Accepted
Dependency #3:
100%
Accepted
Test #29:
score: 3
Accepted
time: 487ms
memory: 18220kb
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:
878
result:
ok single line: '878'
Test #30:
score: 3
Accepted
time: 589ms
memory: 16336kb
input:
3000 528 3 2 2749 507 78 1098 1114 832 608 2375 2044 319 1549 1782 2146 1096 2728 817 1542 394 1362 2837 2714 2424 141 1693 190 2792 424 2422 2891 1525 1796 1932 2241 1427 790 1721 1044 1909 1240 2843 2964 1850 1587 2274 1249 1126 1 1689 2558 994 2911 2148 1160 1580 2530 2574 1402 1723 961 1518 2520...
output:
4
result:
ok single line: '4'
Test #31:
score: 3
Accepted
time: 475ms
memory: 16388kb
input:
3000 458 4 2 943 1128 2440 1236 1649 2508 2922 420 1540 1811 1710 566 1260 668 2124 858 78 373 551 1017 1611 1744 536 104 1999 2934 2391 354 765 675 301 316 301 1613 2919 2533 2604 301 443 1540 2287 1580 397 1970 1925 1439 2478 2414 2189 1169 521 2182 1700 163 2575 334 477 1728 581 332 45 2170 1485 ...
output:
1318
result:
ok single line: '1318'
Test #32:
score: 3
Accepted
time: 591ms
memory: 16460kb
input:
3000 2841 4 2 1502 2819 421 217 1423 1914 1968 2313 1207 544 2752 1319 2459 1345 2192 2421 1320 1368 2936 971 637 1964 1328 1901 1568 1868 1544 1357 308 2198 1883 2064 978 685 336 2521 2173 1402 1288 1166 1514 684 2369 771 1339 738 1446 2786 1060 1543 375 1947 1756 1912 1397 288 609 2230 1015 1187 2...
output:
174
result:
ok single line: '174'
Test #33:
score: 3
Accepted
time: 483ms
memory: 16400kb
input:
3000 2364 3 1 1809 381 674 1824 2549 125 1469 1465 1144 2486 1177 862 2559 1927 1211 36 630 739 2926 1555 1169 2479 2984 2956 1669 1009 398 2796 469 991 1886 2628 2770 2725 1216 1394 703 76 2016 1162 722 1840 78 2793 326 1057 918 1887 1291 2478 1160 1312 2990 801 2969 212 1727 2594 1727 1862 2541 62...
output:
2143
result:
ok single line: '2143'
Test #34:
score: 3
Accepted
time: 606ms
memory: 16116kb
input:
3000 2398 3 1 1889 2450 812 2135 1493 638 1854 1137 1252 648 166 265 1679 1601 1655 2909 1715 1976 1546 1236 2328 2749 983 332 515 133 1557 2018 2253 2065 756 358 2707 1881 706 944 2950 1419 359 2541 1612 628 2622 2164 2567 1293 1984 336 2502 2151 2056 780 59 374 1830 1407 102 1355 2783 1881 1798 15...
output:
149
result:
ok single line: '149'
Test #35:
score: 3
Accepted
time: 644ms
memory: 16116kb
input:
3000 1828 10 4 2915 1223 1673 262 2847 1682 2587 2184 1017 2101 847 948 882 1914 2341 737 1979 1325 1760 1181 2399 742 1265 589 2879 946 1350 1387 2257 460 2101 1349 1985 1386 2132 1234 2582 2928 1454 1911 2819 2291 2016 1584 2738 1284 1523 1881 2630 1557 2830 2492 2967 509 195 2535 2119 1901 1356 2...
output:
82
result:
ok single line: '82'
Test #36:
score: 3
Accepted
time: 0ms
memory: 16156kb
input:
3000 796 3000 10 1508 2938 1186 502 322 2126 1138 1034 1829 1180 897 2854 2944 1095 139 1107 934 599 2851 2720 2328 237 910 796 2326 2751 2034 1301 40 2974 1657 52 684 1644 1610 1646 273 2528 290 2608 2701 2094 1070 837 1574 834 1765 990 2457 1107 2239 449 129 2697 2871 1560 352 2310 1795 2670 673 9...
output:
1
result:
ok single line: '1'
Test #37:
score: 3
Accepted
time: 1ms
memory: 5736kb
input:
1234 899 3 3 232 1227 294 768 507 1064 255 524 116 946 1017 462 850 518 158 912 1190 127 451 1172 671 1119 279 853 706 634 144 243 1160 103 921 917 1078 748 320 1095 695 368 443 1089 186 39 548 540 1062 539 105 546 91 1188 333 462 930 1180 295 417 403 95 280 700 355 432 146 766 267 831 904 324 1047 ...
output:
1
result:
ok single line: '1'
Test #38:
score: 3
Accepted
time: 429ms
memory: 16256kb
input:
2345 36 100 50 1483 1104 731 1472 259 409 1410 1081 1914 802 45 1156 833 790 1092 900 1089 159 2235 2043 797 572 1616 1807 2027 1124 285 1920 607 1280 1034 114 1231 1540 777 1440 1507 2039 1603 3 681 1260 1053 2300 809 1913 1361 1763 1628 463 118 289 1395 2121 882 417 111 472 1279 1336 2324 136 2013...
output:
1
result:
ok single line: '1'
Test #39:
score: 3
Accepted
time: 740ms
memory: 16480kb
input:
3000 2763 10 5 2045 2874 920 2652 1567 2728 1201 2754 1503 1773 940 2797 440 1785 1936 2493 1789 1034 720 2004 1437 617 2787 256 427 757 224 2778 532 2547 2949 2504 1406 2895 1516 2218 2276 1366 742 2277 2636 2820 2465 1978 1742 696 553 697 930 421 1998 1400 188 684 423 2224 371 2083 471 3000 709 27...
output:
10
result:
ok single line: '10'
Test #40:
score: 3
Accepted
time: 727ms
memory: 16420kb
input:
3000 1809 100 50 970 2578 1613 803 2543 868 703 1731 1015 146 1894 806 2367 2708 704 2144 405 532 1795 1918 1337 1208 1084 1674 2609 2253 1847 1747 918 1461 1229 126 873 1948 2963 2499 1069 491 451 441 679 1752 2460 2688 149 557 1344 1848 2218 2066 31 895 1819 1349 37 750 2819 2216 504 2588 1571 226...
output:
1
result:
ok single line: '1'
Test #41:
score: 3
Accepted
time: 0ms
memory: 16404kb
input:
3000 428 1000 500 1235 2483 1038 1248 1686 1427 2539 417 1375 1120 1014 1266 647 2715 918 67 1920 1640 2892 543 2060 1215 816 292 2020 2318 2626 2711 1422 2207 605 2528 1035 1638 2716 2636 2101 2731 1720 2467 2239 1502 1418 2581 2039 2763 342 1047 2214 1403 2508 1845 330 2864 2069 1601 2439 1432 682...
output:
1
result:
ok single line: '1'
Test #42:
score: 3
Accepted
time: 4ms
memory: 16176kb
input:
3000 1830 10 5 707 2455 238 293 2333 1830 2357 142 2284 917 1948 951 626 1368 1644 2504 1736 552 2787 749 2072 626 1030 1830 2398 1863 1077 1265 1334 1117 681 1690 1552 890 2710 612 2675 1268 1755 1736 432 138 2902 1739 1692 1074 1443 1579 130 138 155 2440 469 2119 2537 784 1413 1830 1745 2420 1721 ...
output:
1
result:
ok single line: '1'
Test #43:
score: 3
Accepted
time: 0ms
memory: 16416kb
input:
3000 447 100 50 2018 1373 2585 1432 1765 2078 101 1994 2830 1867 2834 1388 2767 1133 2378 434 185 2560 1241 850 762 750 961 1204 1847 1893 481 304 2749 1149 994 447 2142 2480 1057 573 2080 1204 165 1133 285 1299 2403 985 447 438 2592 463 2561 729 2296 447 563 2749 205 382 2139 528 888 2378 1850 1861...
output:
1
result:
ok single line: '1'
Test #44:
score: 3
Accepted
time: 4ms
memory: 18164kb
input:
3000 2724 1000 500 2050 1598 989 1852 125 1601 2439 1517 497 2510 618 2747 486 1367 1942 527 400 136 1471 2724 2875 486 2471 2594 1328 667 824 2802 607 391 240 2849 2711 2439 1202 1944 1347 989 2375 2168 933 1827 1106 178 2194 734 2419 2811 601 528 2890 822 635 2395 832 2594 1383 2202 2088 1041 933 ...
output:
1
result:
ok single line: '1'
Test #45:
score: 3
Accepted
time: 314ms
memory: 16396kb
input:
3000 1779 3 2 2992 2251 1763 2992 691 2992 2992 2102 2344 57 1163 2559 2798 2992 534 394 719 1163 139 2992 1163 946 203 181 588 2992 2992 2825 1370 1349 2992 962 2992 2856 2584 863 1786 2992 2743 2992 434 2992 2992 1293 20 2992 2477 706 2992 251 2853 517 2612 2992 2992 1350 2992 310 2311 1163 2992 1...
output:
1
result:
ok single line: '1'
Test #46:
score: 3
Accepted
time: 304ms
memory: 16376kb
input:
2999 7 3 2 2618 877 314 2309 698 2889 717 877 877 2045 1747 111 698 2915 877 1558 698 1157 1369 877 1442 698 877 1466 698 883 877 87 1479 910 877 2221 2217 877 410 877 877 2048 1692 877 1868 877 537 1913 795 678 1013 877 2174 877 877 2385 608 698 877 1476 94 698 877 422 1297 698 1774 1002 698 2264 1...
output:
1
result:
ok single line: '1'
Test #47:
score: 3
Accepted
time: 306ms
memory: 16320kb
input:
2998 1036 3 2 2608 498 2961 1017 2608 2159 39 1501 1686 2608 2608 1494 428 2608 2681 1713 2608 2226 2608 1961 1800 2577 434 2681 186 1561 2608 2666 1772 2608 2197 2416 2608 1651 1797 457 2903 2608 2385 2608 2400 1937 2608 2051 1424 372 2608 1034 2791 2608 2608 27 2608 659 900 2608 2028 1866 2681 397...
output:
2
result:
ok single line: '2'
Test #48:
score: 3
Accepted
time: 371ms
memory: 18832kb
input:
3000 40 300 160 52 244 261 122 1943 809 993 895 2718 1514 1252 1384 1376 2663 2050 2398 704 335 1045 1867 2846 2330 851 1543 2756 875 99 105 1765 2714 2218 1170 2586 2581 2340 2594 897 447 2235 2369 1648 1017 1353 1209 2553 2198 595 929 1928 2104 1523 1173 2526 2565 1696 474 2523 1581 1053 1968 1932...
output:
281
result:
ok single line: '281'
Subtask #5:
score: 0
Time Limit Exceeded
Test #49:
score: 0
Time Limit Exceeded
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:
result:
Subtask #6:
score: 0
Skipped
Dependency #4:
100%
Accepted
Dependency #5:
0%
Subtask #7:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
0%