USACO 2024 US Open Contest Silver Division - Painting Fence Posts

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

We can create a vector that holds each edge between two different fences. We can easily find the edges by noting that on each row/column as there will always be an even number of fences and every two will form an edge.

To find the length of a road, we are interested in the following:

• the length from a given fence to the respective point
• the perimeter of the fence
• a method to quickly find the distance between two fences.

All these subproblems boil down to implementation, the idea of solving being easy.

Source code

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

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int NMAX=2e5;
int n, p;
pair <int, int> posts[NMAX+5];
map <int, vector <pair <int, int>>> x, y;
vector <vector <int>> adj;
vector <int> len;
vector <int> index_ord;
int mars[NMAX+5];
struct position
{
    int index, l_fence;
    long long val ()
    {
        return len[index]+l_fence;
    }
    int nxt ()
    {
        if (l_fence==0)
            return index;
        return index+1;
    }
    int prev ()
    {
        return index;
    }
};
int dist (pair <int, int> x, pair <int, int> y)
{
    return abs (x.first-y.first)+abs (x.second-y.second);
}
optional<position> caut (vector <pair <int, int>> &v, int y)
{
    int i=lower_bound (v.begin(), v.end(), make_pair (y, 0ll))-v.begin();
    if (i<v.size() && v[i].first==y)
    {
        return position {index_ord[v[i].second], 0};
    }
    if (i&1)
    {
        pair <int, int> a=v[i-1], b=v[i];
        if ((index_ord[a.second]+1)%p!=index_ord[b.second]) swap (a, b);
        return position {index_ord[a.second], abs (a.first-y)};
    }
    return nullopt;
}
position getPoz (pair <int, int> a)
{
    if (x.count(a.first))
    {
        auto ret=caut (x[a.first], a.second);
        if (ret.has_value())
            return ret.value ();
    }
    auto ret=caut (y[a.second], a.first);
    return ret.value ();
}
int32_t main ()
{
    cin >> n >> p;
    for (int i=0;i<p;i++)
        cin >> posts[i].first >> posts[i].second;
    for (int i=0;i<p;i++)
    {
        x[posts[i].first].push_back ({posts[i].second, i});
        y[posts[i].second].push_back ({posts[i].first, i});
    }
    adj.resize (p);
    for (auto &chestie : x)
    {
        sort (chestie.second.begin(), chestie.second.end());
        for (int i=0;i<chestie.second.size();i++)
            adj[chestie.second[i].second].push_back (chestie.second[i^1].second);
    }
    for (auto &chestie : y)
    {
        sort (chestie.second.begin(), chestie.second.end());
        for (int i=0;i<chestie.second.size();i++)
            adj[chestie.second[i].second].push_back (chestie.second[i^1].second);
    }
    vector <int> ord;
    ord.push_back (0);
    while (true)
    {
        for (auto x : adj[ord.back()])
        {
            if (ord.size()>1 && ord[ord.size()-2]==x)
                continue;
            ord.push_back (x);
            break;
        }
        if (ord.back()==0)
            break;
    }
    ord.pop_back ();
    len.push_back (0);
    for (int i=1;i<=p;i++)
    {
        len.push_back (len.back()+dist (posts[ord[i-1]], posts[ord[i%p]]));
    }
    index_ord.resize (p);
    for (int i=0;i<p;i++)
        index_ord[ord[i]]=i;
    while (n--)
    {
        pair <int, int> start, end;
        cin >> start.first >> start.second >> end.first >> end.second;
        auto p1=getPoz (start), p2=getPoz (end);
        if (p1.val()>p2.val())
            swap (p1, p2);
        long long perim=len.back();
        if (2*(p2.val()-p1.val())>perim)
        {
            mars[p2.nxt()]++;
            mars[p]--;
            mars[0]++;
            mars[p1.prev()+1]--;
        }
        else
        {
            mars[p1.nxt()]++;
            mars[p2.prev()+1]--;
        }
    }
    for (int i=1;i<p;i++)
        mars[i]+=mars[i-1];
    for (int i=0;i<p;i++)
        cout << mars[index_ord[i]] << "\n";
    return 0;
}