QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#302738 | #370. City | NATURAL6 | 8 | 144ms | 16740kb | C++14 | 1.0kb | 2024-01-11 10:40:19 | 2024-01-11 10:40:20 |
Judging History
Encoder
#include<bits/stdc++.h>
#include "Encoder.h"
using namespace std;
int n,dfn[250010],tot,pos[250010],siz[250010];
vector<int>e[250010];
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]);
}
dfs(0,0);
for(int i=0;i<n;++i)
Code(i,dfn[i]|((31-__builtin_clz(siz[i]))<<25));
return ;
}
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;
}
详细
Subtask #1:
score: 8
Accepted
Test #1:
score: 8
Accepted
time: 4ms
memory: 12072kb
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: 11804kb
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: 15232kb
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:
134217729 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 134217732
result:
ok
Test #4:
score: 8
Accepted
time: 6ms
memory: 15468kb
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: 15312kb
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: 4ms
memory: 15068kb
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: 15232kb
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: 0ms
memory: 15216kb
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: 11924kb
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: 6ms
memory: 15016kb
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: 6ms
memory: 12508kb
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: 4ms
memory: 12072kb
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
Stage 1: Program Program Time Limit Exceeded
Test #13:
score: 86.1504
Acceptable Answer
time: 58ms
memory: 12420kb
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:
402653185 33556030 2058 1034 33556768 67110252 33556819 1629 1527 2429 67110990 1603 1204 33554473 2341 33556497 1362 33556749 2318 431 67110382 167773445 1173 1396 1515 1435 239 67108889 9 2406 33554870 2123 67111192 2088 33556745 167773499 1086 291 1554 29 100664922 1227 1033 33555784 33556782 671...
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.93641711870
Test #14:
score: 83.9265
Acceptable Answer
time: 58ms
memory: 15416kb
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:
469762049 1404 33556943 1323 841 33554790 806 67110159 67110180 33555679 67110937 436207618 203 67109071 1437 67110354 2068 2058 2546 33554634 134219693 230 2493 33554509 33555149 147 67108970 67110319 2498 67108979 348 100665312 100664021 134218207 67109679 3332 100663532 2572 33556983 33557021 293...
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.91224402950
Test #15:
score: 84.9956
Acceptable Answer
time: 58ms
memory: 12516kb
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 2799 2710 201326776 100667579 3042 2187 33554509 33554656 167773261 100663358 4264 2732 33555535 1188 1081 2192 134218886 134217799 250 33556512 33557402 2314 4365 1162 33555104 2959 58 33555466 2742 167774470 33556754 67113417 2804 33557155 100665356 3062 136 67109041 167776393 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: 86.1504
Acceptable Answer
time: 58ms
memory: 15068kb
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:
402653185 1134 2530 100665810 1135 2233 473 404 67109078 201326598 1178 100664631 100665745 100663345 67111021 234882052 201327949 167772495 100663509 100663664 100665523 2389 67111388 201326861 67111183 67111219 167773453 2294 1202 1382 120 1296 167774673 2202 67108970 67111026 2455 1099 167774246 ...
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.93641711870
Test #17:
score: 75.5614
Acceptable Answer
time: 122ms
memory: 13704kb
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:
838860801 76888844 48067264 6217480 9609945 2869422 555262 10193725 43312722 9799484 3644795 11243683 44862713 10192069 2828862 2720938 73497915 72473 45099142 89720599 45006619 35249199 1680432 2746800 41871989 5961644 69147344 9844910 8186974 36383747 43755071 7245419 308314 6659023 236936654 7865...
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 1 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:
points 0.8213199790
Test #18:
score: 75.5614
Acceptable Answer
time: 144ms
memory: 15592kb
input:
250000 250000 58662 187031 88005 38197 22682 178770 111851 15764 207630 198631 64191 185171 168598 129456 142337 237430 215849 182270 211116 93208 20 204879 130122 42963 11672 121189 75991 33257 87185 128123 33289 2936 144056 47212 140138 18041 2913 20891 194901 213077 39452 3187 187440 25628 73551 ...
output:
838860801 56065353 16795660 2325882 8766 16888934 153613131 123823993 18100388 16929393 89112818 67779916 56607605 118233111 83999133 285293367 17126820 1025193 104539244 136717383 100842509 23031025 37355168 16780877 3186187 101150576 52927323 83894494 68134016 56116384 67288810 25205761 35877144 2...
input:
Interaction has been finished!
output:
1 0 2 1 2 2 2 0 1 2 1 2 0 0 1 1 0 2 2 2 1 2 1 1 2 1 2 0 2 1 1 2 1 2 2 2 0 0 1 1 2 1 2 2 2 2 2 1 0 1 0 2 2 1 2 0 1 0 2 1 1 2 0 0 1 1 1 2 1 0 1 2 0 2 2 2 0 2 0 0 2 2 1 1 1 0 2 0 0 2 2 1 1 0 1 0 2 0 0 1 2 2 2 2 2 2 0 2 2 1 1 2 0 1 2 2 1 0 2 2 1 0 2 2 2 1 1 2 2 0 1 1 2 2 1 2 1 2 1 2 2 2 2 1 1 0 0 2 0 0 ...
result:
points 0.8213199790
Test #19:
score: 75.5614
Acceptable Answer
time: 132ms
memory: 15480kb
input:
250000 250000 212557 2865 205598 91456 106547 166169 2385 60328 54909 26698 82002 112166 121929 240217 123410 133417 93989 61456 92642 225604 49143 8681 1263 131585 214794 141276 12589 67655 51160 187118 83743 12235 86483 172453 29872 111146 249757 78807 216189 2378 57530 180918 106038 234952 16366 ...
output:
838860801 11375770 138450012 145795301 6346191 86450323 2105838 11158080 72942213 4725015 628129 10856102 52839413 288254549 11567121 104915638 134850535 112042487 19811665 5533898 5047824 6605330 11075716 7680658 6340510 104915685 105210912 39286502 19557235 15253309 15275540 2097778 20365399 78726...
input:
Interaction has been finished!
output:
1 1 2 1 2 2 2 0 0 2 1 1 2 2 2 0 0 2 1 1 0 0 0 2 0 1 1 2 2 2 1 2 0 1 2 1 2 1 1 0 2 2 2 2 2 0 2 1 1 2 2 1 2 0 1 2 1 2 1 1 2 2 2 0 0 2 2 1 2 2 1 2 1 2 2 0 1 2 2 2 0 0 0 2 2 0 0 2 2 2 2 2 2 1 2 0 2 1 2 2 2 1 2 0 2 0 1 1 2 0 1 2 2 0 2 2 2 2 1 0 0 2 1 1 2 2 2 0 0 2 0 1 1 2 2 2 0 0 1 2 0 0 1 1 2 2 2 2 1 1 ...
result:
points 0.8213199790
Test #20:
score: 78.0768
Acceptable Answer
time: 120ms
memory: 16740kb
input:
250000 250000 108989 180679 6618 123314 146792 97095 101695 18624 109138 21259 130176 235020 131970 224224 32023 110376 126943 90247 7024 8229 55250 106561 44259 206501 157785 107293 88446 38793 62937 119441 158397 243678 83221 104131 184687 105512 101778 195126 76695 8559 31678 182822 58730 237755 ...
output:
704643073 744303 68109444 67318085 335585329 68152528 175364 450032 299525 772771 647854 785205 572905 56748 118060 42176 235045004 93395 202014 101073641 309768 904112 378602 959614 90557 705415 67657522 101327456 510700 101099296 841743 680983 168141109 67185952 101351347 68923 324277 67777485 202...
input:
Interaction has been finished!
output:
0 2 2 2 0 1 2 0 2 2 1 0 1 1 2 2 0 0 2 1 2 2 1 2 1 0 2 2 2 2 2 2 2 1 2 2 1 2 0 0 2 2 0 2 2 2 2 0 1 0 1 2 2 2 0 2 0 2 0 2 2 2 2 0 1 2 2 0 2 0 2 2 2 0 2 1 2 2 2 0 0 2 2 2 2 0 1 2 0 1 0 2 1 2 2 2 2 2 0 2 2 2 1 2 2 1 2 0 2 1 0 1 2 2 1 1 2 2 1 2 2 2 2 0 1 1 0 2 2 2 2 1 2 2 1 2 2 2 2 2 1 2 0 2 2 2 1 1 2 1 ...
result:
points 0.84866114930
Test #21:
score: 0
Stage 1: Program Program Time Limit Exceeded
input:
250000 250000 128536 214028 128536 203182 145589 67326 128536 148506 128536 118881 128536 221940 128536 82743 128536 76287 128536 207959 128536 126237 128536 33353 143121 245162 128536 140279 128536 149583 128536 146645 119187 41695 128536 122057 128536 1126 128536 97289 239043 83867 17254 163707 12...