QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#305519#370. Citysio_8 64ms8336kbC++141.2kb2024-01-15 15:15:312024-01-15 15:15:33

Judging History

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

  • [2024-01-15 15:15:33]
  • 评测
  • 测评结果：8
  • 用时：64ms
  • 内存：8336kb
查看
  • [2024-01-15 15:15:31]
  • 提交

Encoder

#include<bits/stdc++.h>
#include "Encoder.h"
using namespace std;
const int maxn=3e4+5;
vector<int> nbr[maxn];
int dfn[maxn],cnt,siz[maxn],power[maxn];
void getpowe()
{
	power[1]=1;
	for(int i=2;i<=512;i++) power[i]=max(power[i-1]+1,(int)(power[i-1]*1.023));
}
void dfs(int cur,int fa)
{
	dfn[cur]=++cnt,siz[cur]=1;
	for(int i=0;i<nbr[cur].size();i++)
		if(nbr[cur][i]!=fa) dfs(nbr[cur][i],cur),siz[cur]+=siz[nbr[cur][i]];
	int pos=lower_bound(power+1,power+512+1,siz[cur])-power;
	Code(cur,1ll*(dfn[cur]-1)*512+pos-1);
	// cout<<cur<<" "<<pos<<endl;
}
void Encode(int n,int A[],int B[])
{
	for(int i=0;i<n;i++)
		nbr[A[i]].push_back(B[i]),nbr[B[i]].push_back(A[i]);
	getpowe();
	dfs(0,0);
}
Source code, Language: C++14

Device

#include<bits/stdc++.h>
#include "Device.h"
using namespace std;
const int maxn=3e5+5;
int powe[maxn];
void getpower()
{
	powe[1]=1;
	for(int i=2;i<=512;i++) powe[i]=max(powe[i-1]+1,(int)(powe[i-1]*1.025));
}
void InitDevice(){getpower();}

int Answer(long long S, long long T)
{
	int dfns=S/512+1,dfnt=T/512+1;
	int sizs=powe[S%512+1],sizt=powe[T%512+1];
	// cout<<dfns<<" "<<dfnt<<" "<<sizs<<" "<<sizt<<endl;
	if(dfns<=dfnt&&dfnt+sizt<=dfns+sizs) return 1;
	if(dfnt<=dfns&&dfns+sizs<=dfnt+sizt) 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: 7892kb

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:

9 2560 1538 4096 3585 513 3075 1024 2048 4608

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
4608

result:

ok

Test #2:

score: 8
Accepted
time: 2ms
memory: 6432kb

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:

9 3584 1536 2560 4608 4097 1026 516 3073 2048

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
4608

result:

ok

Test #3:

score: 8
Accepted
time: 2ms
memory: 7892kb

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:

9 3584 3072 2052 4096 4608 2563 1542 1024 513

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
4608

result:

ok

Test #4:

score: 8
Accepted
time: 2ms
memory: 7848kb

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:

9 1536 3584 514 2560 3073 4608 2053 1024 4097

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
4608

result:

ok

Test #5:

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

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:

9 4096 2560 4608 3072 2050 1536 517 1025 3586

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
4608

result:

ok

Test #6:

score: 8
Accepted
time: 2ms
memory: 6488kb

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:

8 3584 4096 2051 1541 1024 2561 513 3072

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
4096

result:

points 1.0

Test #7:

score: 8
Accepted
time: 2ms
memory: 6424kb

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:

9 2562 2048 4608 1026 512 3072 1536 3584 4097

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
4608

result:

ok

Test #8:

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

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:

4 1024 1537 2048 513

input:

Interaction has been finished!

output:

1
0
0
0
2
1
2
2
1
2
2048

result:

points 1.0

Test #9:

score: 8
Accepted
time: 2ms
memory: 7780kb

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:

6 1536 2050 3072 1025 2561 512

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
3072

result:

points 1.0

Test #10:

score: 8
Accepted
time: 2ms
memory: 8336kb

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:

7 2048 1538 512 2560 3072 3584 1028

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
3584

result:

points 1.0

Test #11:

score: 8
Accepted
time: 2ms
memory: 6512kb

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:

5 1027 2048 512 1537 2560

input:

Interaction has been finished!

output:

0
1
0
1
1
1
0
2
0
2
2
2
2
0
2
2560

result:

points 1.0

Test #12:

score: 8
Accepted
time: 2ms
memory: 6428kb

input:

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

output:

3 1536 513 1024

input:

Interaction has been finished!

output:

1
1
1
2
2
0
1536

result:

points 1.0

Subtask #2:

score: 0
Wrong Answer

Test #13:

score: 0
Wrong Answer
time: 64ms
memory: 6428kb

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:

188 242177 287232 98304 329217 183810 342017 253440 225280 354304 301570 243712 138240 15873 331264 290305 175616 321537 322048 82432 221187 147478 125440 185856 219648 199680 65024 11266 4096 350208 85505 300032 325634 295936 319489 164889 115712 68096 231936 12800 251910 142848 97792 171009 332289...

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:

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

Server Time: 2024-11-29 16:23:54 | OpenSource Project