Submission #110183

#	Time	Username	Problem	Language	Result	Execution time	Memory
110183		tincamatei	Port Facility (JOI17_port_facility)	C++14	100 / 100	3847 ms	144760 KiB

port_facility

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1000000;
const int MOD = 1000000007;
int ev[1+2*MAX_N];
int first[1+MAX_N], last[1+MAX_N];

vector<int> graph[1+MAX_N];
int color[1+MAX_N];
bool bipartite = true;

void dfs(int nod, int c = 1) {
	color[nod] = c;
	for(auto it: graph[nod])
		if(color[it] == 0)
			dfs(it, 3 - c);
		else if(color[it] + color[nod] != 3)
			bipartite = false;
}

int main() {
#ifdef HOME
	FILE *fin = fopen("input.in", "r");
	FILE *fout = fopen("output.out", "w");
#else
	FILE *fin = stdin;
	FILE *fout = stdout;
#endif

	int n, rez = 1;
	
	fscanf(fin, "%d", &n);

	for(int i = 1; i <= n; ++i) {
		fscanf(fin, "%d%d", &first[i], &last[i]);
		ev[first[i]] = i;
		ev[last[i]] = -i;
	}

	set<pair<int, int> > heads;
	for(int i = 1; i <= 2 * n; ++i) {
		if(ev[i] > 0)
			heads.insert(make_pair(i, ev[i]));
		else {
			ev[i] = -ev[i];

			set<pair<int, int> >::iterator it;
			it = heads.upper_bound(make_pair(first[ev[i]], ev[i]));

			int rightest = -1;
			while(it != heads.end()) {
				graph[it->second].push_back(ev[i]);
				graph[ev[i]].push_back(it->second);
				if(rightest == -1 || (rightest != -1 && last[it->second] > last[rightest]))
					rightest = it->second;
				it = heads.erase(it);
			}
			
			if(rightest != -1)
				heads.insert(make_pair(first[rightest], rightest));
			heads.erase(make_pair(first[ev[i]], ev[i]));
		}
	}

	for(int i = 1; i <= n; ++i)
		if(color[i] == 0) {
			dfs(i);
			rez = rez * 2 % MOD;
		}
	
	if(!bipartite)
		rez = 0;

	set<int> c[2];
	for(int i = 1; i <= 2 * n; ++i) {
		if(first[ev[i]] == i)
			c[color[ev[i]] - 1].insert(i);
		else {
			if(c[color[ev[i]] - 1].upper_bound(first[ev[i]]) != c[color[ev[i]] - 1].end())
				rez = 0;
			c[color[ev[i]] - 1].erase(first[ev[i]]);
		}
	}

	fprintf(fout, "%d", rez);

	fclose(fin);
	fclose(fout);
	return 0;
}

Compilation message (stderr)

port_facility.cpp: In function 'int main()':
port_facility.cpp:34:8: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  fscanf(fin, "%d", &n);
  ~~~~~~^~~~~~~~~~~~~~~
port_facility.cpp:37:9: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   fscanf(fin, "%d%d", &first[i], &last[i]);
   ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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