Submission #76598255

---

Source Code Expand

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

#define ll long long

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    vector<ll> l(n + 1), r(n + 1), p(n + 1), q(n + 1);

    for (int i = 1; i <= n; i++) {
        cin >> l[i] >> r[i] >> p[i] >> q[i];
    }

    vector<int> indeg(n + 1, 0);
    vector<int> leftChild(n + 1, -1), rightChild(n + 1, -1);
    vector<vector<int>> adj(n + 1);

    bool ok = true;

    for (int i = 0; i < m; i++) {
        int u, v, b;
        cin >> u >> v >> b;

        indeg[v]++;
        adj[u].push_back(v);

        if (b == 0) {
            if (leftChild[u] != -1) ok = false;
            leftChild[u] = v;
        } else {
            if (rightChild[u] != -1) ok = false;
            rightChild[u] = v;
        }

        if (!(l[u] < l[v] && r[v] < r[u])) {
            ok = false;
        }

        if (q[u] != p[v]) {
            ok = false;
        }
    }

    if (indeg[1] != 0) {
        ok = false;
    }

    for (int i = 2; i <= n; i++) {
        if (indeg[i] != 1) {
            ok = false;
        }
    }

    for (int i = 1; i <= n; i++) {
        int a = leftChild[i];
        int b = rightChild[i];

        if (a != -1 && b != -1) {
            if (!(r[a] < l[b])) {
                ok = false;
            }
        }
    }

    vector<int> vis(n + 1, 0);
    queue<int> qu;

    qu.push(1);
    vis[1] = 1;

    while (!qu.empty()) {
        int node = qu.front();
        qu.pop();

        for (auto nxt : adj[node]) {
            if (!vis[nxt]) {
                vis[nxt] = 1;
                qu.push(nxt);
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        if (!vis[i]) {
            ok = false;
        }
    }

    cout << (ok ? "YES\n" : "NO\n");

    return 0;
}

Submission Info

Judge Result