QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#302731#370. CityNATURAL68 122ms14788kbC++141011b2024-01-11 10:16:232024-01-11 10:16:24

Judging History

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

  • [2024-01-11 10:16:24]
  • 评测
  • 测评结果：8
  • 用时：122ms
  • 内存：14788kb
查看
  • [2024-01-11 10:16:23]
  • 提交

Encoder

#include<bits/stdc++.h>
#include "Encoder.h"
using namespace std;
int n,siz[250010],dfn[250010],tot;
vector<int>e[250010];
inline void dfs(int rt,int da)
{
    siz[rt]=1;dfn[rt]=++tot;
    for(int i:e[rt])
    {
        if(i==da)continue;
        dfs(i,rt);siz[rt]+=siz[i];
    }
    int s=1;
    while(s<siz[rt])s<<=1;
    tot+=s-siz[rt];siz[rt]=s;
    return ;
}
void Encode(int N,int A[],int B[])
{
    n=N;
    for(int i=0;i<n-1;++i)
    {
        e[A[i]].emplace_back(B[i]);
        e[B[i]].emplace_back(A[i]);
    }
    dfs(0,0);
    for(int i=0;i<n;++i)
	Code(i,dfn[i]|((31-__builtin_clz(siz[i]))<<25));
    return ;
}
Source code, Language: C++14

Device

#include<bits/stdc++.h>
#include "Device.h"
using namespace std;
void InitDevice(){return ;}
int Answer(long long S,long long T)
{
    int Mx=(1<<25)-1,dfns,dfnt,sizs,sizt;
    dfns=S&Mx,dfnt=T&Mx;
    sizs=1<<(S>>25);sizt=1<<(T>>25);
    if(dfns<=dfnt&&dfnt<=dfns+sizs-1)return 1;
    if(dfnt<=dfns&&dfns<=dfnt+sizt-1)return 0;
    return 2;
}
Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 8
Accepted

Test #1:

score: 8
Accepted
time: 0ms
memory: 13824kb

input:

10 45
0 5
0 2
4 3
6 4
0 6
2 8
6 9
2 1
5 7
5 0
0 2
8 0
0 7
0 6
1 0
4 0
0 3
0 9
5 2
5 8
7 5
5 6
1 5
4 5
5 3
9 5
8 2
7 2
2 6
2 1
2 4
3 2
2 9
7 8
6 8
8 1
8 4
3 8
9 8
6 7
1 7
4 7
3 7
9 7
1 6
6 4
6 3
6 9
4 1
1 3
9 1
3 4
9 4
9 3

output:

134217729 6 67108868 10 33554441 33554434 67108872 3 5 11

input:

Interaction has been finished!

output:

0
1
0
1
1
0
0
1
1
2
2
0
2
2
2
2
2
0
2
2
1
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
1
1
1
2
2
2
0
2
2
134217729

result:

ok

Test #2:

score: 8
Accepted
time: 6ms
memory: 13784kb

input:

10 45
6 2
0 7
6 9
7 6
0 8
5 4
8 1
7 3
0 5
7 0
0 5
8 0
0 3
6 0
0 1
0 9
4 0
0 2
5 7
8 7
7 3
6 7
7 1
7 9
4 7
7 2
5 8
5 3
5 6
1 5
9 5
4 5
2 5
8 3
6 8
1 8
9 8
8 4
2 8
3 6
3 1
9 3
4 3
2 3
6 1
9 6
4 6
2 6
1 9
1 4
2 1
4 9
9 2
4 2

output:

134217729 11 4 7 13 33554444 67108867 100663298 33554442 5

input:

Interaction has been finished!

output:

0
1
0
1
0
1
1
0
1
2
2
1
0
2
1
2
1
2
2
2
2
2
0
2
2
2
0
2
2
2
2
2
2
2
2
2
0
2
0
2
2
2
2
2
2
134217729

result:

ok

Test #3:

score: 8
Accepted
time: 6ms
memory: 13780kb

input:

10 45
0 9
0 7
7 3
6 2
6 1
9 8
6 4
7 5
3 6
7 0
9 0
3 0
0 6
4 0
1 0
8 0
0 2
0 5
9 7
7 3
7 6
7 4
1 7
8 7
2 7
7 5
9 3
9 6
4 9
1 9
8 9
9 2
5 9
3 6
4 3
1 3
3 8
2 3
5 3
4 6
6 1
8 6
2 6
6 5
4 1
4 8
4 2
5 4
8 1
1 2
1 5
2 8
5 8
2 5

output:

167772161 8 7 100663301 9 13 67108870 134217732 3 33554434

input:

Interaction has been finished!

output:

0
0
0
1
0
0
0
1
1
2
1
1
1
0
2
0
1
2
2
2
2
0
2
2
1
0
0
2
0
2
0
1
2
0
2
2
2
2
2
2
2
2
2
2
2
167772161

result:

ok

Test #4:

score: 8
Accepted
time: 0ms
memory: 14408kb

input:

10 45
3 8
9 6
7 4
7 5
7 9
5 2
0 3
3 1
0 7
7 0
3 0
0 9
6 0
1 0
8 0
0 5
0 2
4 0
7 3
9 7
7 6
1 7
7 8
7 5
2 7
7 4
9 3
6 3
1 3
8 3
5 3
3 2
4 3
9 6
9 1
8 9
5 9
2 9
9 4
1 6
6 8
6 5
2 6
4 6
1 8
5 1
1 2
1 4
8 5
2 8
8 4
5 2
4 5
2 4

output:

134217729 4 9 67108866 7 33554440 11 100663302 3 33554442

input:

Interaction has been finished!

output:

0
0
1
0
0
0
1
1
0
2
0
1
2
2
1
0
1
2
2
0
0
2
2
2
1
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
1
2
2
134217729

result:

ok

Test #5:

score: 8
Accepted
time: 0ms
memory: 12660kb

input:

10 45
8 7
6 8
7 0
2 5
9 0
4 5
1 9
3 9
5 7
7 0
0 9
0 5
0 8
3 0
0 1
2 0
4 0
0 6
7 9
7 5
8 7
7 3
1 7
2 7
7 4
6 7
5 9
9 8
3 9
1 9
2 9
9 4
9 6
5 8
5 3
1 5
2 5
5 4
5 6
3 8
1 8
2 8
8 4
6 8
3 1
2 3
4 3
6 3
2 1
1 4
6 1
4 2
6 2
4 6

output:

134217729 11 6 12 7 67108869 4 100663298 33554435 67108874

input:

Interaction has been finished!

output:

0
1
1
1
0
1
0
0
1
2
1
0
2
2
0
1
0
2
2
0
0
2
2
2
2
2
2
0
1
2
2
2
2
2
0
2
2
2
2
2
2
2
2
2
2
134217729

result:

ok

Test #6:

score: 8
Accepted
time: 6ms
memory: 13272kb

input:

9 36
3 6
4 3
6 8
4 2
3 1
0 7
0 4
7 5
7 0
5 0
0 4
0 3
2 0
1 0
6 0
0 8
7 5
4 7
3 7
2 7
1 7
6 7
8 7
5 4
5 3
5 2
5 1
6 5
8 5
3 4
4 2
4 1
4 6
8 4
2 3
3 1
6 3
8 3
1 2
2 6
2 8
1 6
8 1
6 8

output:

134217729 8 9 67108869 100663300 3 33554438 33554434 7

input:

Interaction has been finished!

output:

0
0
1
1
0
0
0
1
1
2
2
2
2
2
2
2
2
2
2
2
2
0
1
1
1
0
2
1
0
0
2
2
2
2
2
1
134217729

result:

points 1.0

Test #7:

score: 8
Accepted
time: 0ms
memory: 14428kb

input:

10 45
0 5
4 7
4 2
0 4
1 6
0 1
1 8
0 9
9 3
0 1
4 0
2 0
0 8
0 6
0 9
5 0
3 0
7 0
1 4
1 2
8 1
1 6
1 9
5 1
1 3
7 1
2 4
4 8
4 6
9 4
4 5
3 4
4 7
2 8
2 6
9 2
5 2
2 3
7 2
6 8
8 9
8 5
3 8
8 7
9 6
6 5
6 3
6 7
9 5
3 9
9 7
3 5
5 7
3 7

output:

134217729 67108871 5 12 67108867 2 8 4 9 33554443

input:

Interaction has been finished!

output:

1
0
0
1
1
1
0
0
0
2
2
0
1
2
2
2
2
0
2
2
2
2
2
1
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
0
2
2
2
2
134217729

result:

ok

Test #8:

score: 8
Accepted
time: 6ms
memory: 13308kb

input:

5 10
4 1
0 4
0 2
2 3
0 4
2 0
1 0
3 0
2 4
4 1
4 3
1 2
2 3
1 3

output:

100663297 3 33554436 5 33554434

input:

Interaction has been finished!

output:

1
0
0
0
2
1
2
2
1
2
100663297

result:

points 1.0

Test #9:

score: 8
Accepted
time: 0ms
memory: 12964kb

input:

7 21
4 1
2 5
0 6
0 4
0 2
5 3
0 4
1 0
0 6
0 2
0 5
3 0
4 1
6 4
2 4
4 5
4 3
6 1
1 2
1 5
1 3
2 6
5 6
3 6
2 5
2 3
5 3

output:

100663297 4 67108869 7 33554435 33554438 2

input:

Interaction has been finished!

output:

1
0
1
1
1
0
1
2
2
2
2
2
2
2
2
2
2
2
1
1
1
100663297

result:

points 1.0

Test #10:

score: 8
Accepted
time: 4ms
memory: 13008kb

input:

8 28
7 2
2 1
0 3
2 4
7 5
0 7
0 6
0 3
0 6
0 7
0 2
5 0
0 4
0 1
6 3
7 3
2 3
5 3
4 3
1 3
7 6
2 6
6 5
4 6
6 1
7 2
7 5
4 7
1 7
5 2
2 4
1 2
4 5
5 1
4 1

output:

134217729 5 67108868 2 6 8 11 100663299

input:

Interaction has been finished!

output:

1
1
1
1
0
1
1
2
2
2
2
2
2
2
2
2
2
2
1
1
0
0
2
1
0
2
2
2
134217729

result:

points 1.0

Test #11:

score: 8
Accepted
time: 4ms
memory: 12616kb

input:

6 15
0 3
1 4
1 5
4 2
0 1
1 0
0 5
4 0
0 3
0 2
1 5
4 1
1 3
2 1
5 4
3 5
5 2
3 4
2 4
3 2

output:

100663297 67108867 5 2 33554436 6

input:

Interaction has been finished!

output:

0
1
0
1
1
1
0
2
0
2
2
2
2
0
2
100663297

result:

points 1.0

Test #12:

score: 8
Accepted
time: 0ms
memory: 14056kb

input:

4 6
0 2
2 3
0 1
0 1
0 2
0 3
2 1
3 1
3 2

output:

67108865 4 33554434 3

input:

Interaction has been finished!

output:

1
1
1
2
2
0
67108865

result:

points 1.0

Subtask #2:

score: 0
Wrong Answer

Test #13:

score: 83.9265
Acceptable Answer
time: 58ms
memory: 14084kb

input:

700 244650
407 643
680 336
573 208
466 455
159 648
575 549
50 567
251 211
211 481
530 513
136 334
112 492
175 396
643 483
265 132
20 160
174 550
251 90
99 236
579 374
670 613
495 379
251 170
652 61
495 467
27 317
202 484
420 592
542 354
565 650
35 88
216 681
277 219
299 171
220 647
418 433
434 660
2...

output:

469762049 33557803 8202 2058 33563175 67111907 33563226 3497 3303 8836 67117198 3376 2636 33554476 8748 33562641 2928 33563149 8718 1322 100666587 201329412 2587 3051 3288 3185 1130 67108892 9 8813 33555761 8331 67117599 8263 33563145 234883926 2113 1182 3343 32 134221222 2656 2057 33557350 33563189...

input:

Interaction has been finished!

output:

0
0
0
0
1
0
1
1
1
1
0
0
1
0
1
1
1
0
1
1
1
1
0
1
1
0
1
0
0
1
1
1
0
1
1
1
1
1
1
0
1
0
0
0
0
1
1
0
0
1
1
0
1
1
0
0
0
1
1
0
0
1
0
0
1
0
0
0
1
1
1
1
0
1
0
1
1
1
0
1
1
1
1
0
0
0
1
1
0
0
1
0
1
1
0
1
0
0
1
0
0
1
1
0
1
1
1
1
0
1
1
1
1
1
1
0
1
1
0
0
1
0
0
1
0
1
0
0
0
1
0
0
1
0
1
1
1
1
1
0
1
0
0
0
1
0
0
0
0
1
...

result:

points 0.91224402950

Test #14:

score: 81.1254
Acceptable Answer
time: 66ms
memory: 12476kb

input:

699 243951
59 192
191 301
270 524
135 496
647 573
174 262
662 43
371 50
655 434
123 242
209 46
612 646
11 533
156 443
322 462
329 558
417 383
283 263
615 504
29 520
391 135
546 535
54 264
382 651
541 427
536 456
295 169
645 303
494 21
282 179
329 490
191 67
697 55
226 276
32 160
226 482
392 56
144 1...

output:

570425345 5844 33568600 5649 1580 33555104 1538 67114485 67114506 33559973 100673489 536870914 395 67109263 5877 67114866 10185 10172 14206 33554826 167782198 422 14150 33554573 33555853 251 100663498 100669240 14155 67109083 662 100673426 134219163 134218658 67110411 21962 134218156 14240 33568648 ...

input:

Interaction has been finished!

output:

1
0
1
1
1
1
0
1
0
0
0
0
1
0
0
1
0
1
0
0
0
1
0
1
1
1
1
0
0
1
1
1
0
0
1
1
1
0
0
1
0
1
1
1
0
0
0
0
1
0
0
0
1
0
1
1
0
0
0
0
0
1
1
0
0
0
1
0
1
1
0
1
1
1
0
0
0
0
1
0
1
0
1
1
0
1
0
0
1
1
1
0
1
0
0
1
1
0
1
1
0
1
1
0
1
1
0
1
0
0
0
0
0
0
0
0
0
0
1
0
1
1
0
0
0
1
1
0
1
1
1
1
0
1
0
1
0
0
1
1
1
0
0
1
1
0
0
1
0
0
...

result:

points 0.88179751670

Test #15:

score: 84.9956
Acceptable Answer
time: 58ms
memory: 13504kb

input:

700 244650
32 619
369 483
58 148
484 103
190 630
589 659
90 204
515 464
215 254
688 658
454 3
286 582
158 246
90 164
648 13
602 240
237 8
36 620
31 558
515 560
302 39
373 418
288 388
50 516
26 514
190 467
190 439
600 35
258 421
148 214
251 111
50 62
10 530
624 466
666 637
666 692
285 650
137 686
280...

output:

436207617 1067 2991 2838 201326916 100669783 3970 2315 33554548 33554796 201327757 134217822 6448 2860 33555599 1316 1113 2320 134219014 134217838 390 33556530 33558298 2442 6669 1290 33555244 3405 90 33555466 2870 167774598 33556882 100670281 2996 33557283 100665359 3990 264 67109181 201333001 1029...

input:

Interaction has been finished!

output:

1
1
0
1
1
1
0
0
0
0
1
1
0
0
1
1
1
1
0
1
1
1
1
1
0
1
0
1
0
1
1
0
1
1
1
1
1
0
1
1
1
0
0
0
0
0
1
1
1
1
1
0
0
1
1
1
1
0
0
1
1
1
0
0
1
1
1
0
1
0
1
0
1
1
0
0
1
1
0
1
1
1
1
1
0
1
0
1
0
0
0
1
1
0
1
1
0
1
0
0
1
0
1
0
1
0
1
1
0
0
0
0
0
1
0
1
1
1
0
0
0
1
0
0
0
1
1
1
1
1
1
0
0
1
0
0
0
1
1
1
0
0
0
0
1
1
0
0
0
1
...

result:

points 0.92386524730

Test #16:

score: 82
Acceptable Answer
time: 58ms
memory: 14020kb

input:

700 244650
230 624
291 145
565 474
12 535
152 335
438 692
136 13
199 155
255 47
546 152
293 254
427 131
71 388
31 231
124 522
503 23
320 545
322 480
674 535
247 415
301 163
226 63
560 367
361 103
391 149
483 661
262 632
337 79
45 59
182 489
526 425
275 369
256 598
42 487
125 63
661 23
181 152
366 29...

output:

536870913 16717 38174 134255879 16718 33885 5390 5130 67110169 268435462 17438 134236248 134255623 134217816 67141964 335560708 234899718 201330951 134219032 134222152 134251607 37133 67147032 268439558 67145736 67145804 201345031 34137 17487 18735 350 18442 201364742 33822 67109193 67141976 37901 1...

input:

Interaction has been finished!

output:

1
0
1
1
0
1
1
0
1
0
0
1
0
1
1
1
0
1
0
1
0
0
1
0
1
1
0
1
0
1
0
1
0
0
1
0
0
0
1
0
1
1
1
0
0
1
0
0
0
0
1
0
0
1
1
1
0
0
0
1
0
0
0
0
1
1
1
0
1
0
0
1
1
1
1
1
1
1
0
1
1
1
0
1
1
1
1
1
1
1
1
0
0
1
1
1
0
1
0
0
0
0
0
1
0
1
1
1
0
1
1
0
0
1
0
0
0
1
1
1
1
1
0
1
1
1
0
0
1
1
0
0
0
1
0
0
1
0
1
1
1
0
1
0
0
1
0
1
0
1
...

result:

points 0.89130434720

Test #17:

score: 0
Wrong Answer
time: 122ms
memory: 14788kb

input:

250000 250000
98377 99261
85304 211210
196850 193036
80796 130416
3160 72100
145991 142897
200915 46448
218676 213491
89680 96159
73896 8598
61659 226081
22401 122629
228272 20662
17177 215756
118511 136128
95692 43162
78229 30135
134970 150179
163578 188576
213241 99059
203107 94390
139934 51361
18...

output:

905969665 100362382 55510332 22082267 32662770 8591218 1148543 34489692 66726423 33434670 10741469 35941903 36072221 34482328 8494895 8261541 90027410 198094 36655872 87823791 36364747 37892640 4218481 8311633 63813494 21147921 72686213 33595316 30002279 42050036 34514189 25144160 682218 23959474 27...

input:

Interaction has been finished!

output:

2
2
1
1
2
0
0
0
2
1
2
0
2
0
2
0
1
0
0
2
1
2
2
0
2
0
0
2
2
2
1
2
2
2
2
1
1
2
2
1
1
2
0
1
1
0
0
2
2
1
0
1
0
2
2
1
1
2
0
1
2
2
2
0
2
0
1
1
1
1
2
2
0
0
2
2
2
2
2
0
2
2
2
2
1
2
2
2
1
2
1
0
2
0
0
0
0
1
2
1
2
1
1
1
1
0
0
0
2
2
0
2
1
2
2
2
2
2
2
0
2
2
2
2
0
2
2
1
0
2
1
2
2
2
0
1
0
1
1
2
1
2
2
0
0
2
1
2
2
1
...

result:

wrong answer Wrong Answer [6] (Query #121 returned 2 but expected 1)
English 繁體中文 简体中文

Server Time: 2024-11-29 16:30:04 | OpenSource Project