Home » 国际竞赛 » Details

USACO 2019 December Contest, Silver Problem 3. Milk Visits

Category: 国际竞赛, 计算机国际竞赛 Date: 2022年7月1日下午2:49

USACO 2019 December Contest, Silver Problem 3. Milk Visits

Farmer John is planning to build $N$ ( $1 \leq N \leq 10^{5}$ ) farms that will be connected by $N - 1$ roads, forming a tree (i.e., all farms are reachable from each-other, and there are no cycles). Each farm contains a cow, whose breed is either Guernsey or Holstein.

Farmer John's $M$ friends ( $1 \leq M \leq 10^{5}$ ) often come to visit him. During a visit with friend $i$ , Farmer John will walk with his friend along the unique path of roads from farm $A_{i}$ to farm $B_{i}$ (it may be the case that $A_{i} = B_{i}$ ). Additionally, they can try some milk from any cow along the path they walk. Since most of Farmer John's friends are also farmers, they have very strong preferences regarding milk. Some of his friends will only drink Guernsey milk, while the remainder will only drink Holstein milk. Any of Farmer John's friends will only be happy if they can drink their preferred type of milk during their visit.

Please determine whether each friend will be happy after visiting.

SCORING:

Test cases 2-5 satisfy $N \leq 10^{3}, M \leq 2 \cdot 10^{3} .$

INPUT FORMAT (file milkvisits.in):

The first line contains the two integers $N$ and $M$ .The second line contains a string of length $N$ . The $i$ th character of the string is 'G' if the cow in the $i$ th farm is a Guernsey, or 'H' if the cow in the $i$ th farm is a Holstein.

The next $N - 1$ lines each contain two distinct integers $X$ and $Y$ ( $1 \leq X, Y \leq N$ ), indicating that there is a road between farms $X$ and $Y$ .

The next $M$ lines contain integers $A_{i}$ , $B_{i}$ , and a character $C_{i}$ . $A_{i}$ and $B_{i}$ represent the endpoints of the path walked during friend $i$ 's visit, while $C_{i}$ is either G or H if the $i$ th friend prefers Guernsey milk or Holstein milk.

OUTPUT FORMAT (file milkvisits.out):

Print a binary string of length $M$ . The $i$ th character of the string should be '1' if the $i$ th friend will be happy, or '0' otherwise.

SAMPLE INPUT:

SAMPLE OUTPUT:

Here, the path from farm 1 and farm 4 involves farms 1, 2, and 4. All of these contain Holsteins, so the first friend will be satisfied while the second one will not.

Problem credits: Spencer Compton

<h3>USACO 2019 December Contest, Silver Problem 3. Milk Visits 题解(翰林国际教育提供，仅供参考)</h3>
<p style="text-align: center;">题解请<a href="/register" target="_blank" rel="noopener">注册</a>或<a href="/login" target="_blank" rel="noopener">登录</a>查看</p>
[/hide]

(Analysis by Benjamin Qi)

Say that two cows are in the same connected component if all cows on the path between them are of the same type. We can generate these components with a DFS.

For each friend's path, if the endpoints of the path are in different components then he is clearly satisfied since both types of cows must appear on the path. Otherwise, all cows in the path have the same type, so it suffices to check whether the cow at the starting point of the path is of the type which the friend prefers.

It follows that this problem is solvable in $O (N + M)$ time. My code is below:

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

typedef vector<int> vi; 
 
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)
 
#define pb push_back
 
void setIO(string name) {
	ios_base::sync_with_stdio(0); cin.tie(0);
	freopen((name+".in").c_str(),"r",stdin);
	freopen((name+".out").c_str(),"w",stdout);
}

const int MX = 100005;

int N,M,comp[MX],num;
char col[MX];
vi adj[MX];
 
void dfs(int x) {
	if (comp[x]) return;
	comp[x] = num;
	trav(t,adj[x]) if (col[t] == col[x]) dfs(t);
}
 
int main() {
	setIO("milkvisits"); cin >> N >> M;
	string s; cin >> s;
	FOR(i,1,N+1) col[i] = s[i-1];
	F0R(i,N-1) {
		int A,B; cin >> A >> B;
		adj[A].pb(B), adj[B].pb(A);
	}
	FOR(i,1,N+1) if (!comp[i]) {
		num ++;
		dfs(i);
	}
	F0R(i,M) {
		int A,B; char C; cin >> A >> B >> C;
		if (col[A] == C || comp[A] != comp[B]) cout << 1;
		else cout << 0;
	}
	cout << "\n";
}

[/hide]