UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#214838#2642. colorThySecret1001589ms12812kbC++112.4kb2024-11-22 18:54:092024-11-22 23:10:46

answer

// Problem: P5836 [USACO19DEC] Milk Visits S
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P5836
// Date: 2024-04-21 09:17:10
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// 
// Programmed by ThySecret

#include <bits/stdc++.h>

using namespace std;

// #define int long long
// #define DEBUG
#define x first
#define y second
#define File(a) freopen(a".in", "r", stdin); freopen(a".out", "w", stdout)

typedef long long ll;
typedef pair<int, int> PII;

const int N = 200010, M = 400010;
const int INF = 0x3f3f3f3f;

int n, m;
char s[N];
int h[N], e[M], ne[M], idx;
int depth[N], pre[N][20];
int cntH[N], cntG[N];

inline void add(int a, int b)
{
	e[++ idx] = b, ne[idx] = h[a], h[a] = idx;
}

void prework()
{
	memset(depth, 0x3f, sizeof depth);
	depth[0] = 0, depth[1] = 1;
	queue<int> q;
	q.push(1);
	
	while (!q.empty())
	{
		int ver = q.front(); q.pop();
		
		if (s[ver] == 'H') cntH[ver] = cntH[pre[ver][0]] + 1;
		else cntH[ver] = cntH[pre[ver][0]];
		if (s[ver] == 'G') cntG[ver] = cntG[pre[ver][0]] + 1;
		else cntG[ver] = cntG[pre[ver][0]];
		
		for (int i = h[ver]; ~i; i = ne[i])
		{
			int j = e[i];
			if (depth[j] > depth[ver] + 1)
			{
				depth[j] =  depth[ver] + 1;
				q.push(j);
				
				pre[j][0] = ver;
				for (int k = 1; k <= 19; k ++)
					pre[j][k] = pre[pre[j][k - 1]][k - 1];
			}
		}
	}
}

int lca(int a, int b)
{
	if (depth[a] < depth[b]) swap(a, b);
	
	for (int k = 19; k >= 0; k --)
		if (depth[pre[a][k]] >= depth[b])
			a = pre[a][k];
			
	if (a == b) return a;

	for (int k = 19; k >= 0; k --)
		if (pre[a][k] != pre[b][k])
			a = pre[a][k], b = pre[b][k];
	
	return pre[a][0];
}

signed main()
{
	// ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	memset(h, -1, sizeof h);
	cin >> n >> m;
	cin >> s + 1;
	for (int i = 1; i < n; i ++)
	{
		int a, b; cin >> a >> b;
		add(a, b), add(b, a);
	}
	
	prework();
	
	#ifdef DEBUG
	// for (int i = 1; i <= n; i ++)
		// cout << cntH[i] << ' ' << cntG[i] << '\n';
	#endif
	
	while (m --)
	{
		int a, b; cin >> a >> b;
		char str; cin >> str;
		int p = lca(a, b);
		// cout << p << '\n';
		if (str == 'H')
		{
			int tmp = cntH[a] + cntH[b] - 2 * cntH[p] + (s[p] == 'H');
			if (tmp) cout << 1;
			else cout << 0;
		}
		else
		{
			int tmp = cntG[a] + cntG[b] - 2 * cntG[p] + (s[p] == 'G');
			if (tmp) cout << 1;
			else cout << 0;
		}
	}
	
	return 0;
}

详细

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

Test #1:

score: 10
Accepted
time: 5ms
memory: 2948kb

input:

920 900
HHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHGHHGHHHHHHHGGHGHHHGHHGHGHHHHHH...

output:

0010100111100111101010001000010101100010001110110110001101100101111000101111100001111001110100001111...

result:

ok single line: '001010011110011110101000100001...1010100111010011101110111010101'

Test #2:

score: 10
Accepted
time: 6ms
memory: 2948kb

input:

927 949
HHHHGHGGGHHHHGHGHHHHHGHGGHGGGHHHGGHHHHHHGGGGGGHHHGGHHHHGHHHHGGGHHHGHGHHHHGGGGHHGHHGGHGHGGGGG...

output:

1111000011110111101101100110110011110101011000110111111111101110110011111011111110110011101010111111...

result:

ok single line: '111100001111011110110110011011...0011001011010111111011111001110'

Test #3:

score: 10
Accepted
time: 2ms
memory: 2948kb

input:

934 998
HHHHGHHHGHHGGGHGGHGHGHHHGHHGHGGGHHHHHGHHGGHHHHHHGHHHGGHHHHHGGHHHGHHHHHHHGHHGHGHGGHHGHGHHHGGH...

output:

1101010111111010110101011111110111111101101100011111001101110111111111011111101001111011001010101111...

result:

ok single line: '110101011111101011010101111111...1011101110011100101111100101110'

Test #4:

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

input:

941 947
HHHHHHHHHHHHHHHGHHHGHHHGHHHHGHHHGHHHHHHHHGHHHHHHHHHGHHHHHGHHHHHGHHGHHHHGHGGHHGHHHHHHHHHHGGHH...

output:

1111111011010110001101010101110100110001000101100101111101110001111111111110111011010101001111101111...

result:

ok single line: '111111101101011000110101010111...0101100011110110011000000000011'

Test #5:

score: 10
Accepted
time: 267ms
memory: 12360kb

input:

92189 98896
HHHHHHHHHGHHHHGGGHGHHHHHHGHHHHHGHHHHHHHHHGHGHHHGHHHHHHGGHHHGHGGHHHHHHHHHGHHHHHHGHGHGHHHG...

output:

1110111111111111111111111111111111111011110111111111111111110111111101111111111111111111111111101111...

result:

ok single line: '111011111111111111111111111111...1111111111111111111111111111111'

Test #6:

score: 10
Accepted
time: 262ms
memory: 12736kb

input:

95803 95747
HHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHGHHGHGHHHHGHGHHHHHHGGHHHHHHHHHHHHGHHHGHHHHHHHHHGHGGHHHHH...

output:

1011011101111111111111111101111111111011101101111110111111101111111011110111111101111111001100101111...

result:

ok single line: '101101110111111111111111110111...1111101101111110111111111001111'

Test #7:

score: 10
Accepted
time: 220ms
memory: 12400kb

input:

92610 90996
HHGGGHHGHGGGHGHGHGGGGGGHGGGHGGHGHGHGGHHHHHGHGGHGHGGGGHGGGHGGHHGHHHGGHGHGGHGGGHGGGGGGGGGG...

output:

1111111111111111111011111111111111111110111111111111100111111111011111111111101101111111111111011111...

result:

ok single line: '111111111111111111101111111111...1111110011111111111111111111111'

Test #8:

score: 10
Accepted
time: 260ms
memory: 12776kb

input:

96224 91494
HHHHHHHHGGHHGHHHHHHHHHHHHHGHHHGHHHHHHHHHHHHHHHHHGGHHHHHHGHHHHHHHHHHHHHHHHHGHGGGHGHGHHHHH...

output:

1111010110111100111111111111011011010101011111011101111011111011111011111111111111111111111011111101...

result:

ok single line: '111101011011110011111111111101...1101011011111111111111101101111'

Test #9:

score: 10
Accepted
time: 271ms
memory: 12440kb

input:

93031 96743
HHHHHHHHHGHHHHHHHHHHHHHHHHHGGHHHHGHHHGHHHHHHHHHGHHHHHHHHHHHHHHGGHHHHHGGHGHHHGHHHGHHHHHHG...

output:

0100011111101111011111110111001111101111110101110110111111111111111101111110110001011110011111011111...

result:

ok single line: '010001111110111101111111011100...1111111101110011111101011111110'

Test #10:

score: 10
Accepted
time: 296ms
memory: 12812kb

input:

96645 93594
HHHHHHHHHGHGHHHHHHHGHHHHGGGHHHHHHHHHHHHHHHHHHGHHHHHGHGHHHHHGHGHHHHHGHHHHGHHHHGGHHGHHHHGH...

output:

0101000110111110011111111111110111101011011101111110111111011011111111111110111110101111111111111111...

result:

ok single line: '010100011011111001111111111111...1110011111111111110110011111111'