oj.uz

Submission #1071331

# Submission time Handle Problem Language Result Execution time Memory
1071331 2024-08-23T06:43:21 Z Faisal_Saqib Beech Tree (IOI23_beechtree) C++17
5 / 100
 98 ms 22940 KB 
#include <bits/stdc++.h>
using namespace std;
const int N1=2e5+100;
int n,m,p[N1],c[N1],cnt[N1];
vector<int> sub[N1],ma[N1];
void dfs(int x)
{
	sub[x].clear();
	for(int&y:ma[x])
	{
		dfs(y);
		for(int&l:sub[y])sub[x].push_back(l);
		sub[x].push_back(y);
	}
}
std::vector<int> beechtree(int N, int M, std::vector<int> P, std::vector<int> C)
{
	n=N,m=M;
	bool subtask=1;
	for(int i=0;i<n;i++)p[i]=P[i],c[i]=C[i],ma[i].clear(),subtask=(subtask&((p[i]==(i-1))));
	// if(subtask)
	// {
		vector<int> b(n);
		map<int,int> cntp;
		for(int i=n-1;i>=0;i--)
		{
			cntp[c[i]]++;
			if(cntp.size()==1)
			{
				b[i]=1;
			}
			else if(cntp.size()==2 and min(cntp[c[i]],n-cntp[c[i]])==1)
			{
				b[i]=1;
			}
			else{
				b[i]=0;
			}
		}
		return b;
	// }
	// else
	// {
	// 	for(int i=1;i<n;i++)ma[p[i]].push_back(i);
	// 	dfs(0);
	// 	vector<int> b(n);
	// 	for(int i=0;i<n;i++)
	// 	{
	// 		int sz=sub[i].size();
	// 		map<int,int> cntp;
	// 		for(int j=0;j<sz;j++)
	// 		{
	// 			int v=sub[i][j];
	// 			cntp[c[v]]++;
	// 		}
	// 		cntp[c[i]]++;
	// 		if(cntp.size()==1)
	// 		{
	// 			b[i]=1;
	// 		}
	// 		else if(cntp.size()==2 and min(cntp[c[i]],n-cntp[c[i]])==1)
	// 		{
	// 			b[i]=1;
	// 		}
	// 		else{
	// 			b[i]=0;
	// 		}
	// 	}
	// 	return b;
	// }
}

Subtask #0
0.0 / 0.0

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

Subtask #1
0.0 / 9.0

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

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10844 KB Output is correct
2 Correct 1 ms 10844 KB Output is correct
3 Correct 2 ms 10844 KB Output is correct
4 Correct 2 ms 10844 KB Output is correct
5 Correct 2 ms 10844 KB Output is correct
6 Correct 2 ms 10844 KB Output is correct
7 Correct 93 ms 22940 KB Output is correct
8 Correct 72 ms 20564 KB Output is correct
9 Correct 2 ms 10844 KB Output is correct
10 Correct 1 ms 10844 KB Output is correct
11 Correct 2 ms 10684 KB Output is correct
12 Correct 2 ms 10844 KB Output is correct
13 Correct 2 ms 10844 KB Output is correct
14 Correct 2 ms 10840 KB Output is correct
15 Correct 2 ms 10844 KB Output is correct
16 Correct 2 ms 10844 KB Output is correct
17 Correct 38 ms 16032 KB Output is correct
18 Correct 40 ms 15964 KB Output is correct
19 Correct 73 ms 20368 KB Output is correct
20 Correct 98 ms 21840 KB Output is correct

Subtask #3
0.0 / 9.0

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

Subtask #4
0.0 / 8.0

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

Subtask #5
0.0 / 14.0

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

Subtask #6
0.0 / 14.0

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

Subtask #7
0.0 / 12.0

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

Subtask #8
0.0 / 17.0

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

Subtask #9
0.0 / 12.0

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