QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#823381	#9905. 哈夫曼树	guleng2007^#	0	182ms	6004kb	C++20	1008b	2024-12-20 22:56:25	2024-12-20 22:56:25

Judging History

你现在查看的是最新测评结果

[2024-12-20 22:56:25]
评测

测评结果：0
用时：182ms
内存：6004kb

查看

[2024-12-20 22:56:25]
提交

answer

#include <bits/stdc++.h>
using namespace std;

const int N=1e5+5;

int son[N*2][2], n;
long long a[N*2];

unsigned long long H(long long val)
{
	return (unsigned long long)val*val*val*val*val+(unsigned long long)val*val*val+(unsigned long long)val;
}

void work()
{
	unsigned long long sum=0;
	for(int i=n+1;i<=n*2-1;i++)
	{
		a[i]=a[son[i][0]]+a[son[i][1]];
		sum += H(a[i]);
	}

	priority_queue <int,vector<int>,greater<int> > q;
	for(int i=1;i<=n;i++)
		q.push(a[i]);

	for(int i=n+1;i<=n*2-1;i++)
	{
		int val=0;
		val += q.top();
		q.pop();
		val += q.top();
		q.pop();
		q.push(val);
		sum -= H(val);
	}

	if(sum==0)
		printf("YES\n");
	else
		printf("NO\n");
}

int main()
{
	int q;
	cin >> n >> q;
	for(int i=1;i<=n;i++)
		scanf("%lld",&a[i]);

	for(int i=n+1;i<=n*2-1;i++)
		scanf("%d %d",&son[i][0],&son[i][1]);

	work();
	for(int i=1;i<=q-1;i++)
	{
		int x;
		long long y;
		scanf("%d %lld",&x,&y);
		a[x]=y;
		work();
	}
	return 0;
}

Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0

Wrong Answer

Test #1:

score: 30

Accepted

time: 1ms

memory: 5992kb

input:

output:

YES
NO
YES
NO

result:

ok 4 token(s): yes count is 2, no count is 2

Test #2:

score: 30

Accepted

time: 0ms

memory: 3704kb

input:

8 5
5 3 4 2 2 6 5 5
1 8
4 5
10 3
11 9
7 2
6 13
14 12
7 3
6 8
4 2
2 5

output:

NO
YES
YES
YES
NO

result:

ok 5 token(s): yes count is 3, no count is 2

Test #3:

score: 0

Wrong Answer

time: 1ms

memory: 6004kb

input:

5 1000
193989534544158 57483670601746 183281373434588 92196008024549 197513473286508
1 5
4 2
7 3
8 6
2 65545142774024
4 67957472319495
5 131478473459166
2 102185858570152
3 191441353035940
5 186000528093501
2 63201184033501
2 77481806092413
3 159789430863849
4 92773786021894
1 194598667478593
3 1458...

output:

NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
...

result:

wrong answer expected YES, found NO [1st token]

Subtask #2:

score: 0

Time Limit Exceeded

Test #16:

score: 0

Time Limit Exceeded

input:

10000 10000
85117964119 41472951000 61693640396 66409648221 91978532661 62922448518 92497200794 43837348258 45577855926 38256001396 79446271832 95289903258 62510175551 97599809584 56162244722 87617641117 64010325734 56604859803 58544571483 40687963085 38627694508 64665875035 62273927372 73014847094 ...

output:

NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
...

result:

Subtask #3:

score: 0

Time Limit Exceeded

Test #20:

score: 0

Time Limit Exceeded

input:

50000 50000
16394396247 17456058492 11358090355 13208121167 8612535629 2853817504 18100755237 18603321637 1618810635 7615832530 13631222424 7817630977 10963098997 19654927084 645638016 9352759139 17939720223 15106346489 14475376391 2122412099 15482023637 11224675857 15931143509 4240408932 1270948838...

output:

result:

Subtask #4:

score: 0

Wrong Answer

Test #24:

score: 0

Wrong Answer

time: 182ms

memory: 4004kb

input:

70 100000
66748 126 1 91045172 3605661959574 274077743637349 147314183 8209537 740253 6920630855 25494 1377240316614 15756 6 108000 18118446805 169389361127761 29316262755 48 2643445763 5834083602536 3 9439745562111 29 3719 10 47434709561 11197815949 6018 325122336074 851181326345 1633739329 1527382...

output:

NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
...

result:

wrong answer expected YES, found NO [1st token]