oj.uz

Submission #1071050

# Submission time Handle Problem Language Result Execution time Memory
1071050 2024-08-23T03:47:55 Z Muhammad_Aneeq Beech Tree (IOI23_beechtree) C++17
0 / 100
 2 ms 9660 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]={};
vector<int> dfs(int u)
{
	set<pair<int,int>>d;
	for (auto i:nei[u])
	{
		h[i]=h[u]+1;
		vector<int>f=dfs(i);
		for (auto i:f)
		{
			ind[i]=-1;
			cnt[c[i]]=0;
			d.insert({h[i],i});
		}
	}
	int z=1;
	ind[u]=0;
	while (d.size())
	{
		int x=-1;
		for (auto i:d)
		{
			int v=i.second;
			if (ind[p[v]]!=-1&&cnt[c[v]]==ind[p[v]])
			{
				x=v;
				break;
			}
		}	
		if (x==-1)
			break;
		d.erase({h[x],x});
		cnt[c[x]]++;
		ind[x]=z++;
	}
	ans[u]=(d.size()==0);
	vector<int>qw;
	qw.push_back(u);
	for (auto i:d)
		qw.push_back(i.second);
	return qw;
}
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];
	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 2 ms 9560 KB Output is correct
2 Correct 2 ms 9564 KB Output is correct
3 Correct 1 ms 9564 KB Output is correct

Subtask #1
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9564 KB Output is correct
2 Incorrect 1 ms 9660 KB 2nd lines differ - on the 1st token, expected: '0', found: '1'
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9564 KB Output is correct
2 Incorrect 1 ms 9660 KB 2nd lines differ - on the 1st token, expected: '0', found: '1'
3 Halted 0 ms 0 KB -

Subtask #3
0.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 9564 KB Output is correct
4 Correct 1 ms 9564 KB Output is correct
5 Correct 2 ms 9564 KB Output is correct
6 Correct 1 ms 9564 KB Output is correct
7 Correct 2 ms 9652 KB Output is correct
8 Correct 2 ms 9652 KB Output is correct
9 Incorrect 2 ms 9560 KB 2nd lines differ - on the 1st token, expected: '1', found: '0'
10 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 Incorrect 1 ms 9660 KB 2nd lines differ - on the 1st token, expected: '0', found: '1'
3 Halted 0 ms 0 KB -

Subtask #5
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9560 KB Output is correct
2 Correct 2 ms 9564 KB Output is correct
3 Correct 1 ms 9564 KB Output is correct
4 Correct 2 ms 9564 KB Output is correct
5 Incorrect 1 ms 9660 KB 2nd lines differ - on the 1st token, expected: '0', found: '1'
6 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 Incorrect 1 ms 9660 KB 2nd lines differ - on the 1st token, expected: '0', found: '1'
3 Halted 0 ms 0 KB -

Subtask #7
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9560 KB Output is correct
2 Correct 2 ms 9564 KB Output is correct
3 Correct 1 ms 9564 KB Output is correct
4 Correct 2 ms 9564 KB Output is correct
5 Incorrect 1 ms 9660 KB 2nd lines differ - on the 1st token, expected: '0', found: '1'
6 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 Incorrect 1 ms 9660 KB 2nd lines differ - on the 1st token, expected: '0', found: '1'
3 Halted 0 ms 0 KB -

Subtask #9
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9560 KB Output is correct
2 Correct 2 ms 9564 KB Output is correct
3 Correct 1 ms 9564 KB Output is correct
4 Correct 2 ms 9564 KB Output is correct
5 Incorrect 1 ms 9660 KB 2nd lines differ - on the 1st token, expected: '0', found: '1'
6 Halted 0 ms 0 KB -