USACO Gold 2019 December - Milk Visits
Author: Benjamin Qi
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;34using ll = long long;5using ld = long double;6using db = double;7using str = string; // yay python!89using 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;34using ll = long long;5using ld = long double;6using db = double;7using str = string; // yay python!89using 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!