USACO Gold 2019 December - Milk Visits

Author: Benjamin Qi

Official Analysis (Offline)

To solve this problem online, we need efficiently find the closest ancestor of a farm with a certain milk type. Here are several ways to do this.

Method 1

Run the same DFS mentioned in the analysis. For each milk type, store the Euler tour indices at which the answer changes. Then we can get the answer for a vertex using a single lower_bound operation on the vector for the corresponding milk type.

Time Complexity: per query.

1#include <bits/stdc++.h>
2using namespace std;
3
4using ll = long long;
5using ld = long double;
6using db = double;
7using str = string; // yay python!
8
9using pi = pair<int,int>;
10using pl = pair<ll,ll>;

Method 2

Generate a persistent array for each vertex where the indices of the array correspond to the milk types.

Time Complexity: per query. Apparently this is doable in per query (paper). Is this bound optimal for this problem?

Method 3

Use HLD. We can check whether there exists a farm in the path from a vertex to the root of the heavy path containing () with the desired milk type in time using an unordered map. Note that we only need to do two upper_bound operations per query.

Time Complexity: per query.

In the solution below, I refer to milk types as "colors."

1#include <bits/stdc++.h>
2using namespace std;
3
4using ll = long long;
5using ld = long double;
6using db = double;
7using str = string; // yay python!
8
9using pi = pair<int,int>;
10using pl = pair<ll,ll>;

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!

Give Us Feedback on USACO Gold 2019 December - Milk Visits!