Submission #1369255

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

int p, n;
int arr[20100];
int ord[20100];
int rrd[20100];
int YES(int a) {return a*2;}
int NO(int a) {return a*2+1;}
int key = 32768;
struct twosat {
    vector<int> lis[140100];
    int lab[140100];
    int tim[140100];
    int lnk[140100];
    stack<int> st;
    int tt, ct;
    int NOT(int a) {return a^1;}
    void init() {
        int i;
        tt = ct = 0;
        for (i=0;i<4*key;i++) lnk[i] = lab[i] = tim[i] = -1;
        for (i=0;i<4*key;i++) lis[i].clear();
    }
    void add(int a, int b) {
        lis[NOT(a)].push_back(b);
        lis[NOT(b)].push_back(a);
    }
    void dfs(int here) {
        lnk[here] = tim[here] = tt++;
        st.push(here);
        int i;
        for (i=0;i<lis[here].size();i++) {
            int there = lis[here][i];
            if (tim[there]==-1) {
                dfs(there);
                lnk[here] = min(lnk[here],lnk[there]);
            }
            else if (lab[there]==-1) lnk[here] = min(lnk[here],tim[there]);
        }
        if (lnk[here]==tim[here]) {
            while(!st.empty()) {
                int t = st.top();
                lab[t] = ct;
                st.pop();
                if (t==here) break;
            }
            ct++;
        }
    }
    void scc() {
        for (int i=0;i<4*key;i++) if (tim[i]==-1) dfs(i);
    }
    bool ok() {
        scc();
        for (int i=0;i<2*key;i++) if (lab[YES(i)]==lab[NO(i)]) return false;
        return true;
    }
} ts;

void init() {
    int i;
    for (i=key-1;i>0;i--) {
        ts.add(NO(2*i),YES(i));
        ts.add(NO(2*i+1),YES(i));
    }
}

void upd(int s, int e, int idx) {
    s+=key;e+=key;idx+=key;
    while(s<=e) {
        if (s&1) ts.add(NO(idx),NO(s++));
        if (~e&1) ts.add(NO(idx),NO(e--));
        s>>=1;e>>=1;
    }
}

bool ok(int t) {
    int i, j;
    ts.init();
    for (i=0;i<n;i++) {
        ts.add(YES(rrd[i*2]+key),YES(rrd[i*2+1]+key));
        ts.add(NO(rrd[i*2]+key),NO(rrd[i*2+1]+key));
    }
    init();
    j = 1;
    for (i=0;i<2*n;i++) {
        for (j=max(j,i+1);j<2*n&&arr[ord[i]]+t>arr[ord[j]];j++);
        upd(i+1,j-1,i);
    }
    return ts.ok();
}

bool cmp(int a, int b) {return arr[a]<arr[b];}
int main() {
    int i;

    scanf("%d",&n);
    for (i=0;i<n;i++) scanf("%d%d",&arr[i*2],&arr[i*2+1]);
    for (i=0;i<2*n;i++) ord[i] = i;
    sort(ord,ord+2*n,cmp);
    for (i=0;i<2*n;i++) rrd[ord[i]] = i;
    int s = 0, e = 1e9+1;

    while(s<=e) {
        int d = (s+e)>>1;
        if (ok(d)) s = d+1;
        else e = d-1;
    }

    printf("%d\n",e);

    return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:99:19: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
                   ^
./Main.cpp:100:58: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     for (i=0;i<n;i++) scanf("%d%d",&arr[i*2],&arr[i*2+1]);
                                                          ^

Judge Result