Problem: ladders_and_snakes (2019 round1)

**N** ladders have been set up in a room, which can be represented as a 2D plane when viewed from the side. The room's floor is the horizontal line with y-coordinate 0, and its ceiling is the horizontal line with y-coordinate **H**. The _i_th ladder is a vertical line segment between integral coordinates (**Xi**, **Ai**) and (**Xi**, **Bi**), located within the inclusive bounds of the room (such that 0 ≤ **Ai** < **Bi** ≤ **H**). Note that each ladder may be touching the floor and/or ceiling, or may be floating in mid-air (don't question it). No two ladders overlap with one another (even at their endpoints). 

Sneider the Snake has taken an interest in this room, and may add 0 or more
snakes to it. The _j_th snake will be a vertical line segment between some
coordinates (**xj**, **aj**) and (**xj**, **bj**), located strictly inside the
bounds of the room (with **xj** being any non-negative real number, and **aj**
and **bj** being integers such that 0 < **aj** ≤ **bj** < **H**). A snake may
be a length-0 line segment, with its endpoints being equal, in which case it
occupies only a single point on the plane. No snake may overlap with any other
snake, nor with any ladder (even at an endpoint).

Flynn the Flying Squirrel finds herself on the floor at coordinates (0, 0),
and wants to reach coordinates (0, **H**) on the ceiling. At any point, she
may gracefully hover horizontally (left or right) as long as she doesn't
overlap with any snake (including exactly at one of its endpoints). She may
also move vertically (up or down) as long as she's overlapping with a ladder
(including exactly at one of its endpoints). Flynn always moves continuously
around the plane (she does not skip from one integral coordinate to the next).

Sneider the Snake doesn't want Flynn to reach her destination, just because he
likes being mean. Determine the minimum possible sum of lengths of snakes
which Sneider must place such that Flynn will be unable to reach coordinates
(0, **H**) from her initial position (0, 0), if possible.

### Input

Input begins with an integer **T**, the number of rooms. For each room, there
is first a line containing the space-separated integers **N** and **H**. Then,
**N** lines follow, the _i_th of which contains the space-separated integers
**Xi**, **Ai**, and **Bi**.

### Output

For the _i_th room, print a line containing "Case #_i_: " followed by 1
integer, either the minimum total length of snakes required, or -1 if Sneider
cannot prevent Flynn from reaching coordinates (0, **H**).

### Constraints

1 ≤ **T** ≤ 150  
1 ≤ **N** ≤ 50  
1 ≤ **H** ≤ 100,000  
0 ≤ **Xi** ≤ 100,000  
0 ≤ **Ai** < **Bi** ≤ **H**  
0 ≤ **xj**  
0 < **aj** ≤ **bj** < **H**  

### Explanation of Sample

In the first case, one optimal way for Sneider to prevent Flynn from reaching
coordinates (0, 4) involves placing a length-2 snake with endpoints (0.5, 1)
and (0.5, 3), as illustrated below (with ladders indicated in brown and the
snake indicated in green):

![]({{PHOTO_ID:262526658147947}})

In the second case, Flynn already can't reach coordinates (0, 100) even if
Sneider doesn't place any snakes.

In the third case, Flynn cannot be prevented from reaching coordinates (0, 9).

In the fourth case, one optimal way for Sneider to prevent Flynn from reaching
coordinates (0, 30) involves placing a length-1 snake with endpoints (9, 20)
and (9, 21), two length-0 snakes at coordinates (14, 20) and (16, 20), and a
length-2 snake with endpoints (24, 20) and (24, 22). The sum of these snakes'
lengths is 1 + 0 + 0 + 2 = 3.



Sample input:
7
2 4
0 0 3
1 1 4
2 100
1 0 49
1 50 100
3 9
33 0 6
66 0 9
99 3 9
7 30
10 0 10
20 0 10
5 8 21
15 7 20
25 9 22
10 20 30
20 20 30
4 14
34 5 13
17 0 8
41 4 9
8 6 14
11 15
2 1 7
2 9 15
3 0 4
5 7 13
7 0 8
8 3 6
8 8 15
10 2 9
11 8 13
14 6 15
16 0 6
25 614
3 497 552
3 133 298
12 395 522
9 112 493
11 567 614
0 364 401
4 105 386
2 0 449
4 73 80
4 475 505
6 275 423
1 20 380
10 29 180
0 41 352
8 56 157
6 0 70
11 284 317
7 247 385
10 212 614
8 422 469
12 0 337
8 504 557
1 399 598
3 424 459
0 452 486


Sample output:
Case #1: 2
Case #2: 0
Case #3: -1
Case #4: 3
Case #5: 6
Case #6: 5
Case #7: 502



Code: // Ladders and Snakes
// Solution by Jacob Plachta
 
#define DEBUG 0
 
#include <algorithm>
#include <functional>
#include <numeric>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <complex>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <cassert>
#include <string>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <sstream>
using namespace std;
 
#define LL long long
#define LD long double
#define PR pair<int,int>
 
#define Fox(i,n) for (i=0; i<n; i++)
#define Fox1(i,n) for (i=1; i<=n; i++)
#define FoxI(i,a,b) for (i=a; i<=b; i++)
#define FoxR(i,n) for (i=(n)-1; i>=0; i--)
#define FoxR1(i,n) for (i=n; i>0; i--)
#define FoxRI(i,a,b) for (i=b; i>=a; i--)
#define Foxen(i,s) for (i=s.begin(); i!=s.end(); i++)
#define Min(a,b) a=min(a,b)
#define Max(a,b) a=max(a,b)
#define Sz(s) int((s).size())
#define All(s) (s).begin(),(s).end()
#define Fill(s,v) memset(s,v,sizeof(s))
#define pb push_back
#define mp make_pair
#define x first
#define y second
 
template<typename T> T Abs(T x) { return(x<0 ? -x : x); }
template<typename T> T Sqr(T x) { return(x*x); }
string plural(string s) { return(Sz(s) && s[Sz(s)-1]=='x' ? s+"en" : s+"s"); }
 
const int INF = (int)1e9;
const LD EPS = 1e-12;
const LD PI = acos(-1.0);
 
#if DEBUG
#define GETCHAR getchar
#else
#define GETCHAR getchar_unlocked
#endif
 
bool Read(int &x)
{
    char c,r=0,n=0;
    x=0;
        for(;;)
        {
            c=GETCHAR();
                if ((c<0) && (!r))
                    return(0);
                if ((c=='-') && (!r))
                    n=1;
                else
                if ((c>='0') && (c<='9'))
                    x=x*10+c-'0',r=1;
                else
                if (r)
                    break;
        }
        if (n)
            x=-x;
    return(1);
}
 
#define LIM 50
 
struct Dinic {
	struct Edge {
		int to, rev, c, f;
		Edge(int to, int rev, int c, int f) : to(to), rev(rev), c(c), f(f) {}
	};
	vector<int> lvl, ptr, q;
	vector< vector<Edge> > adj;
	
	Dinic(int n) : lvl(n), ptr(n), q(n), adj(n) {}
	
	void addEdge(int a, int b, int c) {
		adj[a].pb(Edge(b, Sz(adj[b]), c, 0));
		adj[b].pb(Edge(a, Sz(adj[a]) - 1, 0, 0));
	}
	
	int dfs(int v, int t, int f) {
		if (v == t || !f) return f;
		for (int& i = ptr[v]; i < Sz(adj[v]); i++) {
			Edge& e = adj[v][i];
			if (lvl[e.to] == lvl[v] + 1) {
				if (int p = dfs(e.to, t, min(f, e.c - e.f))) {
					e.f += p, adj[e.to][e.rev].f -= p;
					return p;
				}
			}
		}
		return 0;
	}
	
	int calc(int s, int t) {
		int L, flow = 0; q[0] = s;
		Fox(L,31) {
			do {
				lvl = ptr = vector<int>(Sz(q));
				int qi = 0, qe = lvl[s] = 1;
				while (qi < qe && !lvl[t]) {
					int i, v = q[qi++];
					Fox(i,Sz(adj[v])) {
						Edge e=adj[v][i];
						if (!lvl[e.to] && (e.c - e.f) >> (30 - L)) {
							q[qe++] = e.to, lvl[e.to] = lvl[v] + 1;
						}
					}
				}
				while (int p = dfs(s, t, INF)) flow += p;
			} while (lvl[t]);
		}
		return flow;
	}
};
 
int main()
{
        if (DEBUG)
            freopen("in.txt","r",stdin);
    // vars
    int T,t;
    int N,H;
    int i,j,k;
    int X[LIM],A[LIM],B[LIM];
    // testcase loop
    Read(T);
        Fox1(t,T)
        {
            // input
            Read(N),Read(H);
                Fox(i,N)
                    Read(X[i]),Read(A[i]),Read(B[i]);
            // construct flow graph
            Dinic D(N+2);
                Fox(i,N)
                {
                    // connected to bottom?
                        if (A[i]==0)
                            D.addEdge(N,i,1e7);
                    // connected to top?
                        if (B[i]==H)
                            D.addEdge(i,N+1,1e7);
                    // consider connections to other ladders
                        Fox(j,N)
                            if (X[i]<X[j])
                            {
                                // compute combined length of connecting, unobstructed y-coordinate intervals
                                vector<pair<int,PR> > E;
                                    Fox(k,N)
                                        if ((X[i]<=X[k]) && (X[k]<=X[j]))
                                        {
                                            E.pb(mp(A[k],mp(1,k)));
                                            E.pb(mp(B[k],mp(0,k)));
                                        }
                                int s=0;
                                set<int> S;
                                sort(All(E));
                                    Fox(k,Sz(E))
                                    {
                                        if (E[k].y.x)
                                            S.insert(E[k].y.y);
                                        else
                                            S.erase(E[k].y.y);
                                        if ((Sz(S)==2) && (S.count(i)) && (S.count(j)))
                                            s+=E[k+1].x-E[k].x;
                                    }
                                    if (s)
                                    {
                                        D.addEdge(i,j,s);
                                        D.addEdge(j,i,s);
                                    }
                            }
                }
            // compute min cut
            int ans=D.calc(N,N+1);
                if (ans>=1e7)
                    ans=-1;
            // output
            printf("Case #%d: %d\n",t,ans);
        }
    return(0);
}