Submission #213192

#	Time	Username	Problem	Language	Result	Execution time	Memory
213192		patrikpavic2	Port Facility (JOI17_port_facility)	C++17	22 / 100	6101 ms	58616 KiB

port_facility

#include <cstdio>
#include <algorithm>
#include <vector>

#define PB push_back
#define X first
#define Y second

using namespace std;

typedef pair < int, int > pii;

const int N = 1e6 + 500;
const int MOD = 1e9 + 7;

vector < pii > v[N];
int col[N], bio[N], mog = 1, n;
int L[N], R[N], id[2 * N], str[N];

void dodaj(int x,int y,int razl = 1){
	v[x].PB({y, razl});
	v[y].PB({x, razl});
}

void dfs(int x){
	if(bio[x]) return;
	bio[x] = 1;
	for(pii nxt : v[x]){
		if(bio[nxt.X] && (col[x] ^ col[nxt.X]) != nxt.Y)
			mog = 0;
		if(!bio[nxt.X]){
			col[nxt.X] = col[x] ^ nxt.Y;
			dfs(nxt.X);
		}
	}
}


int main(){
	scanf("%d", &n);
	for(int i = 1;i <= n;i++){
		scanf("%d%d", L + i, R + i);
		id[L[i]] = i, id[R[i]] = i;
		str[R[i]] = 1;
	}
	for(int i = 1;i <= n;i++){
		for(int j = 1;j <= n;j++){
			if(L[i] < L[j] && R[i] < R[j] && R[i] > L[j])
				dodaj(i, j);
		}
	}
	int komp = 0;
	for(int i = 1;i <= n;i++){
		komp += !bio[i]; dfs(i);
	}
	int sol = 1;
	for(;komp--;) sol = (sol + sol) % MOD;
	printf("%d\n", sol * mog);
}

Compilation message (stderr)

port_facility.cpp: In function 'int main()':
port_facility.cpp:40:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
port_facility.cpp:42:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", L + i, R + i);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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