oj.uz

Submission #1071072

# Submission time Handle Problem Language Result Execution time Memory
1071072 2024-08-23T04:09:13 Z Muhammad_Aneeq Beech Tree (IOI23_beechtree) C++17
9 / 100
 2000 ms 49872 KB 
#include <vector>
#include <algorithm>
#include <set>
#include <iostream>
using namespace std;
int const MAXN=2e5+10;
vector<int>nei[MAXN]={};
int c[MAXN]={};
int h[MAXN]={};
int ans[MAXN]={};
int ind[MAXN]={};
int cnt[MAXN]={};
int p[MAXN]={};
bool check(vector<int>d,int u)
{
	for (auto i:d)
		ind[i]=-1,cnt[c[i]]=0;
	int z=1;
	for (auto i:d)
	{
		if (ind[p[i]]==-1)
			return 0;
		if (cnt[c[i]]!=ind[p[i]])
			return 0;
		ind[i]=z++;
		cnt[c[i]]++;
	}
	return 1;
}
vector<int> dfs(int u)
{
	vector<int>d;
	for (auto i:nei[u])
	{
		h[i]=h[u]+1;
		vector<int>f=dfs(i);
		for (auto i:f)
			d.push_back(i);
	}
	sort(begin(d),end(d));
	while (!check(d,u))
	{
		if (!next_permutation(begin(d),end(d)))
		{
			ans[u]=0;
			break;
		}
	}
	d.push_back(u);
	return d;
}
vector<int> beechtree(int N, int M, vector<int> P, vector<int> C)
{
	for (int i=0;i<N;i++)
		c[i]=C[i],p[i]=P[i],ans[i]=1;
	for (int i=1;i<N;i++)
		nei[P[i]].push_back(i);
	dfs(0);
	vector<int>d;
	for (int i=0;i<N;i++)
		d.push_back(ans[i]);
	return d;
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 9560 KB Output is correct
2 Execution timed out 2025 ms 9564 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9564 KB Output is correct
2 Correct 2 ms 9564 KB Output is correct
3 Correct 1 ms 9656 KB Output is correct
4 Correct 2 ms 9564 KB Output is correct
5 Correct 2 ms 9564 KB Output is correct
6 Correct 2 ms 9564 KB Output is correct
7 Correct 2 ms 9564 KB Output is correct
8 Correct 1 ms 9564 KB Output is correct
9 Correct 1 ms 9564 KB Output is correct
10 Correct 2 ms 9648 KB Output is correct
11 Correct 2 ms 9600 KB Output is correct
12 Correct 2 ms 9560 KB Output is correct
13 Correct 2 ms 9564 KB Output is correct
14 Correct 1 ms 9564 KB Output is correct
15 Correct 2 ms 9564 KB Output is correct
16 Correct 1 ms 9648 KB Output is correct
17 Correct 1 ms 9564 KB Output is correct
18 Correct 2 ms 9564 KB Output is correct
19 Correct 2 ms 9564 KB Output is correct
20 Correct 2 ms 9564 KB Output is correct
21 Correct 2 ms 9564 KB Output is correct
22 Correct 2 ms 9564 KB Output is correct
23 Correct 2 ms 9564 KB Output is correct
24 Correct 2 ms 9564 KB Output is correct
25 Correct 2 ms 9560 KB Output is correct
26 Correct 2 ms 9560 KB Output is correct
27 Correct 1 ms 9564 KB Output is correct
28 Correct 2 ms 9564 KB Output is correct
29 Correct 1 ms 9564 KB Output is correct
30 Correct 1 ms 9564 KB Output is correct
31 Correct 2 ms 9564 KB Output is correct
32 Correct 2 ms 9560 KB Output is correct
33 Correct 2 ms 9564 KB Output is correct
34 Correct 2 ms 9564 KB Output is correct

Subtask #2
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9564 KB Output is correct
2 Correct 2 ms 9564 KB Output is correct
3 Correct 1 ms 9656 KB Output is correct
4 Correct 2 ms 9564 KB Output is correct
5 Correct 2 ms 9564 KB Output is correct
6 Correct 2 ms 9564 KB Output is correct
7 Execution timed out 2079 ms 49872 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2040 ms 9560 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9564 KB Output is correct
2 Correct 2 ms 9564 KB Output is correct
3 Correct 2 ms 9564 KB Output is correct
4 Correct 1 ms 9564 KB Output is correct
5 Execution timed out 2079 ms 49872 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 9560 KB Output is correct
2 Execution timed out 2025 ms 9564 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9564 KB Output is correct
2 Correct 2 ms 9564 KB Output is correct
3 Correct 2 ms 9564 KB Output is correct
4 Correct 1 ms 9564 KB Output is correct
5 Correct 1 ms 9564 KB Output is correct
6 Correct 2 ms 9648 KB Output is correct
7 Correct 2 ms 9600 KB Output is correct
8 Correct 2 ms 9560 KB Output is correct
9 Correct 2 ms 9564 KB Output is correct
10 Correct 1 ms 9564 KB Output is correct
11 Correct 2 ms 9564 KB Output is correct
12 Correct 1 ms 9648 KB Output is correct
13 Correct 1 ms 9564 KB Output is correct
14 Correct 2 ms 9564 KB Output is correct
15 Correct 2 ms 9564 KB Output is correct
16 Correct 2 ms 9564 KB Output is correct
17 Correct 2 ms 9564 KB Output is correct
18 Correct 2 ms 9564 KB Output is correct
19 Correct 2 ms 9564 KB Output is correct
20 Correct 2 ms 9564 KB Output is correct
21 Correct 2 ms 9560 KB Output is correct
22 Correct 2 ms 9560 KB Output is correct
23 Correct 1 ms 9564 KB Output is correct
24 Correct 2 ms 9564 KB Output is correct
25 Correct 66 ms 10072 KB Output is correct
26 Execution timed out 2078 ms 10076 KB Time limit exceeded
27 Halted 0 ms 0 KB -

Subtask #7
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 9560 KB Output is correct
2 Execution timed out 2025 ms 9564 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #8
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9564 KB Output is correct
2 Correct 2 ms 9564 KB Output is correct
3 Correct 2 ms 9564 KB Output is correct
4 Correct 1 ms 9564 KB Output is correct
5 Correct 1 ms 9564 KB Output is correct
6 Correct 2 ms 9648 KB Output is correct
7 Correct 2 ms 9600 KB Output is correct
8 Correct 2 ms 9560 KB Output is correct
9 Correct 2 ms 9564 KB Output is correct
10 Correct 1 ms 9564 KB Output is correct
11 Correct 2 ms 9564 KB Output is correct
12 Correct 1 ms 9648 KB Output is correct
13 Correct 1 ms 9564 KB Output is correct
14 Correct 2 ms 9564 KB Output is correct
15 Correct 2 ms 9564 KB Output is correct
16 Correct 2 ms 9564 KB Output is correct
17 Correct 2 ms 9564 KB Output is correct
18 Correct 2 ms 9564 KB Output is correct
19 Correct 2 ms 9564 KB Output is correct
20 Correct 2 ms 9564 KB Output is correct
21 Correct 2 ms 9560 KB Output is correct
22 Correct 2 ms 9560 KB Output is correct
23 Correct 1 ms 9564 KB Output is correct
24 Correct 2 ms 9564 KB Output is correct
25 Correct 66 ms 10072 KB Output is correct
26 Execution timed out 2078 ms 10076 KB Time limit exceeded
27 Halted 0 ms 0 KB -

Subtask #9
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 9560 KB Output is correct
2 Execution timed out 2025 ms 9564 KB Time limit exceeded
3 Halted 0 ms 0 KB -