QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#821149	#9905. 哈夫曼树	as_lyr	0	2264ms	122628kb	C++14	2.6kb	2024-12-19 13:51:29	2024-12-19 13:51:30

Judging History

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

[2024-12-19 13:51:30]
评测

测评结果：0
用时：2264ms
内存：122628kb

查看

[2024-12-19 13:51:29]
提交

answer

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast","inline","-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
using namespace std;
typedef long long ll;
const int N=210000;
int n,q;
ll a[N],b[N];
int fa[N];
int son[N][2];
int dep[N],mxdep;
void dfs(int x){
	if(son[x][0]){
		int y=son[x][0];
		mxdep=max(mxdep,dep[y]=dep[x]+1);
		dfs(y);
	}
	if(son[x][1]){
		int y=son[x][1];
		mxdep=max(mxdep,dep[y]=dep[x]+1);
		dfs(y);
	}
}
int cnt;
map <pair<ll,ll>,int> mp;
set <pair<ll,ll>> st;
inline bool calc(pair <ll,ll> x,pair <ll,ll> y){
	if(x.first<y.first&&y.second<x.second)
		return 1;
	if(y.first<x.first&&x.second<y.second)
		return 1;
	return min(x.second,y.second)-max(x.first,y.first)>=1;
}
inline void ins(pair <ll,ll> x){
	st.insert(x);
	if(st.size()==1)
		;
	else if(x==*st.begin())
		cnt+=calc(x,*++st.find(x));
	else if(x==*st.rbegin())
		cnt+=calc(x,*--st.find(x));
	else{
		pair <ll,ll> l=*--st.find(x),r=*++st.find(x);
		cnt-=calc(l,r);
		cnt+=calc(x,l);
		cnt+=calc(x,r);
	}
}
inline void era(pair <ll,ll> x){
	if(st.size()==1)
		;
	else if(x==*st.begin())
		cnt-=calc(x,*++st.find(x));
	else if(x==*st.rbegin())
		cnt-=calc(x,*--st.find(x));
	else{
		pair <ll,ll> l=*--st.find(x),r=*++st.find(x);
		cnt+=calc(l,r);
		cnt-=calc(x,l);
		cnt-=calc(x,r);
	}
	st.erase(x);
}
ll all;
void build(int x){
	if(son[x][0]==0)
		return ;
	build(son[x][0]);
	build(son[x][1]);
	a[x]=a[son[x][0]]+a[son[x][1]];
	ll l=a[son[x][0]],r=a[son[x][1]];
	if(l>r)
		swap(l,r);
	if(mp[make_pair(l,r)]++==0)
		ins(make_pair(l,r));
	if(l!=r)
		all+=mp[make_pair(l,r)]>1;
}
void p(int x,ll z){
	if(x==0)
		return ;
	if(z<0){
		ll l=a[son[x][0]],r=a[son[x][1]];
		if(l!=r)
			all+=mp[make_pair(l,r)]>1;
		if(l>r)
			swap(l,r);
		if(--mp[make_pair(l,r)]==0)
			era(make_pair(l,r));
	}
	if(z>0){
		a[x]=a[son[x][0]]+a[son[x][1]];
		ll l=a[son[x][0]],r=a[son[x][1]];
		if(l>r)
			swap(l,r);
		if(mp[make_pair(l,r)]++==0)
			ins(make_pair(l,r));
		if(l!=r)
			all+=mp[make_pair(l,r)]>1;
	}
	p(fa[x],z);
}
void work(){
	if(cnt==0&&all==0)
		puts("YES");
	else
		puts("NO");
}
int main(){
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n;i++)
		scanf("%lld",&a[i]);
	for(int i=n+1;i<2*n;i++){
		scanf("%d%d",&son[i][0],&son[i][1]);
		fa[son[i][0]]=i,fa[son[i][1]]=i;
	}
	dfs(2*n-1);
	if(mxdep>75){
		while(q--)
			puts("NO");
		return 0;
	}
	q--;
	build(2*n-1);
	work();
	for(int i=1;i<=q;i++){
		int x;
		scanf("%d",&x);
		p(fa[x],-1);
		scanf("%lld",&a[x]);
		p(fa[x],1);
		work();
	}
	return 0;
}

源文件, 语言: C++14

詳細信息

Subtask #1:

score: 0

Wrong Answer

Test #1:

score: 30

Accepted

time: 1ms

memory: 7792kb

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: 1ms

memory: 7872kb

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: 30

Accepted

time: 0ms

memory: 10112kb

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:

YES
YES
YES
NO
NO
NO
NO
NO
NO
YES
YES
YES
YES
YES
YES
YES
YES
NO
NO
YES
YES
YES
YES
YES
YES
NO
NO
NO
NO
YES
NO
YES
YES
YES
YES
YES
YES
NO
NO
NO
NO
YES
YES
YES
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
YES
YES
YES
YES
YES
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
YES
...

result:

ok 1000 token(s): yes count is 375, no count is 625

Test #4:

score: 30

Accepted

time: 3ms

memory: 6156kb

input:

7 1000
88159166205053 95998544558881 48231159865354 231786835189365 84291070100955 225941839972605 33315221625793
2 5
6 4
7 3
1 10
8 11
9 12
6 150843468162951
2 75759088055460
1 86133344610051
4 140694127444493
1 63070113756930
1 90150689680608
6 147790469610032
7 46561924657801
2 103953340734616
6 ...

output:

NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO
YES
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
YES
YES
YES
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
N...

result:

ok 1000 token(s): yes count is 86, no count is 914

Test #5:

score: 0

Wrong Answer

time: 0ms

memory: 7872kb

input:

7 1000
5 6 7 3 2 5 5
4 7
3 5
1 2
10 6
8 9
12 11
5 2
5 1
5 1
1 2
3 2
5 1
5 2
6 3
4 2
4 1
2 1
5 1
5 1
5 1
7 1
1 2
5 1
5 1
6 3
6 3
5 1
2 2
7 2
7 1
7 1
2 2
1 2
4 2
4 1
1 1
3 1
5 1
2 2
2 2
4 1
2 1
7 2
6 1
2 1
6 2
5 2
1 1
1 1
6 3
7 2
6 3
4 1
1 1
5 1
2 2
7 2
5 1
4 2
5 2
7 2
7 1
4 1
3 2
3 2
1 1
7 2
5 2
1 1
...

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 [23rd token]

Subtask #2:

score: 0

Wrong Answer

Test #16:

score: 0

Wrong Answer

time: 300ms

memory: 32316kb

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:

YES
YES
YES
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
YES
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
N...

result:

wrong answer expected YES, found NO [957th token]

Subtask #3:

score: 0

Wrong Answer

Test #20:

score: 0

Wrong Answer

time: 2264ms

memory: 122628kb

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:

YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
YES
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
YES
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
YES
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO...

result:

wrong answer expected YES, found NO [433rd token]

Subtask #4:

score: 0

Time Limit Exceeded

Test #24:

score: 20

Accepted

time: 1042ms

memory: 7984kb

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:

YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
...

result:

ok 100000 token(s): yes count is 98093, no count is 1907

Test #25:

score: 0

Time Limit Exceeded

input:

100000 100000
7549638646 8066727970 9672316362 9615802181 6376690689 416134043 5288164622 2316444041 8423663950 1806779510 3010692396 7782858557 4229348735 1361364214 9005774175 6382408188 8174082766 8406340542 8599848784 3178078732 1395839441 5310497981 6807939596 2743315129 3143071583 3636776799 5...

output:

YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
YES
...