QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#856184#8806. Summer Drivingffffyc5 2022ms135072kbC++144.0kb2025-01-13 17:48:082025-01-13 17:48:10

Judging History

你现在查看的是最新测评结果

  • [2025-01-13 17:48:10]
  • 评测
  • 测评结果:5
  • 用时:2022ms
  • 内存:135072kb
  • [2025-01-13 17:48:08]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define ll long long
namespace IO{//by cyffff
    int len=0;
    char ibuf[(1<<21)+1],*iS,*iT,out[(1<<25)+1];
    #if ONLINE_JUDGE
    #define gh() (iS==iT?iT=(iS=ibuf)+fread(ibuf,1,(1<<21)+1,stdin),(iS==iT?EOF:*iS++):*iS++)
    #else
    #define gh() getchar()
    #endif
    #define reg register
    inline int read(){
        reg char ch=gh();
        reg int x=0;
        reg char t=0;
        while(ch<'0'||ch>'9')   t|=ch=='-',ch=gh();
        while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=gh();
        return t?-x:x;
    }
    inline void putc(char ch){
        out[len++]=ch;
    }
    template<class T>
    inline void write(T x){
        if(x<0)putc('-'),x=-x;
        if(x>9)write(x/10);
        out[len++]=x%10+48;
    }
    inline void flush(){
        fwrite(out,1,len,stdout);
        len=0;
    }
    inline char getc(){
        char ch=gh();
        while(ch<'A'||ch>'Z') ch=gh();
        return ch;
    }
}
using IO::read;
using IO::write;
using IO::flush;
using IO::getc;
using IO::putc;
#define pii pair<int,int>
#define mpr make_pair
#define fir first
#define sec second
const int N=3e5+10,INF=1e9;
int n,r,A,B,fa[N],dep[N],dfn[N],low[N],idfn[N],tim,p[N],stk[N],top;
int f[N],g[N],h[N],mxd,d0[N],d1[N];
vector<int>a[N],b[N],sl[N],tl[N],sd[N];
inline void add(int u,int v){
    a[u].push_back(v);
}
inline void dfs(int x,int fa){
    idfn[dfn[x]=++tim]=x,::fa[x]=fa;
    stk[++top]=x,dep[x]=dep[fa]+1,mxd=max(mxd,dep[x]);
    if(top>A) sl[stk[top-A]].push_back(x);
    if(top>=A) tl[stk[top-A+1]].push_back(x);
    sd[dep[x]].push_back(x);
    for(auto t:a[x]){
        if(t==fa) continue;
        dfs(t,x),b[x].push_back(t);
    }
    low[x]=tim,top--;
//    printf("%d %d %d %d\n",x,dfn[x],low[x],dep[x]);
}
struct Segment_Tree{
	#define ls (rt<<1)
	#define rs (rt<<1|1)
	int tag[N<<2];
	inline void pushtag(int rt,int v){
		tag[rt]=min(tag[rt],v);
	}
	inline void build(int rt,int l,int r){
		tag[rt]=INF;
		if(l==r) return ;
		int mid=l+r>>1;
		build(ls,l,mid),build(rs,mid+1,r);
	}
	inline void modify(int rt,int l,int r,int L,int R,int v){
		if(L<=l&&r<=R) return pushtag(rt,v);
		int mid=l+r>>1;
		if(L<=mid) modify(ls,l,mid,L,R,v);
		if(R>mid) modify(rs,mid+1,r,L,R,v);
	}
	inline int query(int rt,int l,int r,int p){
		if(l==r) return tag[rt];
		int mid=l+r>>1,ans=tag[rt];
		if(p<=mid) ans=min(ans,query(ls,l,mid,p));
		else ans=min(ans,query(rs,mid+1,r,p));
		return ans;
	}
}T;
inline bool check(int x){//最终是否会走到 <=x 的点 A 最大化 B 最小化 
//	printf("---check(%d)---\n",x);
	T.build(1,1,n);
	for(int d=mxd;d;d--){
		if(d+A<=mxd)
			for(auto i:sd[d+A])
				g[i]=min(d1[i],dep[i]+T.query(1,1,n,dfn[i]))<=B;//,printf("g[%d]=%d\n",i,g[i]);
		for(auto i:sd[d]){
			d0[i]=i<=x?0:INF;
			int cnt=i<=x,cg=0;
			for(auto j:b[i])
				d0[i]=min(d0[i],d0[j]+1),cnt+=d0[j]<B;
			if(!sl[i].size()) f[i]=d0[i]<=B;
			else{
				f[i]=1;
				for(auto j:sl[i])
					f[i]&=g[j],cg+=!g[j];
			}
//			printf("f[%d]=%d\n",i,f[i]);
			for(auto j:b[i]){
				if(sl[i].size()==tl[j].size()) h[j]=cnt>=2||(cnt&&d0[j]>=B);//,printf("! %d %d %d\n",i,j,d0[j]>=B);
				else{
					int tg=0;
					for(auto k:tl[j])
						tg+=!g[k];
					h[j]=tg==cg;
				}
			}
			d1[i]=f[i]?0:INF;
			for(auto j:b[i])
				d1[i]=min(d1[i],d1[j]+1);
			int pr=INF,sf=INF;
			for(int j=0;j<b[i].size();j++)
				T.modify(1,1,n,dfn[b[i][j]],low[b[i][j]],min(pr,h[b[i][j]]?-d:INF)),pr=min(pr,d1[b[i][j]]+1);
			for(int j=b[i].size()-1;j>=0;j--)
				T.modify(1,1,n,dfn[b[i][j]],low[b[i][j]],min(sf,h[b[i][j]]?-d:INF)),sf=min(sf,d1[b[i][j]]+1);
		}
	}
	return f[r];
}
int main(){
    n=read(),r=read(),A=read(),B=read();
    if(A<=B) return puts("1"),0;
    for(int i=1;i<n;i++){
        int u=read(),v=read();
        add(u,v),add(v,u);
    } 
    dfs(r,r);
    int L=1,R=n,ans=n+1;
    while(L<=R){
        int mid=L+R>>1;
        if(check(mid)) R=mid-1,ans=mid;
        else L=mid+1;
    }
    write(ans);
    flush();
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 1
Accepted

Test #1:

score: 1
Accepted
time: 3ms
memory: 46636kb

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: 46544kb

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: 2ms
memory: 44492kb

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: 3ms
memory: 44624kb

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: 3ms
memory: 42576kb

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: 1918ms
memory: 134300kb

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: 1872ms
memory: 134892kb

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: 882ms
memory: 135072kb

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: 865ms
memory: 133880kb

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: 1810ms
memory: 128968kb

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: 1398ms
memory: 115724kb

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: 1409ms
memory: 115104kb

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: 1745ms
memory: 124804kb

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: 4ms
memory: 44628kb

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: 1957ms
memory: 134796kb

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: 2022ms
memory: 134272kb

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: 6ms
memory: 42424kb

input:

2 2 1 1
2 1

output:

1

result:

ok single line: '1'

Subtask #3:

score: 0
Wrong Answer

Test #18:

score: 0
Wrong Answer
time: 4ms
memory: 46716kb

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:

89

result:

wrong answer 1st lines differ - expected: '83', found: '89'

Subtask #4:

score: 0
Skipped

Dependency #3:

0%

Subtask #5:

score: 0
Wrong Answer

Test #49:

score: 0
Wrong Answer
time: 517ms
memory: 61048kb

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:

46096

result:

wrong answer 1st lines differ - expected: '43056', found: '46096'

Subtask #6:

score: 0
Skipped

Dependency #4:

0%

Subtask #7:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

0%