QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#163979	#7121. Beech Tree	QAQAutoMaton^#	9	588ms	7512kb	C++14	718b	2023-09-04 17:37:55	2023-09-04 17:37:55

Judging History

你现在查看的是测评时间为 2023-09-04 17:37:55 的历史记录

[2024-04-28 07:23:38]
管理员手动重测本题所有提交记录

测评结果：9
用时：807ms
内存：7196kb

查看

[2023-09-04 17:37:55]
评测

测评结果：9
用时：588ms
内存：7512kb

查看

[2023-09-04 17:37:55]
提交

answer

#include "beechtree.h"
#include<bits/stdc++.h>
using namespace std;
vector<int> to[100005];
int fc[100005];
int fa[100005];
int p[100005],c;
bool check(int x){
	p[c=0]=x;
	for(int i=0;i<=c;++i)for(auto j:to[p[i]])p[++c]=j;
	sort(p+1,p+c+1);
	do{
		bool ok=1;
		for(int i=1;i<=c;++i){
			int f=0;
			for(int j=1;j<i;++j)if(fc[p[j]]==fc[p[i]])++f;
			if(p[f]!=fa[p[i]])ok=0;
		}
		if(ok)return 1;
	}while(next_permutation(p+1,p+c+1));
	return 0;
}
std::vector<int> beechtree(int n, int m, std::vector<int> P, std::vector<int> C)
{
	for(int i=1;i<n;++i){
		fa[i]=P[i];
		to[P[i]].emplace_back(i);
		fc[i]=C[i];
	}
	vector<int> ans(n);
	for(int i=0;i<n;++i)ans[i]=check(i);
	return ans;
}

Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 9

Accepted

Test #1:

score: 9

Accepted

time: 0ms

memory: 6112kb

input:

j2DRV0nYbs0y1xUYUGaiqtOKUU9vM9zi
8 500
-1 0 1 2 3 4 5 6
0 281 281 281 281 281 281 281

output:

p89vHUOQJ7iyHtdrgGXzKx8iRtXLL6wH
OK
1 1 1 1 1 1 1 1

result:

ok

Test #2:

score: 0

Accepted

time: 2ms

memory: 6088kb

input:

j2DRV0nYbs0y1xUYUGaiqtOKUU9vM9zi
8 500
-1 0 1 2 3 4 5 6
0 11 169 169 169 169 169 169

output:

p89vHUOQJ7iyHtdrgGXzKx8iRtXLL6wH
OK
0 1 1 1 1 1 1 1

result:

ok

Test #3:

score: 0

Accepted

time: 1ms

memory: 6352kb

input:

j2DRV0nYbs0y1xUYUGaiqtOKUU9vM9zi
8 500
-1 0 1 2 3 4 5 6
0 324 324 492 324 324 324 324

output:

p89vHUOQJ7iyHtdrgGXzKx8iRtXLL6wH
OK
0 0 0 1 1 1 1 1

result:

ok

Test #4:

score: 0

Accepted

time: 2ms

memory: 6896kb

input:

j2DRV0nYbs0y1xUYUGaiqtOKUU9vM9zi
8 500
-1 0 1 2 3 4 5 6
0 216 220 387 371 53 34 188

output:

p89vHUOQJ7iyHtdrgGXzKx8iRtXLL6wH
OK
0 0 0 0 0 0 1 1

result:

ok

Test #5:

score: 0

Accepted

time: 2ms

memory: 6176kb

input:

j2DRV0nYbs0y1xUYUGaiqtOKUU9vM9zi
7 500
-1 0 0 0 1 1 2
0 357 147 147 20 147 20

output:

p89vHUOQJ7iyHtdrgGXzKx8iRtXLL6wH
OK
0 1 1 1 1 1 1

result:

ok

Test #6:

score: 0

Accepted

time: 1ms

memory: 7512kb

input:

j2DRV0nYbs0y1xUYUGaiqtOKUU9vM9zi
4 500
-1 0 0 0
0 267 210 278

output:

p89vHUOQJ7iyHtdrgGXzKx8iRtXLL6wH
OK
1 1 1 1

result:

ok

Test #7:

score: 0

Accepted

time: 0ms

memory: 6152kb

input:

j2DRV0nYbs0y1xUYUGaiqtOKUU9vM9zi
7 500
-1 0 0 0 1 2 3
0 250 140 214 250 250 140

output:

p89vHUOQJ7iyHtdrgGXzKx8iRtXLL6wH
OK
0 1 1 1 1 1 1

result:

ok

Test #8:

score: 0

Accepted

time: 2ms

memory: 6068kb

input:

j2DRV0nYbs0y1xUYUGaiqtOKUU9vM9zi
8 500
-1 0 0 0 1 1 3 3
0 40 205 455 455 36 36 455

output:

p89vHUOQJ7iyHtdrgGXzKx8iRtXLL6wH
OK
0 1 1 1 1 1 1 1

result:

ok

Test #9:

score: 0

Accepted

time: 0ms

memory: 6088kb

input:

j2DRV0nYbs0y1xUYUGaiqtOKUU9vM9zi
7 500
-1 0 0 1 1 1 2
0 181 33 33 181 201 33

output:

p89vHUOQJ7iyHtdrgGXzKx8iRtXLL6wH
OK
0 1 1 1 1 1 1

result:

ok

Test #10:

score: 0

Accepted

time: 1ms

memory: 6560kb

input:

j2DRV0nYbs0y1xUYUGaiqtOKUU9vM9zi
5 500
-1 0 0 1 2
0 162 281 162 162

output:

p89vHUOQJ7iyHtdrgGXzKx8iRtXLL6wH
OK
1 1 1 1 1

result:

ok

Subtask #2:

score: 0

Runtime Error

Test #11:

score: 0

Runtime Error

input:

j2DRV0nYbs0y1xUYUGaiqtOKUU9vM9zi
200000 200000
-1 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86...

output:

result:

Subtask #3:

score: 0

Runtime Error

Test #25:

score: 0

Runtime Error

input:

j2DRV0nYbs0y1xUYUGaiqtOKUU9vM9zi
103965 200000
-1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...

output:

result:

Subtask #4:

score: 0

Runtime Error

Test #48:

score: 0

Runtime Error

input:

j2DRV0nYbs0y1xUYUGaiqtOKUU9vM9zi
199979 200000
-1 0 1 1 1 1 1 1 1 1 1 1 11 11 1 11 11 11 11 11 11 11 0 22 23 23 23 23 23 23 23 23 23 23 33 22 35 36 36 36 36 36 36 36 36 38 38 38 35 48 49 49 49 49 49 49 49 53 53 48 59 60 60 60 60 60 59 66 67 67 67 67 67 67 67 67 67 67 73 71 66 80 81 81 81 81 81 81 81...

output:

result:

Subtask #5:

score: 0

Time Limit Exceeded

Dependency #1:

100%

Accepted

Test #54:

score: 14

Accepted

time: 2ms

memory: 7112kb

input:

j2DRV0nYbs0y1xUYUGaiqtOKUU9vM9zi
200 500
-1 0 0 1 1 2 3 4 5 6 2 7 0 8 9 10 11 12 13 14 1 15 3 16 17 2 18 19 20 4 5 21 22 23 24 25 26 27 28 29 6 30 31 3 32 33 34 35 36 37 7 8 9 38 10 39 11 40 41 12 13 14 4 42 43 44 45 46 5 47 6 48 15 49 50 51 16 52 53 7 54 17 55 56 57 8 9 18 58 59 60 61 19 62 63 64 2...

output:

p89vHUOQJ7iyHtdrgGXzKx8iRtXLL6wH
OK
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

result:

ok

Test #55:

score: -14

Time Limit Exceeded

input:

j2DRV0nYbs0y1xUYUGaiqtOKUU9vM9zi
195 500
-1 0 1 2 3 0 5 5 6 6 7 7 5 8 6 8 9 10 11 9 12 13 14 15 16 10 11 12 17 18 19 20 21 22 13 23 24 14 25 26 15 27 28 1 43 43 44 45 46 47 48 44 49 45 46 50 43 44 47 51 52 53 54 45 55 56 48 49 57 58 59 60 61 62 63 64 46 65 66 50 67 2 81 82 81 81 82 83 84 83 84 85 86...

output:

result:

Subtask #6:

score: 0

Time Limit Exceeded

Test #65:

score: 14

Accepted

time: 588ms

memory: 6732kb

input:

j2DRV0nYbs0y1xUYUGaiqtOKUU9vM9zi
2000 2
-1 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 ...

output:

p89vHUOQJ7iyHtdrgGXzKx8iRtXLL6wH
OK
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

result:

ok

Test #66:

score: -14

Time Limit Exceeded

input:

j2DRV0nYbs0y1xUYUGaiqtOKUU9vM9zi
2000 2
-1 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 ...

output:

result:

Subtask #7:

score: 0

Skipped

Dependency #5:

Subtask #8:

score: 0

Skipped

Dependency #6:

Subtask #9:

score: 0

Skipped

Dependency #1:

100%

Accepted