QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#505724#8806. Summer Drivinglyx123886a1238861 404ms37548kbC++144.4kb2024-08-05 10:05:182024-08-05 10:05:18

Judging History

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

  • [2024-08-05 10:05:18]
  • 评测
  • 测评结果:1
  • 用时:404ms
  • 内存:37548kb
  • [2024-08-05 10:05:18]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
template<class T> void chkmin(T &x,T y) {x=(y<x)?y:x;}
template<class T> void chkmax(T &x,T y) {x=(y>x)?y:x;}
#define pb emplace_back
#define LOCAL 0
#define open_file if(LOCAL) {freopen("a.in","r",stdin);freopen("a.out","w",stdout);}
const int MAXN=3e5+50;
int Ex[MAXN],Dp[MAXN];// Dp:(u->v:u) Ex:(u->all-{v'}:v')
int Fb[MAXN];
vector<int> g[MAXN],e[MAXN];int n,Root,A,B;
int dep[MAXN],rv[MAXN],dfn[MAXN],siz[MAXN],par[MAXN],son[MAXN],top[MAXN];

#define bro(v,u) for(int v:g[par[u]]) if(v!=u)

namespace part0 {  //(1) get edges (2) initalize Dp,Ex
    int stk[MAXN],fmx[MAXN],fmx2[MAXN];
    void dfs1(int u,int fa) {
        par[u]=fa;dep[u]=dep[fa]+1;
        siz[u]=1;
        stk[dep[u]]=u;
        if(dep[u]-1>=A) {
            // e[stk[dep[u]]-(A-1)].pb(u);
            e[ stk[dep[u]-(A-1)] ].pb(u);
        }

        fmx[u]=0;
        for(int v:g[u]) if(v!=fa) {
            dfs1(v,u);siz[u]+=siz[v];
            chkmax(fmx[u],fmx[v]+1);
            if(siz[v]>siz[son[u]]) son[u]=v;
        }

    }
    void dfs2(int u,int fa) {
        rv[dfn[u]=++dfn[0]]=u;
        top[u]=(son[fa]==u)?top[fa]:u;
        if(son[u]) dfs2(son[u],u);
        for(int v:g[u]) if(v!=fa&&v!=son[u]) {
            dfs2(v,u);
        }
    }
    namespace dsu {
        int fa[MAXN];
        int get_fa(int x) {return (fa[x]==x)?x:(fa[x]=get_fa(fa[x]));}
        int del(int x) {
            // assert(x!=Root);
            fa[x]=par[x];
            return get_fa(x);
        }
        void init() {
            for(int i=1;i<=n;++i) fa[i]=i;
        }
    };

    void work() {
        dfs1(Root,0);
        dfs2(Root,0);

        for(int u=1;u<=n;++u) {
            sort(g[u].begin(),g[u].end(),[&] (auto i,auto j){return dep[i]>dep[j];});
            if(dep[g[u].back()]<dep[u]) g[u].pop_back();
        }

        for(int u=1;u<=n;++u) 
            bro(v,u) chkmax(fmx2[u],fmx[v]+1);

        // for(int u=1;u<=n;++u) {
            // printf("[%d]",dep[u]);
            // for(auto v:g[u]) printf("%d,",dep[v]);puts("");
        // }
        
        dsu::init();
        for(int i=1;i<=n;++i) {
            // cerr<<i<<"\n";
            if(!Dp[i]&&fmx[i]<A) Dp[i]=i;
            for(int v:g[i]) if(!Ex[v]&&fmx2[v]<A) Ex[v]=i;

            for(int u=dsu::get_fa(i);u!=Root&&dep[i]-dep[par[u]]<=B;u=dsu::del(u)) {//it's B's turn
                bro(v,u) if(!Ex[v]&&fmx2[v]<A) Ex[v]=i;//bf heres
                if(!Dp[par[u]]&&fmx[par[u]]<A) Dp[par[u]]=i; 
                // cerr<<u<<"\n";
            }
        }


        for(int i=1;i<=n;++i) if(i!=Root&&fmx2[i]<A) {
            assert(Ex[i]);
        }
    }
};
using part0::fmx;
using part0::fmx2;
namespace part1 {
    #define For(v,u) for(int my_id=dfn[u],v=rv[my_id];my_id<=dfn[u]+siz[u]-1;++my_id,v=rv[my_id])
    void get_g(int u) {
        For(v,u) if(dep[v]-dep[u]<=B) chkmin(Fb[u],Dp[v]);
        // if(u==1) {
        //     printf("[%d]\n",dep[u]-dep[par[par[u]]]<=B);
        // }
        for(int y=u;(y!=Root)&&(dep[u]-dep[par[y]]<=B);y=par[y]) {
            // if(u==1) printf("*%d*\n",y);
            chkmin(Fb[u],Ex[y]);
            bro(v,u)    
                For(c,v) if(dep[c]+dep[u]-2*dep[par[y]]<=B)//!!
                    chkmin(Fb[u],Dp[c]);
        }
    } 
};
using part1::get_g ;

void gen() {
    scanf("%d%d%d%d",&n,&Root,&A,&B);
    if(A<=B) {
        puts("1");return ;
    }
    for(int i=1,u,v;i<n;++i) {
        scanf("%d%d",&u,&v);
        g[u].pb(v);
        g[v].pb(u);
    }
    for(int i=1;i<=n;++i) {
        Fb[i]=n+1;
        Dp[i]=Ex[i]=0;
    }

    part0::work();

    // return ;

    // printf("{%d}\n",Ex[1]);

    // return ;
    vector<int> perm;
    for(int i=1;i<=n;++i) perm.pb(i);
    sort(perm.begin(),perm.end(),[&] (auto i,auto j){return dep[i]>dep[j];});
    for(auto rt:perm) {
        if(fmx[rt]<A) continue;
        for(auto u:g[rt]) {
            if(fmx[u]<A-1) continue;
            int res=0;
            for(auto v:e[u]) {
                get_g(v);//the most hard one
                chkmax(res,Fb[v]);
            }
            chkmax(Dp[rt],res);
            bro(v,u) chkmax(Ex[v],res);
        }
    }

    // for(int i=1;i<=n;++i) printf("[%d,%d,%d]\n",Dp[i],Fb[i],Ex[i]);
    // printf("{%d}",Fb[1]);

    int ans=Dp[Root];
    printf("%d",ans);
}

int main() {
    open_file 
    gen() ;
    return 0;
}

详细

Subtask #1:

score: 1
Accepted

Test #1:

score: 1
Accepted
time: 0ms
memory: 20328kb

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

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

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

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

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: 0
Wrong Answer

Test #18:

score: 5
Accepted
time: 0ms
memory: 30424kb

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

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

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

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

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

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: 0
Wrong Answer
time: 0ms
memory: 30716kb

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:

44

result:

wrong answer 1st lines differ - expected: '2', found: '44'

Subtask #4:

score: 0
Skipped

Dependency #3:

0%

Subtask #5:

score: 0
Wrong Answer

Test #49:

score: 4
Accepted
time: 71ms
memory: 36128kb

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: 4
Accepted
time: 77ms
memory: 33800kb

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:

717

result:

ok single line: '717'

Test #51:

score: 4
Accepted
time: 77ms
memory: 35944kb

input:

100000 8852 4 2
40452 57256
17799 88040
60724 53958
13290 90136
19267 49330
97135 48815
91159 71145
11677 334
6176 11175
2311 36476
80261 78319
22343 42921
53692 9431
20138 8540
15962 57516
66603 41779
22916 82799
36377 26000
46797 3889
5764 3600
76457 13146
41675 46067
65577 93967
3461 31914
46191 ...

output:

66085

result:

ok single line: '66085'

Test #52:

score: 4
Accepted
time: 75ms
memory: 33208kb

input:

100000 16035 4 2
43071 56048
63171 4393
98259 47823
2561 96442
9238 88690
85973 58025
9308 88080
16242 96064
88566 55956
57022 90692
84895 82151
27964 28817
24774 35654
35624 93885
37408 43501
89095 11303
1737 8666
378 67623
56302 11639
22263 32297
12188 72428
49974 80854
29579 370
70340 55421
4511 ...

output:

13134

result:

ok single line: '13134'

Test #53:

score: 4
Accepted
time: 65ms
memory: 37548kb

input:

100000 85235 3 1
94738 24340
59327 27917
90855 27869
97393 55723
50462 24028
27405 59525
40629 84195
41269 21311
97793 12448
94822 90533
96359 70118
59964 12798
51098 68286
58527 7816
41817 19034
10924 54535
63191 97115
60743 79349
6864 76498
29085 92310
8063 41260
11214 91868
23225 2976
50822 99018...

output:

86829

result:

ok single line: '86829'

Test #54:

score: 4
Accepted
time: 72ms
memory: 36340kb

input:

100000 96572 3 1
36159 41653
67667 34037
37976 63963
45201 5393
52221 59416
54961 13650
28764 99209
60804 67606
48624 79765
41041 83510
51667 65582
53730 45676
22269 64403
52565 21021
64941 4761
62855 69936
67203 18060
91572 33888
52593 86981
38287 22045
72710 6674
19970 36871
12501 91926
14428 9425...

output:

12008

result:

ok single line: '12008'

Test #55:

score: 4
Accepted
time: 77ms
memory: 33060kb

input:

100000 73324 10 4
71933 28912
87834 88149
44971 99521
60861 82846
97055 92782
56244 87280
53155 84157
70530 70324
79371 71634
21639 40110
75095 53060
6988 96059
21201 57449
65138 12755
88230 54355
87152 56089
86570 76587
79256 65685
16310 13946
41916 10874
9161 88963
90203 58683
76300 29464
25230 30...

output:

513

result:

ok single line: '513'

Test #56:

score: 4
Accepted
time: 48ms
memory: 32348kb

input:

100000 15636 100000 10
10243 50231
32391 7992
18149 2934
33787 51982
96445 22322
41361 80285
17777 24611
69149 49364
87021 54306
89564 43531
90973 83603
85869 90213
27390 88410
38427 49151
77811 41575
32541 86212
92924 21286
47549 65738
76763 15623
17786 10339
32880 76070
9809 67114
91819 43885
7140...

output:

1

result:

ok single line: '1'

Test #57:

score: 4
Accepted
time: 149ms
memory: 34824kb

input:

100000 42996 20 10
74902 50663
7097 23701
45735 7288
52375 46377
46724 63127
89073 24467
29104 28729
83469 85669
70860 88962
78797 72790
27570 86063
24686 20963
90850 57413
17431 29758
84798 67397
74951 85193
37009 12044
56862 33692
23929 61577
18914 38454
58446 32853
69649 68901
55638 59986
47751 1...

output:

221

result:

ok single line: '221'

Test #58:

score: 4
Accepted
time: 65ms
memory: 33824kb

input:

100000 98739 100 10
85414 42813
17848 77599
42506 71989
1918 745
9097 91249
79539 71491
71938 77961
66338 99594
19970 52870
38371 91469
69665 44311
13354 45803
56738 89880
46844 51870
38831 48646
37471 66852
2177 16313
35195 71674
8625 70549
1856 78239
9309 43203
4214 95780
29103 47895
69129 78296
4...

output:

14017

result:

ok single line: '14017'

Test #59:

score: 4
Accepted
time: 57ms
memory: 33676kb

input:

100000 29573 10000 10
54397 69025
83525 16322
69843 91831
18296 65353
43293 19327
70856 30469
80150 62236
40232 32171
68933 90628
66837 2965
54776 47328
62998 65584
23455 70312
34594 26099
90702 38631
99042 75615
83802 53660
60219 72548
22411 34554
71451 67910
31284 17953
55582 86186
80488 79094
180...

output:

4314

result:

ok single line: '4314'

Test #60:

score: 4
Accepted
time: 34ms
memory: 34472kb

input:

100000 80902 11 10
90717 1067
6057 7613
33217 91418
62156 49414
35712 58370
3406 3782
14422 36383
13121 54659
75065 82970
75833 76063
45137 74130
15269 84206
55939 35132
58683 99724
10608 64362
97967 78859
87661 3406
18955 76762
80678 25453
18179 44046
76792 92120
94865 94823
41467 53099
16426 15081...

output:

1

result:

ok single line: '1'

Test #61:

score: 4
Accepted
time: 0ms
memory: 20052kb

input:

100000 10278 10 10
22080 78739
83644 60650
84023 10536
67793 39227
64817 3246
95349 11887
32894 95918
57769 72231
70181 74963
19829 86171
64925 17589
77353 21140
73018 75509
80759 72751
77187 23048
67991 3801
84230 36205
67544 76682
47475 7799
55601 5047
33506 35435
84123 96632
55627 68456
12697 632...

output:

1

result:

ok single line: '1'

Test #62:

score: 4
Accepted
time: 0ms
memory: 20088kb

input:

56789 52146 3 3
5472 30471
5612 23037
21888 4725
9673 14647
40053 18588
21170 12453
8765 7882
10193 30274
4849 41647
31241 54244
14257 31966
15987 54036
16735 44259
53171 6717
55365 38027
42958 27812
48238 1399
3252 46229
5390 16924
29962 31185
34680 46655
43807 6253
1971 15286
53171 8341
8324 41346...

output:

1

result:

ok single line: '1'

Test #63:

score: 0
Wrong Answer
time: 404ms
memory: 33800kb

input:

87654 33545 100 10
76907 51162
2915 42413
34214 66794
26541 46255
64067 84944
39351 71693
45020 7870
24345 49823
43523 68748
18308 78976
46430 4311
73739 13607
4941 68811
33354 64770
22269 605
65058 33589
73005 12430
4881 65990
15196 24871
74977 64963
26162 16647
25414 25820
62913 18924
45927 6426
5...

output:

1454

result:

wrong answer 1st lines differ - expected: '312', found: '1454'

Subtask #6:

score: 0
Skipped

Dependency #4:

0%

Subtask #7:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

0%