oj.uz

Submission #1071077

# Submission time Handle Problem Language Result Execution time Memory
1071077 2024-08-23T04:14:06 Z Muhammad_Aneeq Beech Tree (IOI23_beechtree) C++17
0 / 100
 2000 ms 9564 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;
	bool w=1;
	for (int i=1;i<N;i++)
	{
		nei[P[i]].push_back(i);
		if (P[i]!=i-1)
			w=0;
	}
	if (w)
	{
		vector<int>ans(N,0);
		for (int i=N-1;i>=0;i--)
		{
			if (c[i]==c[N-1])
				ans[i]=1;
			else
				break;
		}
		return ans;
	}
	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 2 ms 9564 KB Output is correct
2 Execution timed out 2088 ms 9564 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #1
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 7512 KB 2nd lines differ - on the 1st token, expected: '1', found: '0'
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 7512 KB 2nd lines differ - on the 1st token, expected: '1', found: '0'
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 9.0

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

Subtask #4
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 7512 KB 2nd lines differ - on the 1st token, expected: '1', found: '0'
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9564 KB Output is correct
2 Execution timed out 2088 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 Incorrect 1 ms 7512 KB 2nd lines differ - on the 1st token, expected: '1', found: '0'
2 Halted 0 ms 0 KB -

Subtask #7
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9564 KB Output is correct
2 Execution timed out 2088 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 Incorrect 1 ms 7512 KB 2nd lines differ - on the 1st token, expected: '1', found: '0'
2 Halted 0 ms 0 KB -

Subtask #9
0.0 / 12.0

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