QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#274340#7736. Red Black Treeluyiming123AC ✓302ms43600kbC++143.2kb2023-12-03 14:30:262023-12-03 14:30:27

Judging History

你现在查看的是测评时间为 2023-12-03 14:30:27 的历史记录

  • [2024-02-19 10:15:37]
  • 自动重测本题所有获得100分的提交记录
  • 测评结果:AC
  • 用时:442ms
  • 内存:42404kb
  • [2024-02-19 10:14:05]
  • hack成功,自动添加数据
  • (/hack/538)
  • [2023-12-03 14:30:27]
  • 评测
  • 测评结果:100
  • 用时:302ms
  • 内存:43600kb
  • [2023-12-03 14:30:26]
  • 提交

answer

# include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
bool col[N]; char str[N]; 
int n; 
vector <int> g[N]; 
struct node
{
	vector <int> fu, zh; 
	int dp0, siz0, fusum; 
	int size(void) {return (int)fu.size() + (int)zh.size() + siz0; }
	void clear(void)
	{
		dp0 = siz0 = fusum = 0; fu.clear(), zh.clear(); 
		fu.shrink_to_fit(), zh.shrink_to_fit(); 
		return; 
	}
}dp[N]; int Ans[N]; 
// node merge(node &L, node &R, int h)
// {
// 	vector <int> tmp(N + 5); 
// 	int pos = -1;
// 	for(int x : L.fu) 
// 	{
// 		if(pos < h) tmp[++pos] = x; 
// 		else break; 
// 	}
// 	if(pos < h)
// 	{
// 		pos += L.siz0; 
// 		for(int i = (int)L.zh.size() - 1; i >= 0; i--)
// 		{
// 			if(pos < h) tmp[++pos] = L.zh[i]; 
// 			else break; 
// 		}
// 	}
// 	pos = -1;
// 	for(int x : R.fu)
// 	{
// 		if(pos < h) tmp[++pos] += x; 
// 		else break; 
// 	}
// 	if(pos < h)
// 	{
// 		pos += R.siz0; 
// 		for(int i = (int)R.zh.size() - 1; i >= 0; i--)
// 		{
// 			if(pos < h) tmp[++pos] += R.zh[i]; 
// 			else break; 
// 		}
// 	}
// 	node ans; ans.dp0 = L.dp0 + R.dp0, ans.siz0 = ans.fusum = 0; 
// 	for(int x : tmp)
// 	{
// 		if(x < 0) ans.fu.push_back(x), ans.fusum += x; 
// 		else if(x > 0) ans.zh.push_back(x); 
// 		else ans.siz0++;
// 	}
// 	reverse(ans.zh.begin(), ans.zh.end());
// 	return ans;
// }
node merge(node &L, node &R, int h)
{
	node ans; ans.clear(); ans.dp0 = L.dp0 + R.dp0; 
	// h = min((int)L.size(), (int)R.size()); 
	vector <int> tmp(h); int pos = 0;
	for(int x : L.fu)
	{
		if(pos >= h) break; tmp[pos++] = x; 
	}
	pos += L.siz0; 
	reverse(L.zh.begin(), L.zh.end()); 
	for(int x : L.zh)
	{
		if(pos >= h) break; tmp[pos++] = x; 
	}
	pos = 0;
	for(int x : R.fu)
	{
		if(pos >= h) break; tmp[pos++] += x; 
	}
	pos += R.siz0; 
	reverse(R.zh.begin(), R.zh.end());
	for(int x : R.zh) 
	{
		if(pos >= h) break; tmp[pos++] += x; 	
	}
	for(int x : tmp)
	{
		if(x < 0) ans.fu.push_back(x), ans.fusum += x; 
		else if(x > 0) ans.zh.push_back(x); 
		else ans.siz0++; 
	}
	reverse(ans.zh.begin(), ans.zh.end()); 
	return ans;
}
int dfs(int x)
{
	dp[x].clear(); 
	int h = (g[x].size() == 0) ? 0 : 1e9; 
	for(int v : g[x]) h = min(h, dfs(v)); 
	// ++h; 
	// printf("x = %d, h = %d\n", x, h); 
	if((int)g[x].size())
	{
		swap(dp[x], dp[g[x][0]]);
		for(int i = 1; i < (int)g[x].size(); i++)
		{
			int v = g[x][i]; 
			dp[x] = merge(dp[x], dp[v], h); 
		}	
	}
	++h;
	if(col[x]) 
	{
		dp[x].dp0++; dp[x].fu.push_back(-1), dp[x].fusum--;
	}
	else dp[x].zh.push_back(1); 
	Ans[x] = dp[x].dp0 + dp[x].fusum; 
	// printf("x = %d, dp0 = %d\n", x, dp[x].dp0); 
	// printf("fu : \n"); 
	// for(int x : dp[x].fu) printf("%d ", x); printf("\n"); 
	// printf("0 : %d\n", dp[x].siz0); 
	// for(int x : dp[x].zh) printf("%d ", x); printf("\n");
	return h;
}
int main(void)
{
	int Test; scanf("%d", &Test);
	while(Test--)
	{
		scanf("%d", &n);
		for(int i = 0; i <= n; i++) g[i].clear(), dp[i].clear(); 
		scanf("%s", str + 1); 
		for(int i = 1; i <= n; i++) col[i] = str[i] - '0'; 
		for(int i = 2; i <= n; i++)
		{
			int f; scanf("%d", &f); g[f].push_back(i); 
		}
		dfs(1);
		for(int i = 1; i <= n; i++) printf("%d%c", Ans[i], " \n"[i == n]);
	}
	 

	return 0; 
}

这程序好像有点Bug,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 3ms
memory: 12332kb

input:

2
9
101011110
1 1 3 3 3 6 2 2
4
1011
1 1 3

output:

4 1 2 0 0 0 0 0 0
2 0 0 0

result:

ok 2 lines

Test #2:

score: 0
Accepted
time: 199ms
memory: 43600kb

input:

6107
12
000000001000
1 2 3 2 5 4 4 7 3 8 11
19
1100111101111011110
1 2 1 1 4 5 2 4 3 2 2 7 10 2 11 3 15 5
7
0111110
1 1 2 2 1 5
3
000
1 1
7
1000011
1 2 3 3 5 4
7
0001001
1 1 1 3 5 3
8
00111000
1 1 3 2 5 2 7
11
11111110111
1 1 1 4 5 4 5 2 5 1
15
110101101000010
1 2 3 2 1 5 2 5 6 5 8 7 9 14
10
0101000...

output:

1 1 1 1 0 0 0 0 0 0 0 0
6 2 0 1 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0
0 0 0
0 0 0 0 0 0 0
2 0 1 0 0 0 0
2 1 0 0 0 0 0 0
4 0 0 2 1 0 0 0 0 0 0
4 3 0 0 2 0 0 0 0 0 0 0 0 0 0
2 0 1 0 0 0 0 0 0 0
6 5 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0
1 1 0 0 0
5 1 0 1 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0
5 3 ...

result:

ok 6107 lines

Test #3:

score: 0
Accepted
time: 302ms
memory: 17864kb

input:

10
100000
10001010000001100001000100001000010100010101100001001110110001000010000110001000000010000011000001000001010001110100000000000000000010011011100000000000001000000000100100100110000000100001010011000000110000000111010100100001100000100100101001000000010000000011100000000000000010001100011100...

output:

22440 21414 19422 13454 5328 2719 1421 1168 1478 661 4662 5037 418 183 2304 501 2008 1643 692 2211 570 1003 967 950 504 124 894 333 775 523 905 197 12 337 195 310 1325 1016 638 50 907 361 179 336 313 102 309 555 733 871 490 414 375 318 66 625 336 267 276 162 203 25 112 216 252 146 42 233 232 333 27 ...

result:

ok 10 lines

Test #4:

score: 0
Accepted
time: 155ms
memory: 16096kb

input:

10
100000
01010111111101011100011111111010011001111111110001100111111101011111110011101111110110111011010111011011010011111110101111111011111111011101011111011001110101111011011010110100011111001101001011111101111101111111111100101101000111111110111101111111111011111100111011101110110101111010101101...

output:

25019 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 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...

result:

ok 10 lines

Test #5:

score: 0
Accepted
time: 151ms
memory: 41840kb

input:

10
100000
00111110110011111111111010011111011111101010110111111110011110111111111111000110101110110111111101011111111111010101111111011001110110011101111001110111101101110110101000011111110100101110110100111110001111011100111101011010111111011011100011111011110111111110011110111111001111111010011100...

output:

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 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 ...

result:

ok 10 lines

Test #6:

score: 0
Accepted
time: 199ms
memory: 36748kb

input:

10
100000
00111100100100001111011000100000000000111001100000000000100000101001001010010000001000010010111000001011010000000000001000000000010100000010010010000001000010001000000100000001010000000000000000000001000110000010100100000010000011000000000010010000100010100000000100000100100011000000001000...

output:

4415 4415 4415 4415 4415 4415 4415 4415 4415 4415 4415 4415 4415 4415 4415 4415 4415 4415 4415 4415 4415 4415 4415 4415 4415 4415 4415 4415 4415 4415 4415 4415 4415 4415 4415 4415 4415 4415 4415 4415 4415 4415 4415 4415 4415 4415 4415 4415 4415 4415 4415 4415 4415 4415 4415 4415 4415 4415 4415 4415 ...

result:

ok 10 lines

Test #7:

score: 0
Accepted
time: 169ms
memory: 29316kb

input:

10
100000
00111101111001101110101101111110100001010100011011100001011100000110000100100010111010011001111011100010010011111100000011111011001001000110000101101001011110000000011100001010100001000110110101111010000100000111001110001100001001001000101110100111111000101101100000011001110111001111101011...

output:

210 210 210 210 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 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...

result:

ok 10 lines

Test #8:

score: 0
Accepted
time: 183ms
memory: 26924kb

input:

10
100000
00010011111100101111110000110010101110000000001111011110011010011011101011010000111100001001111111111001000110100010001111010111101100101111101100001001100110000011010100110110010101000010111001001010110111011000010100110101110001100110101010101001100010100000100000100101011110000100001001...

output:

6360 6360 4803 4803 1549 1549 1555 1555 1555 1595 1555 1549 1549 1555 1555 1600 1555 1549 1549 1549 1555 1555 1555 1555 1595 1549 1555 1555 1555 1555 1595 1595 1600 1555 1600 1600 1595 1549 1555 1555 1549 1600 1595 1600 1555 1595 1595 1549 1549 1549 1549 1555 1549 1549 1600 1595 1555 1549 1549 1555 ...

result:

ok 10 lines

Test #9:

score: 0
Accepted
time: 194ms
memory: 16584kb

input:

10
100000
11000111101111111101001011010110110111010011000111011111011111110111110000110101111111011101111011111111101110011100011101111111001011111101011111110010011111101111111011101101100110101010011111110111111101100101010011111111111100101111111101111100011100111110111111011111011001111110011101...

output:

18217 12003 6214 6012 5991 3232 2982 3008 3004 2973 3017 1780 1451 1499 1483 1513 1495 1486 1516 1499 1474 1509 1508 1037 743 738 713 722 776 752 731 741 771 759 735 731 755 740 776 733 765 736 738 753 756 739 769 678 359 362 380 364 374 342 370 356 364 393 382 367 385 360 371 370 371 383 387 387 37...

result:

ok 10 lines

Test #10:

score: 0
Accepted
time: 175ms
memory: 29380kb

input:

10
100000
10111111011011110010111111111111110111101110110001011111101110111011111111111101101011111101101001100111011011011101001110110110101010010001010111111111111111111011011011101011011101100001111101111110111110010011011111111011101110111111111110010011110011111011011011111111101111001110111111...

output:

50037 0 50035 0 50034 0 50033 0 50033 0 50032 0 50030 0 50029 0 50029 0 50027 0 50025 0 50024 0 50023 0 50022 0 50021 0 50020 0 50019 0 50019 0 50018 0 50017 0 50015 0 50014 0 50012 0 50012 0 50011 0 50011 0 50010 0 50009 0 50008 0 50006 0 50005 0 50003 0 50002 0 50000 0 49999 0 49998 0 49997 0 4999...

result:

ok 10 lines

Extra Test:

score: 0
Extra Test Passed