ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#214838 | #2642. color | ThySecret | 100 | 1589ms | 12812kb | C++11 | 2.4kb | 2024-11-22 18:54:09 | 2024-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'