UOJ Logo

NOI.AC

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#214871#2642. colorHHC883100520ms13844kbC++1.3kb2024-11-22 22:28:222024-11-22 23:14:31

answer

#include<iostream>
using namespace std;
int n,m;
char col[(int)1e5+5];
int es[(int)2e5+5],nxt[(int)2e5+5],head[(int)1e5+5],cnt;
int deep[(int)1e5+5],fa[(int)1e5+5][25],pre[(int)1e5+5][2];
void link(int u,int v){
	es[++cnt]=v;
	nxt[cnt]=head[u];
	head[u]=cnt;
}
void dfs(int now,int fath){
	deep[now]=deep[fath]+1,fa[now][0]=fath;
	for(int i=1;i<=20;i++) fa[now][i]=fa[fa[now][i-1]][i-1];
	pre[now][0]=pre[fath][0],pre[now][1]=pre[fath][1];
	if(col[now]=='H') pre[now][0]++;
	else pre[now][1]++;
	for(int i=head[now];i;i=nxt[i]){
		if(es[i]==fath) continue;
		dfs(es[i],now);
	}
}
int lca(int x,int y){
	if(deep[x]<deep[y]) swap(x,y);
	for(int i=20;i>=0;i--) if(deep[fa[x][i]]>=deep[y]) x=fa[x][i];
	if(x==y) return x;
	for(int i=20;i>=0;i--) if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];
	return fa[x][0];
}
int main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin>>n>>m;
	cin>>col+1;
	int u,v;
	for(int i=1;i<n;i++){
		cin>>u>>v;
		link(u,v),link(v,u);
	}
	dfs(1,0);
	int x,y;
	char ch;
	while(m--){
		cin>>x>>y>>ch;
		int lca_=lca(x,y);
		if(ch=='H'){
			if(pre[x][0]+pre[y][0]-2*pre[lca_][0]+(col[lca_]=='H')) cout<<1;
			else cout<<0;
		}else{
			if(pre[x][1]+pre[y][1]-2*pre[lca_][1]+(col[lca_]=='G')) cout<<1;
			else cout<<0;
		}
	}
	return 0;
}

Details

小提示:点击横条可展开更详细的信息

Test #1:

score: 10
Accepted
time: 1ms
memory: 1400kb

input:

920 900
HHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHGHHGHHHHHHHGGHGHHHGHHGHGHHHHHH...

output:

0010100111100111101010001000010101100010001110110110001101100101111000101111100001111001110100001111...

result:

ok single line: '001010011110011110101000100001...1010100111010011101110111010101'

Test #2:

score: 10
Accepted
time: 1ms
memory: 1404kb

input:

927 949
HHHHGHGGGHHHHGHGHHHHHGHGGHGGGHHHGGHHHHHHGGGGGGHHHGGHHHHGHHHHGGGHHHGHGHHHHGGGGHHGHHGGHGHGGGGG...

output:

1111000011110111101101100110110011110101011000110111111111101110110011111011111110110011101010111111...

result:

ok single line: '111100001111011110110110011011...0011001011010111111011111001110'

Test #3:

score: 10
Accepted
time: 1ms
memory: 1404kb

input:

934 998
HHHHGHHHGHHGGGHGGHGHGHHHGHHGHGGGHHHHHGHHGGHHHHHHGHHHGGHHHHHGGHHHGHHHHHHHGHHGHGHGGHHGHGHHHGGH...

output:

1101010111111010110101011111110111111101101100011111001101110111111111011111101001111011001010101111...

result:

ok single line: '110101011111101011010101111111...1011101110011100101111100101110'

Test #4:

score: 10
Accepted
time: 0ms
memory: 1408kb

input:

941 947
HHHHHHHHHHHHHHHGHHHGHHHGHHHHGHHHGHHHHHHHHGHHHHHHHHHGHHHHHGHHHHHGHHGHHHHGHGGHHGHHHHHHHHHHGGHH...

output:

1111111011010110001101010101110100110001000101100101111101110001111111111110111011010101001111101111...

result:

ok single line: '111111101101011000110101010111...0101100011110110011000000000011'

Test #5:

score: 10
Accepted
time: 101ms
memory: 13264kb

input:

92189 98896
HHHHHHHHHGHHHHGGGHGHHHHHHGHHHHHGHHHHHHHHHGHGHHHGHHHHHHGGHHHGHGGHHHHHHHHHGHHHHHHGHGHGHHHG...

output:

1110111111111111111111111111111111111011110111111111111111110111111101111111111111111111111111101111...

result:

ok single line: '111011111111111111111111111111...1111111111111111111111111111111'

Test #6:

score: 10
Accepted
time: 73ms
memory: 13732kb

input:

95803 95747
HHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHGHHGHGHHHHGHGHHHHHHGGHHHHHHHHHHHHGHHHGHHHHHHHHHGHGGHHHHH...

output:

1011011101111111111111111101111111111011101101111110111111101111111011110111111101111111001100101111...

result:

ok single line: '101101110111111111111111110111...1111101101111110111111111001111'

Test #7:

score: 10
Accepted
time: 84ms
memory: 13324kb

input:

92610 90996
HHGGGHHGHGGGHGHGHGGGGGGHGGGHGGHGHGHGGHHHHHGHGGHGHGGGGHGGGHGGHHGHHHGGHGHGGHGGGHGGGGGGGGGG...

output:

1111111111111111111011111111111111111110111111111111100111111111011111111111101101111111111111011111...

result:

ok single line: '111111111111111111101111111111...1111110011111111111111111111111'

Test #8:

score: 10
Accepted
time: 85ms
memory: 13792kb

input:

96224 91494
HHHHHHHHGGHHGHHHHHHHHHHHHHGHHHGHHHHHHHHHHHHHHHHHGGHHHHHHGHHHHHHHHHHHHHHHHHGHGGGHGHGHHHHH...

output:

1111010110111100111111111111011011010101011111011101111011111011111011111111111111111111111011111101...

result:

ok single line: '111101011011110011111111111101...1101011011111111111111101101111'

Test #9:

score: 10
Accepted
time: 84ms
memory: 13372kb

input:

93031 96743
HHHHHHHHHGHHHHHHHHHHHHHHHHHGGHHHHGHHHGHHHHHHHHHGHHHHHHHHHHHHHHGGHHHHHGGHGHHHGHHHGHHHHHHG...

output:

0100011111101111011111110111001111101111110101110110111111111111111101111110110001011110011111011111...

result:

ok single line: '010001111110111101111111011100...1111111101110011111101011111110'

Test #10:

score: 10
Accepted
time: 90ms
memory: 13844kb

input:

96645 93594
HHHHHHHHHGHGHHHHHHHGHHHHGGGHHHHHHHHHHHHHHHHHHGHHHHHGHGHHHHHGHGHHHHHGHHHHGHHHHGGHHGHHHHGH...

output:

0101000110111110011111111111110111101011011101111110111111011011111111111110111110101111111111111111...

result:

ok single line: '010100011011111001111111111111...1110011111111111110110011111111'