QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#303340#370. CityNATURAL68 126ms12588kbC++141.3kb2024-01-12 09:01:472024-01-12 09:01:48

Judging History

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

  • [2024-01-12 09:01:48]
  • 评测
  • 测评结果：8
  • 用时：126ms
  • 内存：12588kb
查看
  • [2024-01-12 09:01:47]
  • 提交

Encoder

#include<bits/stdc++.h>
#include "Encoder.h"
using namespace std;
int n,dfn[250010],tot,pos[250010],siz[250010],S[250010];
vector<int>e[250010];
inline bool cmp(int x,int y){return S[x]<S[y];}
inline void dfss(int rt,int da)
{
	S[rt]=1;
	for(int i:e[rt])
	{
		if(i==da)continue;
		dfss(i,rt);S[rt]+=S[i];
	}
	sort(e[rt].begin(),e[rt].end(),cmp);
	return ;
}
inline void dfs(int rt,int da)
{
    dfn[rt]=pos[rt]=++tot;
    for(int i:e[rt])
    {
        if(i==da)continue;
        dfs(i,rt);
        pos[rt]=max(pos[rt],pos[i]);
    }
    int s=1,lim=pos[rt]-dfn[rt]+1;
    while(s<lim)s<<=1;tot=max(dfn[rt]+s-1,tot);
    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]);
    }
    dfss(0,0);dfs(0,0);
    for(int i=0;i<n;++i)
	Code(i,dfn[i]|((31-__builtin_clz(siz[i]))<<20));
    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<<20)-1,dfns,dfnt,sizs,sizt;
    dfns=S&Mx,dfnt=T&Mx;
    sizs=1<<(S>>20);sizt=1<<(T>>20);
    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: 9532kb

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:

4194305 6 2097156 11 1048586 1048578 2097160 3 5 9

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
4194305

result:

ok

Test #2:

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

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:

4194305 3 9 7 5 1048580 2097160 3145734 1048578 10

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
4194305

result:

ok

Test #3:

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

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:

4194305 9 8 3145734 10 5 2097159 3145732 3 1048578

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
4194305

result:

ok

Test #4:

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

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:

4194305 4 9 2097154 7 1048584 11 3145734 3 1048586

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
4194305

result:

ok

Test #5:

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

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:

4194305 3 10 4 11 2097161 8 3145734 1048583 2097154

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
4194305

result:

ok

Test #6:

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

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:

4194305 7 5 2097158 3145732 3 1048584 1048578 9

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
4194305

result:

points 1.0

Test #7:

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

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:

4194305 2097161 7 4 2097157 2 10 6 11 1048579

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
4194305

result:

ok

Test #8:

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

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:

3145729 3 1048580 5 1048578

input:

Interaction has been finished!

output:

1
0
0
0
2
1
2
2
1
2
3145729

result:

points 1.0

Test #9:

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

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:

3145729 4 2097157 7 1048579 1048582 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
3145729

result:

points 1.0

Test #10:

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

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:

3145729 7 2097158 2 8 5 3 3145732

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
3145732

result:

points 1.0

Test #11:

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

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:

3145729 2097155 6 2 1048581 4

input:

Interaction has been finished!

output:

0
1
0
1
1
1
0
2
0
2
2
2
2
0
2
3145729

result:

points 1.0

Test #12:

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

input:

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

output:

2097153 2 1048579 4

input:

Interaction has been finished!

output:

1
1
1
2
2
0
2097153

result:

points 1.0

Subtask #2:

score: 0
Wrong Answer

Test #13:

score: 92
Accepted
time: 70ms
memory: 10504kb

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:

11534337 1049929 196 322 1048618 2098377 1048639 1397 1122 85 2097318 1348 449 1049169 47 1048775 1272 1048586 11 710 2098265 5243161 398 1223 1091 1058 771 2097730 523 91 1049290 163 2097166 174 1048605 5244127 342 757 1089 573 3147122 434 321 1049841 1048613 2097961 354 361 1266 1049628 2097689 10...

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: 62ms
memory: 10512kb

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:

11534337 694 1049365 869 327 1049010 296 2098036 2098014 1049403 2098424 11534370 388 2097683 695 2098285 1263 1227 954 1048963 4195534 542 768 1048695 1048740 134 2097242 2098253 785 2097252 424 3147025 3145947 4194710 2097458 170 3146276 1000 1049540 1049586 501 1237 4194399 988 1240 6292566 13 10...

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: 62ms
memory: 10504kb

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:

11534337 486 1313 1214 6292211 3145963 1156 1540 1049218 1049339 5243292 3146352 252 1327 1048994 374 455 1542 4194654 4194937 746 1048663 1049634 1365 200 356 1049121 1223 600 1048982 1329 5244243 1049955 2097163 1307 1049833 3145825 1102 556 2097903 5243127 404 1411 4195811 2098197 1049908 1048661...

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: 70ms
memory: 10444kb

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:

12582913 1134 482 3146194 1135 185 2009 1940 2098902 6292998 1308 3146996 3146129 3147313 2097261 7341060 6292617 5244751 3147477 3147632 3145907 341 2097628 6293261 2097423 2097459 5244106 246 1332 1186 1656 1229 5243345 154 2098794 2097266 407 1099 5242918 2097488 2019 3147698 1098 5243910 2097201...

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: 126ms
memory: 12588kb

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:

22020097 3191651 1702159 1303194 993344 336976 75990 989407 1103871 1010617 308640 896025 1925226 989953 358947 348380 3389528 111312 1969331 2098659 1909324 1214439 167705 349920 1820971 1271283 2281206 1022900 792272 1408257 2036649 1400426 87569 1469613 7529976 3017113 5235180 687409 1473498 1069...

input:

Interaction has been finished!

output:

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

result:

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

Server Time: 2024-11-29 18:40:27 | OpenSource Project