Submission #197487

#	Time	Username	Problem	Language	Result	Execution time	Memory
197487		dennisstar	Port Facility (JOI17_port_facility)	C++17	100 / 100	2502 ms	80268 KiB

port_facility

#include <bits/stdc++.h>
#define fi first
#define se second
#define eb emplace_back
#define all(V) (V).begin(), (V).end()
using namespace std;
typedef long long ll;
typedef vector<int> vim;
typedef pair<int, int> pii;

const ll MOD=1e9+7;
int N; ll ans=1; vector<pii> V; set<pii> S;

vim par;
int get(int x) { return par[x]==-1?x:par[x]=get(par[x]); }
void Union(int x, int y) { x=get(x), y=get(y); if (x!=y) par[y]=x; }

int main() {
	scanf("%d", &N); V.resize(N); par.resize(2*N); fill(all(par), -1);
	for (auto &i:V) scanf("%d %d", &i.fi, &i.se);
	sort(all(V));
	for (int i=0; i<N; i++) {
		auto s=S.lower_bound(pii(V[i].fi, 0)), e=S.upper_bound(pii(V[i].se, (1<<30)));
		if (e!=S.begin()) for (; s!=e; ++s) {
			Union(i, s->se+N);
			Union(i+N, s->se);
			if (get(s->se)==get(prev(e)->se)) break;
		}
		S.emplace(V[i].se, i);
	}
	for (int i=0; i<N; i++) if (get(i)==get(i+N)) { puts("0"); return 0; }
	for (int i=0; i<N; i++) if (get(i)==i) ans=ans*2%MOD;
	printf("%lld\n", ans);
	return 0;
}

Compilation message (stderr)

port_facility.cpp: In function 'int main()':
port_facility.cpp:19:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N); V.resize(N); par.resize(2*N); fill(all(par), -1);
  ~~~~~^~~~~~~~~~
port_facility.cpp:20:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (auto &i:V) scanf("%d %d", &i.fi, &i.se);
                  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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