Learning Algorithms

アルゴリズムの勉強メモ

Codeforces Testing Round 1 C. Circular RMQ

Codeforces Testing Round 1 C. Circular RMQ

Problem - C - Codeforces

感想

区間加算、区間最小値を処理する遅延セグメント木をライブラリに追加したので、貼るだけの問題で試しておいた。

解法

貼るだけ。ただし入力が親切じゃないので、getlineで入力をとって' 'でパースしてどちらのクエリなのかをみないといけない。

実装
#include "bits/stdc++.h"
using namespace std;

static const int INF = 0x3f3f3f3f;

//区間加算、区間最小値
template<typename Type>
struct LazySegmentTree {
        vector<Type> data, lazy;
        int n;
        LazySegmentTree(int x) {
                n = pow(2, ceil(log2(x)));
                data.resize(2 * n - 1, INF);
                lazy.resize(2 * n - 1, 0);
        }
        void init(int k, Type p) {
                k += n - 1;
                data[k] = p;
                while (k > 0) {
                        k = (k - 1) / 2;
                        data[k] = min(data[k * 2 + 1], data[k * 2 + 2]);
                }
        }
        void add(int a, int b, int x) { return add(a, b, x, 0, 0, n); } //[a, b)
        void add(int a, int b, int x, int k, int l, int r) {
                if (r <= a || b <= l) return;
                if (a <= l && r <= b) {
                        lazy[k] += x;
                        return;
                }
                int m = (l + r) / 2;
                add(a, b, x, k * 2 + 1, l, m);
                add(a, b, x, k * 2 + 2, m, r);
                data[k] = min(data[k * 2 + 1] + lazy[k * 2 + 1], data[k * 2 + 2] + lazy[k * 2 + 2]);
        }
        Type getmin(int a, int b) { return getmin(a, b, 0, 0, n); } //[a, b)
        Type getmin(int a, int b, int k, int l, int r) {
                if (r <= a || b <= l) return INF;
                if (a <= l && r <= b) return data[k] + lazy[k];
                int m = (l + r) / 2;
                Type left = getmin(a, b, k * 2 + 1, l, m);
                Type right = getmin(a, b, k * 2 + 2, m, r);
                return min(left, right) + lazy[k];
        }
};

void solve() {
        int n;
        cin >> n;
        LazySegmentTree<int> st(n);
        for (int i = 0; i < n; i ++) { 
                int a;
                cin >> a;
                st.init(i, a);
        }
        int q;
        cin >> q;
        cin.ignore();
        while (q --) {
                string s;
                getline(cin, s);
                int cnt = 0;
                for (int i = 0; i < s.size(); i ++) cnt += s[i] == ' ';
                if (cnt == 1) {
                        int sp;
                        for (int i = 0; i < s.size(); i ++) {
                                if (s[i] == ' ') { 
                                        sp = i;
                                        break;
                                }
                        }
                        int l = stoi(s.substr(0, sp));
                        int r = stoi(s.substr(sp, s.size()));
                        if (l <= r) cout << st.getmin(l, r + 1) << endl;
                        else cout << min(st.getmin(0, r + 1), st.getmin(l, n)) << endl;
                } else {
                        int sp1 = 0, sp2;
                        for (int i = 0; i < s.size(); i ++) {
                                if (s[i] == ' ' && !sp1) {
                                        sp1 = i;
                                        continue;
                                }
                                if (s[i] == ' ' && sp1) {
                                        sp2 = i;
                                }
                        }
                        int l = stoi(s.substr(0, sp1));
                        int r = stoi(s.substr(sp1, sp2));
                        int v = stoi(s.substr(sp2, s.size()));
                        if (l <= r) { 
                                st.add(l, r + 1, v);
                        } else {
                                st.add(0, r + 1, v);
                                st.add(l, n, v);
                        }
                }
        }
        return;
}

int main() {
        ios_base::sync_with_stdio(false);
        cin.tie(0);
        solve();
        return 0;
}

CS Academy 048 D. Dominant Free Sets

CS Academy 048 D. Dominant Free Sets

CS Academy

感想

アルゴリズムの正当性を証明していたにも$\ AC\ $できず......。結局FenwickTreeのクエリ処理時にMODをとっていなかっただけだった。

解法

まず$\ x\ $に関してソートしておき、その列の上で順に$\ y\ $を見ていくことを考える。取り出す部分列の中で、ある$\ i\ $について、$\ x_i < x_{i + 1}\ $となっているならば、$\ y_i > y_{i + 1}\ $となっていればよい。$\ x_i = x_{i + 1}\ $となっているならば、$\ y\ $はどうなっていてもいけない($\ =\ $は$\ \leq\ $でもあり$\ \geq\ $でもあるからだ)。これは結局、$\ x\ $が同じものについては$\ y\ $についてソートしておけばよい(つまり普通にペアのソートをする)。

そうすると、$\ y\ $の数列について、狭義単調減少な部分列の個数を求める問題に帰着する。これをdpで求める。

dp[i] := i - 1までの、y[i]より大きい数を末尾とする部分列の個数 + 1(自分自身だけで作る部分列の個数)+ dp[i - 1](自分自身を使わない部分列の個数)

となる。最初の2項が自分自身が末尾になる部分列の個数であるから、その値を保存しておきたい。そしてその総和をとりたいので、FenwickTreeで位置y[i]にその値を加えることで、うまく総和をとれるようにする。

あとは正しくMODをとりながら計算してdp[n - 1]を出力する。

実装
#include "bits/stdc++.h"
using namespace std;

#define all(x)  x.begin(), x.end()
#define mp      make_pair
#define pii     pair<int, int>
#define ll      long long

static const int MOD = 1000000007;

//0-origin
template <typename T>
struct FenwickTree {
	vector<T> data;
	FenwickTree(int n) : data(n, 0) {}
        //v[i] += x
	void add(int i, T x) { for (int p = i; p < (int)data.size(); p |= p + 1) data[p] += x; }
        //[0, i)
	T sum(int i) {
		T s = 0;
                for (int p = i - 1; p >= 0; p = (p & (p + 1)) - 1) s += data[p];
		return s;
	}
        //[l, r)
	T sum(int l, int r) { return sum(r) - sum(l); }
};

void solve() {
        int n;
        cin >> n;
        vector<pair<long long, long long>> p(n);
        for (int i = 0; i < n; i ++) cin >> p[i].first >> p[i].second;
        sort(all(p));
        FenwickTree<long long> ft(101010);
        vector<long long> v(n);
        for (int i = 0; i < n; i ++) v[i] = p[i].second;
        long long dp[101010];
        dp[0] = 1;
        for (int i = 0; i < n; i ++) {
                long long sum = ft.sum(v[i] + 1, 101010) % MOD;
                ft.add(v[i], (sum + 1) % MOD);
                dp[i] = ((i == 0 ? 0 : dp[i - 1]) + sum + 1) % MOD;
        }
        cout << dp[n - 1] % MOD << endl;
        return;
}

int main() {
        ios_base::sync_with_stdio(false);
        cin.tie(0);
        solve();
        return 0;
}

Atcoder Grand Contest 002 F. Leftmost Ball

Atcoder Grand Contest 002 F. Leftmost Ball

F: Leftmost Ball - AtCoder Grand Contest 002 | AtCoder

感想

前半の考察はできたが、あとはなにも手を動かせなかった。
順序制限のある組み合わせの問題であることから、各数を頂点と見たグラフに落とし込み、そのトポロジカルソートの個数を求めることと等価であるところまで詰める考え方が、個人的におもしろかった。

解法

$\ n\ $個の$\ 0\ $と$\ k - 1\ $個の各数を並べる問題。左から見て初めて現れる数は$\ 1, 2, ..., n\ $となっているものとして、最後に$\ n!\ $をかける。$\ 0\ $が出現するたびに、並べることができる数が増加する。

editorialにある図を参考にして適当にdpすると答えが出る。「$\ B\ $の左側には必ず$\ A\ $が無ければならない」などというような制限のもとで順列を考えるときにはこのように考えるのが有効なのだろう(それはそう)。

組み合わせについては、最大$\ n * k\ $くらいまで大きくなるので、いつもの組み合わせのやつ(?)が使えないので、あらかじめfactinvfactを求めておく方法をとる。invfactについては、$\ \cfrac {1} {x !} = \cfrac {1} {(x + 1)!} * (x + 1)\ $なので、大きい方から再帰的に求めらる。

組み合わせのライブラリがまた長くなった。。。

実装
#include "bits/stdc++.h"
using namespace std;

static const int MOD = 1000000007;

long long inv(long long a) {
        long long res = 1;
        long long n = MOD - 2;
        while (n > 0) {
                if (n & 1) res = res * a % MOD;
                a = a * a % MOD;
                n >>= 1;
        }
        return res;
}

long long fact[4040404];
long long invfact[4040404];

void init() {
        fact[0] = 1;
        for (int i = 1; i < 4040404; i ++) fact[i] = (fact[i - 1] * i) % MOD;
        invfact[4040403] = inv(fact[4040403]);
        for (int i = 4040402; i >= 0; i --) invfact[i] = (invfact[i + 1] * (i + 1)) % MOD;
}

long long nCr(long long n, long long r) {
        if (n < r) return 0;
        if (n - r < r) r = n - r;
        return fact[n] * invfact[n - r] % MOD * invfact[r] % MOD;
}

long long dp[2020][2020];

void solve() {
        init();
        int n, k;
        cin >> n >> k;
        if (k == 1) {
                cout << 1 << endl;
                return;
        }
        memset(dp, 0, sizeof dp);
        dp[0][1] = 1LL;
        for (int i = 0; i <= n; i ++) {
                for (int j = i; j <= n; j ++) {
                        if (i != 0) dp[i][j] = dp[i - 1][j]; 
                        if (i != j) {
                                long long a = nCr(i + j * (k - 1) - 1, k - 2);
                                dp[i][j] = (dp[i][j] + dp[i][j - 1] * a % MOD) % MOD;
                        }
                }
        }
        cout << dp[n][n] * fact[n] % MOD << endl;
        return;
}

int main() {
        ios_base::sync_with_stdio(false);
        cin.tie(0);
        solve();
        return 0;
}

Atcoder Grand Contest 012 D. Colorful Balls

Atcoder Grand Contest 012 D. Colorful Balls

感想

前半の考察はできたのに、ほとんど同じの後半の発想がなぜかできなかった。

解法

まずすべての色が等しければ、答えは$\ 1\ $となる。以下は2種類以上の色があるものとする。

操作1では色の配置を変えることができないので、この操作の役割というのはできるだけ操作2ができるような状態にもっていくことである。操作2をするときには、常に操作1によって、その2つのボールの重さをできるだけ小さくなるようにしておくのが最適である。このように考えると結局、すべてのボールについて、そのボールと同じ色であって、かつ交換可能なボールの中で重さの最小値をとって、それをそのボールの重さとしてしまって良い。するとあとは操作2のみを考えればよい。

以下、上の操作によって変化した重さで考える。重さが最も小さいボールに注目すると、このボールと色が異なっていて、かつこのボールと交換可能ではないボールは、他のどのボールとも交換することができない。逆に、このボールと色が異なっていて、交換可能であるならば、それらのボールは、すべて互いに交換可能である。それは最小のボールを仲介にして、スワップを3回することによって、他のボールの位置を全く変えずに任意の2個をスワップできるからである。これらの並び順は重複を含む順列なので簡単に計算できる。

上の重さが最も小さいボールと同じ色のボールに対してはどう考えればよいだろうか?それはやはり上のボールとは異なる色の中で、重さが最小のものをとってくることで、同様に考えることができる。

この2つのボールがもし交換不可能であるならば、どの2つのボールも交換不可能であるので、答えは$\ 1\ $である。交換可能であるならば、これらの和集合の任意の2つは交換可能ということになる。

実装
#include "bits/stdc++.h"
using namespace std;

#define all(x)  x.begin(), x.end()
#define mp      make_pair
#define pll     pair<long long, long long>

static const long long INFL = 0x3f3f3f3f3f3f3f3fLL;
static const int INF = 0x3f3f3f3f;
static const int MOD = 1000000007;

struct UnionFind {
        int n;
        vector<int> parent;
        vector<int> rank;
        vector<int> num;
        int find(int x) {
                if (parent[x] == x) return  x;
                return parent[x] = find(parent[x]);
        }
        UnionFind(int n_) {
                n = n_;
                parent.resize(n);
                for (int i = 0; i < n; i ++) parent[i] = i;
                rank.assign(n, 0);
                num.assign(n, 1);
        }
        void unite(int x, int y) {
                if ((x = find(x)) != (y = find(y))) {
                        if (rank[x] < rank[y]) {
                                parent[x] = y;
                                num[y] += num[x];
                        } else {
                                parent[y] = x;
                                if (rank[x] == rank[y]) rank[x] ++;
                                num[x] += num[y];
                        }
                        n --;
                }
        }
        bool same(int x, int y) { return find(x) == find(y); }
        int get() { return n; }
        int get(int x) { return num[find(x)]; }
};

long long inv(long long a) {
        long long res = 1;
        long long n = MOD - 2;
        while (n > 0) {
                if (n & 1) res = res * a % MOD;
                a = a * a % MOD;
                n >>= 1;
        }
        return res;
}
long long fact[202020];

void init() {
        fact[0] = 1;
        for (int i = 1; i < 202020; i ++) fact[i] = fact[i - 1] * i % MOD;
}

void solve() {
        init();
        long long n, x, y;
        cin >> n >> x >> y;
        vector<vector<pll>> color(200000);
        for (int i = 0; i < n; i ++) {
                long long c, w;
                cin >> c >> w;
                color[c - 1].emplace_back(i, w);
        }
        int cnt = 0;
        for (int i = 0; i < n; i++) if (color[i].size() > 0) cnt ++;
        if (cnt == 1) {
                cout << 1 << endl;
                return;
        }
        vector<pll> ball(n);
        for (int i = 0; i < 200000; i ++) if (!color[i].empty()) {
                long long minwei = INFL;
                for (int j = 0; j < color[i].size(); j ++) minwei = min(minwei, color[i][j].second);
                for (int j = 0; j < color[i].size(); j ++) {
                        ball[color[i][j].first] = mp(i, (minwei + color[i][j].second <= x ? minwei : color[i][j].second));
                }
        }       
        int mi1 = INF, idx1, mi2 = INF, idx2;
        for (int i = 0; i < n; i ++) {
                if (ball[i].second < mi1) {
                        mi1 = ball[i].second;
                        idx1 = i;
                }
        }
        for (int i = 0; i < n; i ++) {
                if (ball[i].first != ball[idx1].first && ball[i].second < mi2) {
                        mi2 = ball[i].second;
                        idx2 = i;
                }
        }
        UnionFind uf(n);
        for (int i = 0; i < n; i ++) {
                if (ball[i].second + ball[idx1].second <= y && ball[i].first != ball[idx1].first) uf.unite(i, idx1);
                if (ball[i].second + ball[idx2].second <= y && ball[i].first != ball[idx2].first) uf.unite(i, idx2);
        }
        if (!uf.same(idx1, idx2)) {
                cout << 1 << endl;
        } else {
                int all = uf.get(idx1);
                map<int, int> color_cnt;
                for (int i = 0; i < n; i ++) if (uf.same(i, idx1)) color_cnt[ball[i].first] ++;
                long long ans = fact[all];
                for (auto c : color_cnt) ans = ans * inv(fact[c.second]) % MOD;
                cout << ans % MOD << endl;
        }
        return;
}

int main() {
        ios_base::sync_with_stdio(false);
        cin.tie(0);
        solve();
        return 0;
}

CS Academy 46 Div. 1.5 C. Set Subtraction

CS Academy 46 Div. 1.5 C. Set Subtraction

CS Academy

感想

ちょっと応用できそう。

解法

まず数列はソートしておく。そして$\ X\ $について全探索する。全探索といっても$\ X \leq A_{n - 1}\ $ですべて試していると間に合わないので、$\ X\ $の候補としてありうるもの、すなわち$\ A_{n - 1} - A_i (i = 0, 1, ..., n - 2)\ $だけをチェックすれば良い。重複をなくせるようにsetにいれた。

$\ X\ $を固定すると、ある数$\ a\ $に対して、そのペアとなる数が$\ a + X\ $と定まる。よってあらかじめすべての数の出現回数をmapなどで数えておいて、小さい数から順に$\ A_i\ $と$\ A_i + X\ $の回数を$\ 1\ $ずつ減らしながら見ていって、すべてうまくマッチングできるかを考えれば良い。$\ O(n ^ 2)\ $。

実装
#include "bits/stdc++.h"
using namespace std;

#define all(x)  x.begin(), x.end()

int main() {
        int n;
        cin >> n;
        vector<int> a(2 * n);
        for (int i = 0; i < 2 * n; i ++) cin >> a[i];
        sort(all(a));
        map<int, int> cnt;
        for (int i = 0; i < 2 * n; i ++) cnt[a[i]] ++;
        set<int> x;
        for (int i = 0; i < 2 * n - 1; i ++) x.insert(a.back() - a[i]);
        for (auto X : x) {
                map<int, int> tmp = cnt;
                vector<int> ans;
                for (int i = 0; i < 2 * n; i ++) {
                        if (tmp[a[i]] == 0) continue;
                        tmp[a[i]] --;
                        if (tmp[a[i] + X] == 0) goto next;
                        tmp[a[i] + X] --;
                        ans.push_back(a[i] + X);
                }
                cout << X << endl;
                for (int i = 0; i < ans.size(); i ++) cout << ans[i] << (i == ans.size() - 1 ? '\n' : ' ');
                return 0;
                next:;
        }
        cout << -1 << endl;
        return 0;
}

Atcoder Grand Contest 008 F. Black Radius

Atcoder Grand Contest 008 F. Black Radius

F: Black Radius - AtCoder Grand Contest 008 | AtCoder

感想

こちらのei1333さんの記事†全方位木DP†について - ei1333の日記で全方位木dpの概念を学んだところだったので、そこまで苦労しなかった。わかりやすい記事をありがとうございます。

解法

まず重複しないようにすべての配色を数えるために、各頂点について、それが中心になるような配色としてありえるものを数えるという方針をとる。これを辺についても同じように考える。これらの頂点や辺が異なれば、必ずその配色も異なることは明らかである。

まず頂点を$\ v\ $に固定して考える。もしこの点がお気に入りの点であるならば、その半径$\ r\ $とすると、$\ 0 \leq r \leq d_1\ $の範囲で連続的に$\ r\ $を動かしていくことができる。そしてこれらは明らかに異なる配色になる。この上限$\ d_1\ $というのは、絵を書いてみればわかるように、$\ v\ $が中心になるようにするためには、$\ v\ $からのびる部分木の中で、深さが2番目に大きいものでなければいけない。 

この点がお気に入りの点でない場合は、その半径を$\ r\ $とすると、$\ d_2 \leq r \leq d_1\ $の範囲で連続的に変化させることができる。ただし、$\ d_1\ $は上と同じである。一方下限の方は、まずその色を塗るためのお気に入りの点が含まれている部分木がある必要がある。その頂点から、$\ v\ $を通り越して別の部分木に同じだけの$\ r\ $の範囲を塗るものでなければいけないので、その部分木というのは十分深さの小さいものが好ましい。お気に入りの点を含む部分木の中で、深さが最小のもののその深さを$\ d\ $とすると、その部分木内はすべて黒に塗り尽くしてさらに$\ v\ $を通り越して$\ r\ $だけ塗ることになるのだが、結局この$\ r\ $というのは$\ d\ $に一致しているので、この$\ d\ $が下限$\ d_2\ $である。

次に辺が中心になる場合を考える。少し考察すれば、ある辺が中心になるような配色というのは高々1個しかない。なぜなら、その辺が接続する頂点を$\ u, v\ $として、$\ u, v\ $からそれぞれの部分木を同時に塗っていくとき、そのどちらか一方が塗り終わるまでは明らかにどの頂点を選んでもうまく塗ることができない。そして一方が塗り終わったその時に限り、その辺が中心になるようなバランスを崩すことなく、その塗り終えた部分木の中からある頂点を選んでそこから上手く塗ることができる。よってこのようなことができるどうかの判定は、$\ u, v\ $を根とする部分木のうち深さが小さい方にお気に入りの点が含まれているかどうかを見るだけで良い。

実装は、まず1回目のdfs1では、$\ 0\ $を根とする根付き木について、各部分木の最大の深さfarとその部分木にお気に入りの点が含まれているかどうかのin_favを順に求めておく。

次に、2回目のdfs2をする。親の自分を除く部分木についての最大の深さと、親と自分以外の部分木の中にお気に入りの点が存在するかどうか、という情報を伝播させている。

そのような部分木をchildrenにいれ、その中でもお気に入りの点を含むような部分木を特にfav_childrenにいれる。そしてchildrenについてはその中で2番目に大きいものを記録し、fav_childrenについては最も浅いものを記録する。

辺に関する探索は各頂点から次の頂点に移動する、その直前にちょうど必要な情報が揃っているので、それでぱぱっと答えに足しておく。

実装自体は書いてみたあとでは意外と単純なことに気がつく。全方位木dpについて注意することは、とにかく「次に探索しようとする部分木の情報(自分自身の情報)」が入らないようにして伝播させること。そして根の次数が$\ 1\ $である場合などにうまく適切な値を伝播させることができるように、最初に適切な初期値をchildrenなどの中にいれておくこと。

実装
#include "bits/stdc++.h"
using namespace std;
 
#define all(x)  x.begin(), x.end()
#define mp      make_pair
#define pii     pair<int, int>
 
int n;
vector<int> g[202020];
bool fav[202020];
int far[202020];
int second_farthest[202020];
int closest[202020];
bool in_fav[202020];
long long ans = 0;
 
static const int INF = 0x3f3f3f3f;
 
void dfs1(int v, int prev) {
        if (fav[v]) in_fav[v] = true;
        for (auto u : g[v]) if (u != prev) {
                dfs1(u, v);
                in_fav[v] |= in_fav[u];
                far[v] = max(far[v], far[u] + 1);
        }
}
 
void dfs2(int v, int ma, bool par_fav, int prev) {
        vector<pair<pii, bool>> children;
        children.push_back(mp(mp(0, -1), false));
        for (auto u : g[v]) {
                if (u == prev) children.push_back(mp(mp(ma + 1, u), par_fav));
                else children.push_back(mp(mp(far[u] + 1, u), in_fav[u]));
        }
        vector<pii> fav_children;
        for (auto c : children) if (c.second) fav_children.push_back(mp(c.first.first, c.first.second));
        sort(all(fav_children));
        if (fav_children.empty()) closest[v] = INF;
        else closest[v] = fav_children[0].first;
        sort(all(children), greater<pair<pii, bool>>());
        second_farthest[v] = children[1].first.first;
        for (auto u : g[v]) if (u != prev) { 
                int maa = children[u == children[0].first.second ? 1 : 0].first.first;
                bool par_f = fav[v] || par_fav;
                if (!in_fav[u]) par_f |= !fav_children.empty();
                else par_f |= fav_children.size() > 1;
                ans += (maa < far[u] && par_f) || (maa > far[u] && in_fav[u]) || (maa == far[u] && (par_f || in_fav[u]));
                dfs2(u, maa, par_f, v);
        }
}
 
int main() {
        cin >> n;
        for (int i = 0; i < n - 1; i ++) {
                int a, b;
                cin >> a >> b;
                a --, b --;
                g[a].push_back(b);
                g[b].push_back(a);
        }
        string s;
        cin >> s;                                            
        for (int i = 0; i < n; i ++) fav[i] = s[i] == '1' ? true : false;
        dfs1(0, -1);
        dfs2(0, 0, fav[0], -1);
        for (int i = 0; i < n; i ++) {
                if (fav[i]) ans += 1 + second_farthest[i];
                else ans += max(0, 1 + (second_farthest[i] - closest[i]));
        }
        cout << ans << endl;
        return 0;
}

Atcoder Grand Contest 017 E. Jigsaw

Atcoder Grand Contest 017 E. Jigsaw

E: Jigsaw - AtCoder Grand Contest 017 | AtCoder

感想

新しい感じのdfsをした。

解法

まずある右(左)の形状に対して、対応する左(右)の形状が一意に定まることに注意する。このうまくフィットする形状同士を同一の値(形状が変わる高さ)で管理する。ただし、左右のどちらの形状で何回現れたのかは記録しておく。同じブロックの左右の形状についてその値同士で辺を張っておく。

さて、まず、ある形状の値について床につかないようなパーツの方が多くなっていればこの時点で構成不可能である。逆に、床につくパーツの方が多い分には全く問題ない。なぜなら、そのようなパーツは端っことして使えるからである。この問題では完成したブロックの連結成分が1個でなくてもよいことに注意すること。

次に、この接合部分に関する(各個別の部分、ではなく)dfsをする。言い換えると、すべての同一形状の接合部分は一気に探索する。そして、逐一その個数に関するチェックをし、端っこのパーツをうまく決めれるかどうかをみる。

説明が全然できてない感じがするけど...

実装
#include "bits/stdc++.h"
using namespace std;

vector<int> g[505];
int l_cnt[505], r_cnt[505];
bool used[505];

int print(bool ok) {
        if (ok) cout << "YES" << endl;
        else cout << "NO" << endl;
        return 0;
}

bool dfs(int v) {
        used[v] = true;
        bool res = l_cnt[v] != r_cnt[v];
        for (auto u : g[v]) if (!used[u]) res |= dfs(u);
        return res;
}

int main() {      
        int n, h, a, b, c, d;
        cin >> n >> h;
        for (int i = 0; i < n; i ++) {
                cin >> a >> b >> c >> d;
                int lh = (c == 0 ? a : c + 250);
                int rh = (d == 0 ? b + 250 : d);
                l_cnt[lh] ++;
                r_cnt[rh] ++;
                g[lh].push_back(rh);
                g[rh].push_back(lh);
        }
        for (int i = 0; i < h + 1; i ++) if (r_cnt[i] > l_cnt[i]) return print(0);
        for (int i = 251; i < h + 251; i ++) if (l_cnt[i] > r_cnt[i]) return print(0);
        for (int i = 0; i < 501; i ++) if (!used[i]) if (!g[i].empty()) if (!dfs(i)) return print(0);
        return print(1);
}