QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#302725#370. CityNATURAL68 120ms15564kbC++141.0kb2024-01-11 10:06:042024-01-11 10:06:04

Judging History

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

  • [2024-01-11 10:06:04]
  • 评测
  • 测评结果：8
  • 用时：120ms
  • 内存：15564kb
查看
  • [2024-01-11 10:06:04]
  • 提交

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<<(31-__builtin_clz(siz[rt]));
    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]))<<23));
    return ;
}
源文件, 语言: 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<<23)-1,dfns,dfnt,sizs,sizt;
    dfns=S&Mx,dfnt=T&Mx;
    sizs=1<<(S>>23);sizt=1<<(T>>23);
    if(dfns<=dfnt&&dfnt<=dfns+sizs-1)return 1;
    if(dfnt<=dfns&&dfns<=dfnt+sizt-1)return 0;
    return 2;
}
源文件, 语言: C++14

详细

Subtask #1:

score: 8
Accepted

Test #1:

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

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:

33554433 6 16777220 10 8388617 8388610 16777224 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
33554433

result:

ok

Test #2:

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

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:

33554433 11 4 7 13 8388620 16777219 25165826 8388618 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
33554433

result:

ok

Test #3:

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

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:

41943041 8 7 25165829 9 13 16777222 33554436 3 8388610

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
41943041

result:

ok

Test #4:

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

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:

33554433 4 9 16777218 7 8388616 11 25165830 3 8388618

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
33554433

result:

ok

Test #5:

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

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:

33554433 11 6 12 7 16777221 4 25165826 8388611 16777226

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
33554433

result:

ok

Test #6:

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

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:

33554433 8 9 16777221 25165828 3 8388614 8388610 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
33554433

result:

points 1.0

Test #7:

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

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:

33554433 16777223 5 12 16777219 2 8 4 9 8388619

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
33554433

result:

ok

Test #8:

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

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:

25165825 3 8388612 5 8388610

input:

Interaction has been finished!

output:

1
0
0
0
2
1
2
2
1
2
25165825

result:

points 1.0

Test #9:

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

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:

25165825 4 16777221 7 8388611 8388614 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
25165825

result:

points 1.0

Test #10:

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

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:

33554433 5 16777220 2 6 8 11 25165827

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
33554433

result:

points 1.0

Test #11:

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

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:

25165825 16777219 5 2 8388612 6

input:

Interaction has been finished!

output:

0
1
0
1
1
1
0
2
0
2
2
2
2
0
2
25165825

result:

points 1.0

Test #12:

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

input:

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

output:

16777217 4 8388610 3

input:

Interaction has been finished!

output:

1
1
1
2
2
0
16777217

result:

points 1.0

Subtask #2:

score: 0
Wrong Answer

Test #13:

score: 92
Accepted
time: 58ms
memory: 12956kb

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:

117440513 8391979 8202 2058 8397351 16780259 8397402 3497 3303 8836 16785550 3376 2636 8388652 8748 8396817 2928 8397325 8718 1322 25169115 50334468 2587 3051 3288 3185 1130 16777244 9 8813 8389937 8331 16785951 8263 8397321 58723158 2113 1182 3343 32 33557926 2656 2057 8391526 8397365 16778299 2078...

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 1.0

Test #14:

score: 92
Accepted
time: 58ms
memory: 12692kb

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:

142606337 5844 8402776 5649 1580 8389280 1538 16782837 16782858 8394149 25176017 134217730 395 16777615 5877 16783218 10185 10172 14206 8389002 41953078 422 14150 8388749 8390029 251 25166026 25171768 14155 16777435 662 25175954 33555867 33555362 16778763 21962 33554860 14240 8402824 8402872 550 100...

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 1.0

Test #15:

score: 92
Accepted
time: 50ms
memory: 13904kb

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:

109051905 1067 2991 2838 50331972 25172311 3970 2315 8388724 8388972 50332813 33554526 6448 2860 8389775 1316 1113 2320 33555718 33554542 390 8390706 8392474 2442 6669 1290 8389420 3405 90 8389642 2870 41945478 8391058 25172809 2996 8391459 25167887 3990 264 16777533 50338057 1029 2605 33556816 2517...

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 1.0

Test #16:

score: 92
Accepted
time: 66ms
memory: 13496kb

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:

134217729 16717 38174 33592583 16718 33885 5390 5130 16778521 67108870 17438 33572952 33592327 33554520 16810316 83902468 58738950 50336007 33555736 33558856 33588311 37133 16815384 67112966 16814088 16814156 50350087 34137 17487 18735 350 18442 50369798 33822 16777545 16810328 37901 16650 50364486 ...

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 1.0

Test #17:

score: 0
Wrong Answer
time: 120ms
memory: 15564kb

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:

226492417 33253518 63898940 22082267 32662770 8591218 1148543 34489692 33171991 33434670 10741469 35941903 44460829 34482328 8494895 8261541 22918546 198094 45044480 87823791 44753355 12726816 4218481 8311633 30259062 21147921 22354565 33595316 30002279 8495604 42902797 25144160 682218 23959474 7272...

input:

Interaction has been finished!

output:

2
2
1
2
2
0
0
0
2
1
2
0
2
0
2
0
1
0
0
2
1
2
2
0
2
0
2
2
2
2
1
2
2
2
2
1
1
2
2
2
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
2
2
2
2
2
2
2
0
2
2
2
2
0
2
2
1
2
2
1
2
2
2
0
1
0
1
1
2
1
2
2
0
0
2
2
2
2
1
...

result:

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

服务器时间: 2024-11-29 17:32:33 | 开源项目