Submission #27819

#	Time	Username	Problem	Language	Result	Execution time	Memory
27819		tlwpdus	Port Facility (JOI17_port_facility)	C++11	100 / 100	1443 ms	103448 KiB

port_facility

// N^2

#include <bits/stdc++.h>
#define x first
#define y second

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;

map<int,int> ma;
vector<int> lis[1000100];

int n;
ll MOD = 1000000007, res = 1;
pii arr[1000100];
int par[2000100], chk[2000100];

int fin(int a) {return par[a] = ((par[a]==a)?a:fin(par[a]));}
void uni(int a, int b) {par[fin(a)]=fin(b);}

void good(int a, int b) {uni(a,b);uni(a+n,b+n);}
void bad(int a, int b) {uni(a,b+n);uni(a+n,b);}

int main() {
    int i;

    scanf("%d",&n);
    for (i=0;i<n;i++) {
		scanf("%d%d",&arr[i].x,&arr[i].y);
    }
    for (i=0;i<2*n;i++) par[i] = i;
    sort(arr,arr+n);
    for (i=0;i<n;i++) {
		auto it = ma.lower_bound(arr[i].x), ed = ma.lower_bound(arr[i].y);
		while(it!=ed) {
			auto pit = --ed; ++ed;
			bad(i,it->second);
			if (fin(it->second)==fin(pit->second)) break;
			it++;
		}
		if (fin(i)==fin(i+n)) {
			printf("0\n");
			return 0;
		}
		ma[arr[i].y] = i;
    }
    for (i=0;i<n;i++) {
		if (fin(i)==fin(i+n)) res = 0;
		else chk[fin(i)] = chk[fin(i+n)] = 1;
    }
    for (i=0;i<n;i++) if (chk[i]) res = res*2%MOD;
    printf("%lld\n",res);

    return 0;
}

Compilation message (stderr)

port_facility.cpp: In function 'int main()':
port_facility.cpp:29:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
                   ^
port_facility.cpp:31:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&arr[i].x,&arr[i].y);
                                    ^

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