QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#812107#8806. Summer Drivingkkkgjyismine49 767ms24552kbC++203.7kb2024-12-13 11:37:172024-12-13 11:37:17

Judging History

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

  • [2024-12-13 11:37:17]
  • 评测
  • 测评结果:9
  • 用时:767ms
  • 内存:24552kb
  • [2024-12-13 11:37:17]
  • 提交

answer

#include<bits/stdc++.h>
#define N 300005
#define M 5500005
#define pb push_back
using namespace std;
const int inf=1e9;
int n,rt,A,B,up[N][20],dep[N];
int ff[M],*bit[2][N],*cc,Up[N][20],Rt[N][20],col[2][N][20],Sz[N],nrt,Mxz[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 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;
}
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 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]));
	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]);
				}
				g[v]=min(g[v],Qry(v,getkth(v,B)));
				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: 3ms
memory: 10948kb

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

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

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

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

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

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

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

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

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

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

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: 5ms
memory: 22080kb

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: 0ms
memory: 22128kb

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

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

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

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: 519ms
memory: 24340kb

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: 616ms
memory: 22352kb

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: 508ms
memory: 22292kb

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: 618ms
memory: 22332kb

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: 511ms
memory: 22300kb

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: 627ms
memory: 24552kb

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: 678ms
memory: 22296kb

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

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

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: 444ms
memory: 22504kb

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: 767ms
memory: 22396kb

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: 752ms
memory: 22452kb

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

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

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: 5ms
memory: 18504kb

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

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: 321ms
memory: 22296kb

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: 320ms
memory: 22548kb

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: 321ms
memory: 22276kb

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: 372ms
memory: 22876kb

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%