QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#672151 | #8806. Summer Driving | OccDreamer | 0 | 0ms | 0kb | C++14 | 5.5kb | 2024-10-24 15:52:18 | 2024-10-24 15:52:19 |
answer
//code by Emissary
#include<bits/stdc++.h>
#define fi first
#define se second
#define vc vector
#define db double
#define ll long long
#define mk make_pair
#define pb push_back
#define PI pair<int,int>
#define ull unsigned long long
#define err cerr << " -_- " << endl
#define debug cerr << " ------------------- " << endl
#define input(x) freopen(#x".in","r",stdin)
#define output(x) freopen(#x".out","w",stdout)
#define NO puts("No")
#define YES puts("Yes")
//#define int long long
using namespace std;
namespace IO{
inline int read(){
int X=0, W=0; char ch=getchar();
while(!isdigit(ch)) W|=ch=='-', ch=getchar();
while(isdigit(ch)) X=(X<<1)+(X<<3)+(ch^48), ch=getchar();
return W?-X:X;
}
inline void write(int x){
if(x<0) x=-x, putchar('-');
if(x>9) write(x/10);
putchar(x%10+'0');
}
inline void sprint(int x){write(x), putchar(32);}
inline void eprint(int x){write(x), putchar(10);}
}using namespace IO;
const int MAXN = 6e5+5;
const int inf = 1e9;
int siz[MAXN], tot;
int stk[MAXN], topf, up[MAXN], ups[MAXN];
int de[MAXN], toid[MAXN], dfn[MAXN], maxd[MAXN];
int n, r, a, b, val[MAXN], fa[MAXN], Max[MAXN<<2];
int head[MAXN], ne[MAXN<<1], to[MAXN<<1], minn[MAXN<<2], cnt;
vc<int> d[MAXN], son[MAXN];
int dp1[MAXN], dp2[MAXN], dp3[MAXN];
inline void add(int x, int y){++cnt;to[cnt]=y;ne[cnt]=head[x];head[x]=cnt;}
inline void dfs(int x, int f){
stk[++topf]=x; siz[x]=1;
if(topf>=a+1) up[x]=stk[topf-a];
if(topf>=a) ups[x]=stk[topf-a+1];
de[x]=de[fa[x]=f]+1; dfn[x]=++tot; toid[tot]=x;
for(int i=head[x];i;i=ne[i]){
if(to[i]==f) continue;
dfs(to[i],x); son[x].pb(to[i]);
maxd[x]=max(maxd[x],maxd[to[i]]+1);
siz[x]+=siz[to[i]];
}
d[de[x]].pb(x); --topf;
return ;
}
inline void build(int p, int l, int r){
Max[p]=-inf;
if(l==r) return minn[p]=val[toid[l]]?de[toid[l]]:inf, void();
int mid=(l+r)>>1;
build(p<<1,l,mid); build(p<<1|1,mid+1,r);
return minn[p]=min(minn[p<<1],minn[p<<1|1]), void();
}
inline int chk(int p, int l, int r, int pos){
//cerr << "de:" << de[toid[pos]] << ' ' << Max[p] << endl;
if(de[toid[pos]]<=Max[p]) return 1;
if(l==r) return 0;
int mid=(l+r)>>1;
if(pos<=mid) return chk(p<<1,l,mid,pos);
return chk(p<<1|1,mid+1,r,pos);
}
inline void chkmax(int p, int l, int r, int L, int R, int v){
if(L>R) return ;
if(L<=l && r<=R) return Max[p]=max(Max[p],v), void();
int mid=(l+r)>>1;
if(L<=mid) chkmax(p<<1,l,mid,L,R,v);
if(R>mid) chkmax(p<<1|1,mid+1,r,L,R,v);
return ;
}
inline int ask(int p, int l, int r, int L, int R){
if(L<=l && r<=R) return minn[p];
int mid=(l+r)>>1, res=inf;
if(L<=mid) res=min(res,ask(p<<1,l,mid,L,R));
if(R>mid) res=min(res,ask(p<<1|1,mid+1,r,L,R));
return res;
}
inline void upd(int p, int l, int r, int pos, int v){
if(l==r) return minn[p]=v, void();
int mid=(l+r)>>1;
if(pos<=mid) upd(p<<1,l,mid,pos,v);
else upd(p<<1|1,mid+1,r,pos,v);
minn[p]=min(minn[p<<1],minn[p<<1|1]);
return ;
}
inline bool check(int x){
// cerr << "check:" << x << ' ' << maxd[r] << endl;
for(int i=1;i<=n;++i) val[i]=i<=x; build(1,1,n);
for(int i=1;i<=n;++i) dp1[i]=dp2[i]=1, dp3[i]=0;
for(int i=n;i>=1;--i){
for(auto j:d[i]){
if(val[j]==1) chkmax(1,1,n,dfn[j],dfn[j]+siz[j]-1,de[j]+b);
for(auto k:son[j]){
int l=dfn[j], r=dfn[j]+siz[j]-1;
int o=ask(1,1,n,dfn[k],dfn[k]+siz[k]-1);
if(val[j]==1) o=de[j]; int dis=o-de[j]; dis=b-dis+de[j];
chkmax(1,1,n,l,dfn[k]-1,dis), chkmax(1,1,n,dfn[k]+siz[k],r,dis);
//cerr << "lca=" << j << ' ' << k << ' ' << dis << endl;
}
}
}
//err;
for(int i=1;i<=n;++i){
if(maxd[i]<a){
int u=chk(1,1,n,dfn[i]);
dp1[i]=dp3[i]=chk(1,1,n,dfn[i]);
int p=ask(1,1,n,dfn[i],dfn[i]+siz[i]-1);
if(p-de[i]<=b) u=1;
for(auto j:son[i]) dp2[j]=u; dp1[i]=dp3[i]=u;
//if(dp3[i]==1) cerr << "node:" << i << ' ' << u << endl;
}
if(son[i].size()==1){
int ver=son[i][0];
int u=chk(1,1,n,dfn[i]);
int p=ask(1,1,n,dfn[i],dfn[i]+siz[i]-1);
if(p-de[i]<=b) u=1; dp2[ver]=u;
}
}
//err;
for(int i=1;i<=n<<2;++i) minn[i]=inf, Max[i]=-inf;
//err;
for(int i=n, e=i+b-1;e>=1;--i, --e){
if(i>=1){
for(auto j:d[i]){
if(dp2[j]==1) chkmax(1,1,n,dfn[j],dfn[j]+siz[j]-1,de[j]+b-1);
for(auto k:son[j]){
int l=dfn[j], r=dfn[j]+siz[j]-1;
int o=ask(1,1,n,dfn[k],dfn[k]+siz[k]-1);
if(val[j]==1) o=de[j]; int dis=o-de[j]; dis=b-dis+de[j];
chkmax(1,1,n,l,dfn[k]-1,dis), chkmax(1,1,n,dfn[k]+siz[k],r,dis);
}
if(dp1[j]==1) upd(1,1,n,dfn[j],de[j]);
}
}
for(auto j:d[e]){
dp3[j]|=chk(1,1,n,dfn[j]);
int u=ask(1,1,n,dfn[j],dfn[j]+siz[j]-1);
if(u-de[j]<=b) dp3[j]=1;
if(dp3[j]==0){
if(up[j]) dp1[up[j]]=0;
if(ups[j]) dp2[ups[j]]=0;
}
}
}
// for(int i=1;i<=n;++i){
// cout << "info:" << i << endl;
// cout << dp1[i] << ' ' << dp2[i] << ' ' << dp3[i] << endl;
// }
return dp1[r]==1;
}
int main(){
// input(aba); output(aba);
freopen("25.in","r",stdin);
n=read(), r=read(), a=read(), b=read();
if(a<=b) return eprint(1), 0;
for(int i=2;i<=n;++i){
int x, y;
x=read(), y=read();
add(x,y), add(y,x);
}
err;
dfs(r,0);
err;
int l=1, r=n, mid;
while(l<=r){
mid=(l+r)>>1;
// cerr << "range:" << l << ' ' << r << ' ' << mid << endl;
if(check(mid)) r=mid-1;
else l=mid+1;
}
eprint(l);
return 0;
}
/*
9 6 2 1
1 3
1 6
2 4
2 5
2 7
3 9
4 6
4 8
*/
详细
Subtask #1:
score: 0
Time Limit Exceeded
Test #1:
score: 0
Time Limit Exceeded
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:
result:
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
Time Limit Exceeded
Test #18:
score: 0
Time Limit Exceeded
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:
result:
Subtask #4:
score: 0
Skipped
Dependency #3:
0%
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:
0%
Subtask #7:
score: 0
Skipped
Dependency #1:
0%