Submission #2215243


Source Code Expand

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

#define int long long

#define rep(i,n) for(int i=0;i<(n);i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;

template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

struct UnionFindTree{
    vector<int>par,sz;
    UnionFindTree(int n){
        par.resize(n);
        sz.resize(n);
        for(int i=0;i<n;i++){
            par[i]=i;
            sz[i]=1;
        }
    }
    int find(int x){
        return x==par[x]?x:par[x]=find(par[x]);
    }
    void unite(int x,int y){
        x=find(x);y=find(y);
        if(x==y)return;
        if(sz[x]<sz[y])swap(x,y);
        sz[x]+=sz[y];
        par[y]=x;
    }
    bool areSame(int x,int y){
        return find(x)==find(y);
    }
    int size(int x){
        return sz[find(x)];
    }
};

int N,H;
int A[111111],B[111111],C[111111],D[111111];


int M=500;
int deg[1111];
bool used[1111];

signed main(){
    cin>>N>>H;
    UnionFindTree uf(1111);
    rep(i,N){
        cin>>A[i]>>B[i]>>C[i]>>D[i];

        int u,v;
        if(C[i]==0){
            u=A[i];
        }
        else{
            u=M+C[i];
        }

        if(D[i]==0){
            v=M+B[i];
        }
        else{
            v=D[i];
        }

        uf.unite(u,v);
        used[u]=used[v]=true;
        deg[u]++;
        deg[v]--;

    }



    used[2*M]=true;
    int ei=0,uku=0;
    rep(i,M){
        if(deg[i]<0){
            cout<<"NO"<<endl;
            return 0;
        }
        if(deg[i]>0){
            ei+=deg[i];
            uf.unite(2*M,i);
        }
    }

    for(int i=M;i<2*M;i++){
        if(deg[i]>0){
            cout<<"NO"<<endl;
            return 0;
        }
        if(deg[i]<0){
            uku+=-deg[i];
            uf.unite(2*M,i);
        }
    }

    if(ei!=uku){
        cout<<"NO"<<endl;
        return 0;
    }


    rep(i,1111)rep(j,1111){
        if(!used[i]||!used[j])continue;
        if(!uf.areSame(i,j)){
            cout<<"NO"<<endl;
            return 0;
        }
    }
    cout<<"YES"<<endl;
    return 0;
}

Submission Info

Submission Time
Task E - Jigsaw
User latte0119
Language C++14 (GCC 5.4.1)
Score 1200
Code Size 2353 Byte
Status AC
Exec Time 83 ms
Memory 3456 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 1200 / 1200
Status
AC × 3
AC × 84
Set Name Test Cases
Sample sample1.txt, sample2.txt, sample3.txt
All sample1.txt, sample2.txt, sample3.txt, a1.txt, a2.txt, a3.txt, b1.txt, b10.txt, b101.txt, b102.txt, b103.txt, b104.txt, b105.txt, b106.txt, b107.txt, b108.txt, b109.txt, b11.txt, b110.txt, b111.txt, b112.txt, b113.txt, b114.txt, b115.txt, b116.txt, b117.txt, b118.txt, b119.txt, b12.txt, b13.txt, b14.txt, b15.txt, b2.txt, b200.txt, b201.txt, b202.txt, b203.txt, b204.txt, b205.txt, b206.txt, b207.txt, b208.txt, b209.txt, b210.txt, b211.txt, b212.txt, b213.txt, b214.txt, b215.txt, b216.txt, b217.txt, b218.txt, b219.txt, b3.txt, b300.txt, b301.txt, b302.txt, b303.txt, b304.txt, b305.txt, b306.txt, b307.txt, b308.txt, b309.txt, b310.txt, b311.txt, b4.txt, b5.txt, b6.txt, b7.txt, b8.txt, b9.txt, c1.txt, c2.txt, c3.txt, c4.txt, c5.txt, d1.txt, d2.txt, d3.txt, d4.txt, sample1.txt, sample2.txt, sample3.txt
Case Name Status Exec Time Memory
a1.txt AC 1 ms 256 KB
a2.txt AC 9 ms 640 KB
a3.txt AC 77 ms 3456 KB
b1.txt AC 2 ms 256 KB
b10.txt AC 17 ms 896 KB
b101.txt AC 79 ms 3456 KB
b102.txt AC 77 ms 3456 KB
b103.txt AC 78 ms 3456 KB
b104.txt AC 78 ms 3456 KB
b105.txt AC 76 ms 3456 KB
b106.txt AC 34 ms 1664 KB
b107.txt AC 71 ms 3072 KB
b108.txt AC 78 ms 3456 KB
b109.txt AC 69 ms 3072 KB
b11.txt AC 53 ms 2304 KB
b110.txt AC 78 ms 3456 KB
b111.txt AC 77 ms 3456 KB
b112.txt AC 78 ms 3456 KB
b113.txt AC 78 ms 3456 KB
b114.txt AC 77 ms 3456 KB
b115.txt AC 34 ms 1664 KB
b116.txt AC 71 ms 3072 KB
b117.txt AC 79 ms 3456 KB
b118.txt AC 60 ms 2688 KB
b119.txt AC 69 ms 3072 KB
b12.txt AC 54 ms 2560 KB
b13.txt AC 78 ms 3456 KB
b14.txt AC 78 ms 3456 KB
b15.txt AC 78 ms 3456 KB
b2.txt AC 10 ms 640 KB
b200.txt AC 76 ms 3328 KB
b201.txt AC 76 ms 3328 KB
b202.txt AC 76 ms 3328 KB
b203.txt AC 76 ms 3328 KB
b204.txt AC 77 ms 3456 KB
b205.txt AC 77 ms 3328 KB
b206.txt AC 76 ms 3456 KB
b207.txt AC 76 ms 3328 KB
b208.txt AC 77 ms 3456 KB
b209.txt AC 79 ms 3328 KB
b210.txt AC 76 ms 3328 KB
b211.txt AC 77 ms 3328 KB
b212.txt AC 76 ms 3328 KB
b213.txt AC 77 ms 3328 KB
b214.txt AC 77 ms 3456 KB
b215.txt AC 76 ms 3328 KB
b216.txt AC 81 ms 3328 KB
b217.txt AC 83 ms 3456 KB
b218.txt AC 75 ms 3328 KB
b219.txt AC 76 ms 3456 KB
b3.txt AC 76 ms 3456 KB
b300.txt AC 78 ms 3456 KB
b301.txt AC 75 ms 3456 KB
b302.txt AC 52 ms 2688 KB
b303.txt AC 51 ms 2688 KB
b304.txt AC 76 ms 3456 KB
b305.txt AC 75 ms 3456 KB
b306.txt AC 55 ms 2944 KB
b307.txt AC 51 ms 2688 KB
b308.txt AC 69 ms 3328 KB
b309.txt AC 77 ms 3456 KB
b310.txt AC 65 ms 3328 KB
b311.txt AC 66 ms 3328 KB
b4.txt AC 77 ms 3456 KB
b5.txt AC 9 ms 640 KB
b6.txt AC 9 ms 640 KB
b7.txt AC 9 ms 640 KB
b8.txt AC 9 ms 640 KB
b9.txt AC 9 ms 640 KB
c1.txt AC 65 ms 3456 KB
c2.txt AC 65 ms 3456 KB
c3.txt AC 53 ms 2816 KB
c4.txt AC 65 ms 3456 KB
c5.txt AC 34 ms 1920 KB
d1.txt AC 78 ms 3456 KB
d2.txt AC 80 ms 3456 KB
d3.txt AC 78 ms 3328 KB
d4.txt AC 62 ms 2688 KB
sample1.txt AC 2 ms 256 KB
sample2.txt AC 1 ms 256 KB
sample3.txt AC 2 ms 256 KB