Submission #1414474

---

Source Code Expand

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define fore(i,a) for(auto &i:a)
#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
//---------------------------------------------------------------------------------------------------
/*---------------------------------------------------------------------------------------------------
　　　　　　　　　　　 ∧＿∧  
　　　　　 ∧＿∧ 　（´<_｀ ）　 Welcome to My Coding Space!
　　　　 （ ´_ゝ`）　/　 ⌒i     
　　　　／　　　＼　 　  |　|     
　　　 /　　 /￣￣￣￣/　　|  
　 ＿_(__ﾆつ/　    ＿/ .| .|＿＿＿＿  
　 　　　＼/＿＿＿＿/　（u　⊃  
---------------------------------------------------------------------------------------------------*/
 
 


#define NO "NO"
#define YES "YES"
int N, H;
int L[101010], R[101010];
int in[505], ou[505];
int used[505];
//---------------------------------------------------------------------------------------------------
vector<int> E[505];
int vis[505];
void dfs(int cu) {
    vis[cu] = 1;
    fore(to, E[cu]) if(!vis[to]) {
        dfs(to);
    }
}
//---------------------------------------------------------------------------------------------------
string solve() {
    cin >> N >> H;

    // make_edge
    rep(i, 0, N) {
        int a, b, c, d; cin >> a >> b >> c >> d;

        int l;
        if (0 < c) l = -c;
        else l = a;

        int r;
        if (0 < d) r = d;
        else r = -b;

        l += 250, r += 250;

        L[i] = l, R[i] = r;
    }

    // in/out check
    rep(i, 0, N) {
        int l = L[i], r = R[i];
        ou[l]++; in[r]++;
    }
    rep(i, 0, 505) {
        int x = i - 250;
        if (0 < x) if (ou[i] < in[i]) return NO;
        if (x < 0) if (in[i] < ou[i]) return NO;
    }

    // cycle check
    rep(i, 0, N) {
        int l = L[i], r = R[i];
        used[l] = used[r] = 1;
        E[l].push_back(r);
    }

    rep(i, 0, 505) {
        int x = i - 250;
        if (0 < x) if (ou[i] > in[i]) if (!vis[i]) dfs(i);
    }
    rep(i, 0, 505) if (used[i]) if (!vis[i]) return NO;

    return YES;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cout << solve() << endl;
}

Submission Info

Judge Result