Submission #314324

#	Time	Username	Problem	Language	Result	Execution time	Memory
314324		limabeans	Port Facility (JOI17_port_facility)	C++17	22 / 100	6086 ms	43896 KiB

port_facility

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

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl





using ll = long long;

const ll mod = 1e9+7;
const int maxn = 1e6 + 5;


int n;
int a[maxn], b[maxn];
vector<int> g[maxn];


void add_edge(int u, int v) {
    g[u].push_back(v);
    g[v].push_back(u);
}


bool isect(int u, int v, int x, int y) {
    if (u>x) {
	swap(u,x);
	swap(v,y);
    }


    assert(u<x);
    // u.....v
    //    x.....y

    return x<v && v<y;


    // u........v
    //    x...y

    
    //u...v
    //      x..y

}


int color[maxn];


bool dfs(int at) {
    for (int to: g[at]) {
	if (color[to]==-1) {
	    color[to]=1^color[at];
	    if (!dfs(to)) return false;
	} else if (color[to]==color[at]) {
	    return false;
	}
    }
    return true;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);

    cin>>n;
    for (int i=1; i<=n; i++) {
	cin>>a[i]>>b[i];
    }


    for (int i=1; i<=n; i++) {
	for (int j=i+1; j<=n; j++) {
	    if (isect(a[i],b[i],a[j],b[j])) {
		add_edge(i,j);
	    }
	}
    }

    // for (int i=1; i<=n; i++) {
    // 	watch(i);
    // 	for (int j: g[i]) cout<<j<<" ";
    // 	cout<<endl;
    // }

    memset(color,-1,sizeof(color));

    ll res=1;
    for (int i=1; i<=n; i++) {
	if (color[i]==-1) {
	    color[i]=0;
	    if (!dfs(i)) out(0);
	    res=res*2%mod;
	}
    }

    cout<<res<<endl;
    
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 12 / 12
• Subtask 3: 0 / 56
• Subtask 4: 0 / 22