QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#812165 | #8806. Summer Driving | kkkgjyismine4 | 1 | 1995ms | 339152kb | C++20 | 5.5kb | 2024-12-13 12:23:22 | 2024-12-13 12:23:22 |
Judging History
answer
#include<bits/stdc++.h>
#define N 300005
#define M 6000005
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
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],dhh[N],sz[N],dfn[N],low[N],tt,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 top[N];
void dfs1(int u,int g){
dfn[u]=++tt,top[u]=g;
if(son[u]!=-1)dfs1(son[u],g);
for(int v:rd[u])if(!top[v]&&v!=son[u])dfs1(v,v);
int id=-1,id1=-1;
for(int v:rd[u]){
if(dep[v]<dep[u])continue;
if(id==-1||dhh[id]>=dhh[v])id1=id,id=v;
else if(id1==-1||dhh[id1]>dhh[v])id1=v;
}
for(int v:rd[u]){
if(dep[v]<dep[u])continue;
if(id!=v)dh[v]=dhh[id];
else if(id1!=-1)dh[v]=dhh[id1];
}
}
int getkth(int u,int k){for(int i=0;(1<<i)<=k;++i)if((k>>i)&1)u=up[u][i];return u;}
int mnv[N<<2];
#define ls (p<<1)
#define rs (p<<1|1)
#define mid (l+r>>1)
void pp(int p){mnv[p]=min(mnv[ls],mnv[rs]);}
void cg(int p,int l,int r,int q,int v){
if(l==r){mnv[p]=v;return;}
if(q<=mid)cg(ls,l,mid,q,v);else cg(rs,mid+1,r,q,v);pp(p);
}
int qry(int p,int l,int r,int a,int b){
int ans=inf;
if(a<=l&&r<=b)return mnv[p];
if(a<=mid)ans=min(ans,qry(ls,l,mid,a,b));
if(b>mid)ans=min(ans,qry(rs,mid+1,r,a,b));
return ans;
}
int Calc(int x,int 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]);
return ans;
}
int Qry(int x,int y){
if(x==y)return inf;
int ans=inf;
while(top[x]!=top[y]){
if(x!=top[x])ans=min(ans,qry(1,1,n,dfn[top[x]],dfn[x]-1));
ans=min(ans,Calc(fa[top[x]],top[x])),x=fa[top[x]];
}
if(x!=y)ans=min(ans,qry(1,1,n,dfn[y],dfn[x]-1));
return ans;
}
void upd(int p){
int q=fa[p];
if(Mx[q]==p);
else if(Mx1[q]==p){
if(h[p]>h[Mx[q]])swap(Mx[q],Mx1[q]);
return;
}else {
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;
}
cg(1,1,n,dfn[q],Calc(q,son[q]));
}
int Fa[N];
int Find(int r){return r==Fa[r]?r:(Fa[r]=Find(Fa[r]));}
int dis[N];
pii ff[M*4],*bit[2][N],*bit1[2][N],*cc=ff;
int upds[N][20],Rt[N][20],Mxd[N],col[2][N][20],bl[N][20],Sz[N],nrt,Mxz[N],vis[N];
void find(int u,int ffa,int cta){
Sz[u]=1,Mxz[u]=0;
for(int v:rd[u]){
if(vis[v]||v==ffa)continue;
find(v,u,cta),Sz[u]+=Sz[v],Mxz[u]=max(Mxz[u],Sz[v]);
}Mxz[u]=max(Mxz[u],cta-Sz[u]);
if(nrt==-1||Mxz[u]<Mxz[nrt])nrt=u;
}
int mxd;
void gd(int u,int ffa,int dn){
Sz[u]=1,mxd=max(mxd,dis[u]);
upds[u][dn]=dis[u],Rt[u][dn]=nrt;
for(int v:rd[u]){
if(v==ffa||vis[v])continue;
if(u==nrt)bl[v][dn]=v;
else bl[v][dn]=bl[u][dn];
dis[v]=dis[u]+1;
col[0][v][dn]=col[1][v][dn]=0;
if(dep[v]>dep[u])col[0][v][dn]=col[0][u][dn];
else col[1][v][dn]=col[1][u][dn];
gd(v,u,dn),Sz[u]+=Sz[v];
}
}
void solve(int u,int G,int dn){
nrt=-1,find(u,-1,G),u=nrt,mxd=0,vis[u]=1;
col[0][u][dn]=col[1][u][dn]=1,dis[u]=0,gd(u,-1,dn);
vector<pii>nxt;for(int v:rd[u])if(!vis[v])nxt.pb(make_pair(v,Sz[v]));
Mxd[u]=mxd,bit[0][u]=cc,cc+=mxd+1,bit[1][u]=cc,cc+=mxd+1;
bit1[0][u]=cc,cc+=mxd+1,bit1[1][u]=cc,cc+=mxd+1;
for(int i=0;i<=mxd;++i)bit[0][u][i]=bit[1][u][i]=make_pair(inf,-2),bit1[0][u][i]=bit1[1][u][i]=make_pair(inf,-1);
for(auto v:nxt)solve(v.fi,v.se,dn+1);
}
void add(int o,int p,int q,pii v){
for(int i=q+1;i<=Mxd[p]+1;i+=(i&-i)){
if(bit[o][p][i-1].se==v.se){
if(bit[o][p][i-1].fi>=v.fi)bit[o][p][i-1]=v;
}
else {
if(bit[o][p][i-1].fi>=v.fi)bit1[o][p][i-1]=bit[o][p][i-1],bit[o][p][i-1]=v;
else if(bit1[o][p][i-1].fi>=v.fi)bit1[o][p][i-1]=v;
}
assert(bit[o][p][i-1].se!=bit1[o][p][i-1].se);
}
}
int qry2(int o,int p,int q,int c){
if(q<0)return inf;q=min(q,Mxd[p]);int ans=inf;
for(int i=q+1;i;i&=(i-1)){
if(bit[o][p][i-1].se!=c)ans=min(ans,bit[o][p][i-1].fi);
if(bit1[o][p][i-1].se!=c)ans=min(ans,bit1[o][p][i-1].fi);
}
return ans;
}
void upd1(int p){
for(int i=0;i<20;++i){
if(!Rt[p][i])continue;
add(col[1][p][i],Rt[p][i],upds[p][i],make_pair(f[p],bl[p][i]));
}
}
int qry1(int p){
int ans=f[p];
for(int i=0;i<20;++i){
if(!Rt[p][i])continue;
ans=min(ans,qry2(0,Rt[p][i],B-upds[p][i],bl[p][i]));
if(!col[0][p][i])ans=min(ans,qry2(1,Rt[p][i],B-upds[p][i],bl[p][i]));
}return ans;
}
int main(){
ios::sync_with_stdio(0);
cin>>n>>rt>>A>>B;
for(int i=1;i<=n;++i)h[i]=0,dh[i]=dhh[i]=inf,Fa[i]=i;
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){
int x=Find(i);
while(x&&dep[i]-dep[x]<B)dhh[x]=i,Fa[x]=Find(fa[x]),x=Find(x);
}
for(int i=1;i<=n;++i)Fa[i]=i;
for(int i=1;i<=n;++i){
int x=Find(i);
while(x&&dep[i]-dep[x]<=B){
if(len[x]<A)f[x]=i;
Fa[x]=Find(fa[x]),x=Find(x);
}
}dfs1(rt,rt);
for(int i=1;i<=n;++i)if(son[i]!=-1)cg(1,1,n,dfn[i],Calc(i,son[i]));
solve(rt,n,0);
for(int dd=n;dd>=0;--dd){
if(dd+A<=n){
for(int v:d[dd+A]){
g[v]=min(qry1(v),Qry(v,getkth(v,B)));
int q=getkth(v,A),p=getkth(v,A-1);
if(f[q]<g[v])f[q]=g[v],upd1(q);
if(h[p]<g[v])h[p]=g[v],upd(p);
}
}
}cout<<f[rt];
return 0;
}
詳細信息
Subtask #1:
score: 1
Accepted
Test #1:
score: 1
Accepted
time: 3ms
memory: 11752kb
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: 3ms
memory: 13812kb
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: 14028kb
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: 11748kb
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: 2ms
memory: 9760kb
input:
2 1 1 2 2 1
output:
1
result:
ok single line: '1'
Subtask #2:
score: 0
Wrong Answer
Test #6:
score: 4
Accepted
time: 1967ms
memory: 338304kb
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: 1995ms
memory: 338448kb
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: 1004ms
memory: 337476kb
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: 1029ms
memory: 339152kb
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: 0
Wrong Answer
time: 1873ms
memory: 328568kb
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:
289094
result:
wrong answer 1st lines differ - expected: '289093', found: '289094'
Subtask #3:
score: 0
Wrong Answer
Test #18:
score: 5
Accepted
time: 3ms
memory: 48668kb
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: 0
Wrong Answer
time: 0ms
memory: 46892kb
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:
1
result:
wrong answer 1st lines differ - expected: '4', found: '1'
Subtask #4:
score: 0
Skipped
Dependency #3:
0%
Subtask #5:
score: 0
Wrong Answer
Test #49:
score: 4
Accepted
time: 214ms
memory: 107540kb
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: 0
Wrong Answer
time: 245ms
memory: 113184kb
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:
7
result:
wrong answer 1st lines differ - expected: '717', found: '7'
Subtask #6:
score: 0
Skipped
Dependency #4:
0%
Subtask #7:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
0%