USACO 2019 December Contest Silver Division - Milk Visits

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

Your goal is to find fast enough if there is the favorite type of cow on the path from \(A\) to \(B\). There are many ways of doing this, I will explain two ways here.

The first and the easiest way consists of finding the connected components if we separate the Hs and the Gs. In order to see if we can get the type of milk we want, there are two conditions we have to check. Either the points belong to different connected components (therefore, we must go from a H to a G at some point), or they have the correct type of milk already. Otherwise, we can't get the type of milk we need.

For those knowing Gold level data structures, we can also do it by precomputing where is the most recent place such that we have that favorite type of cow upwards in the tree, something we need to precompute the LCAs for, using binary lifting.

For each query, we will rely on finding LCA using binary lifting as well as these most recent places using the aforementioned precomputing.

Source codes

The source codes in C++ can be seen below.

DFS Solution

#include <iostream>
#include <vector>
#include <queue>
#include <string>
#include <fstream>
#include <climits>
using namespace std;
int n, m;
vector<pair<vector<int>, char>> comp = {};
string cows;
vector<vector<int>> roads;
int pos = 0;
vector<bool> visited;

void traverse(int start) {
    queue<int> q;
    q.push(start);
    while (!q.empty()) {
        int a = q.front();
        comp[pos].first.push_back(a);
        visited[a] = true;
        q.pop();
        for (auto i: roads[a]) {
            if (cows[i] == comp[pos].second && !visited[i]) {
                q.push(i);
                visited[i] = true;
            }
        }
    }
}

int main() {

    ifstream cin("milkvisits.in");
    ofstream cout("milkvisits.out");

    cin >> n >> m;
    cin >> cows;
    roads.resize(n);
    visited.resize(n, false);
    int a;
    int b;
    for (int i = 0; i < n - 1; i++) {
        cin >> a >> b;
        a--;
        b--;
        roads[a].push_back(b);
        roads[b].push_back(a);
    }

    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            comp.push_back({{}, cows[i]});
            visited[i] = true;
            traverse(i);
            pos++;
        }
    }
    vector<pair<int, char>> type(n);
    int p = comp.size();
    for (int i = 0; i < p; i++) {
        for (auto j: comp[i].first) {
            type[j] = {i, comp[i].second};
        }
    }

    char req;
    string ans = "";
    for (int i = 0; i < m; i++) {
        cin >> a >> b >> req;
        a--;
        b--;
        if (type[a].first != type[b].first || type[a].second == req) {
            ans += "1";
        }
        else {
            ans += "0";
        }
    }
    cout << ans;
    return 0;
}

LCA Solution

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

vector<vector<int> > tree;

string s;
int n, q, lstG[100002], lstH[100002], anc[17][100002], lvl[100002];

void dfs(int parent, int node)
{
    if(s[node-1] == 'G')
        lstG[node] = node;
    else
        lstG[node] = lstG[parent];
    if(s[node-1] == 'H')
        lstH[node] = node;
    else
        lstH[node] = lstH[parent];
    anc[0][node] = parent;
    for(int i = 1; i <= 16; i++)
        anc[i][node] = anc[i-1][anc[i-1][node]];
    lvl[node] = lvl[parent] + 1;
    for(int i = 0; i < (int) tree[node].size(); i++)
    {
        int nxt = tree[node][i];
        if(nxt == parent)
            continue;
        dfs(node, nxt);
    }
}

int query(int a, int b)
{
    if(lvl[a] > lvl[b])
        swap(a, b);
    for(int i = 16; i >= 0; i--)
        if(lvl[b] - (1<<i) >= lvl[a])
            b = anc[i][b];
    if(a == b)
        return a;
    for(int i = 16; i >= 0; i--)
        if(anc[i][a] != anc[i][b])
            a = anc[i][a], b = anc[i][b];
    return anc[0][a];
}
int main()
{
    ifstream cin("milkvisits.in");
    ofstream cout("milkvisits.out");

    cin >> n >> q;
    cin >> s;

    tree.resize(n+1);
    for(int i = 0; i + 1 < n; i++)
    {
        int a, b;
        cin >> a >> b;
        tree[a].push_back(b);
        tree[b].push_back(a);
    }

    dfs(0, 1);

    for(; q; q--)
    {
        int L, R;
        char c;
        cin >> L >> R >> c;

        int anc = query(L, R);
        if(c == 'G')
        {
            if(lvl[lstG[L]] >= lvl[anc] || lvl[lstG[R]] >= lvl[anc])
                cout << 1;
            else
                cout << 0;
        }
        else
        {
            if(lvl[lstH[L]] >= lvl[anc] || lvl[lstH[R]] >= lvl[anc])
                cout << 1;
            else
                cout << 0;
        }
    }
    return 0;
}