USACO Bronze 2019 December - Livestock Lineup

Official Analysis (C++)

Solution w/ Graphs

What if there were up to $10^5$ cows? Then neither of the solutions provided in the analysis would be fast enough.

Say that we draw an edge between two cows if they must be adjacent. Then if a solution exists, the graph must be a union of paths.

(insert diagram)

We iterate over the cows in increasing lexicographical order. If a cow is not yet part of the answer and it is the endpoint of a path, then we add the entire path containing the cow to the answer.

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>;