Submission #402665

#	Time	Username	Problem	Language	Result	Execution time	Memory
402665		maximath_1	Port Facility (JOI17_port_facility)	C++11	100 / 100	1485 ms	85448 KiB

port_facility

#include <bits/stdc++.h>

#define kyou using
#define mo namespace
#define kawaii std

kyou mo kawaii; // hi honey~

#define ll long long
#define ld long double
#define endl "\n"
const int MX = 1000005;
const int LG = 5;
const int BLOCK = 205;
const int inf = 1000000069;
const ll inf_ll = 4000000000000000069ll;
const ll mod = 1e9 + 7;
const int dxh[] = {1, 1, -1, -1, 2, 2, -2, -2};
const int dyh[] = {2, -2, 2, -2, 1, -1, 1, -1}; // horse
const int dx[] = {0, 1, 0, -1, 0, 0};
const int dy[] = {1, 0, -1, 0, 0, 0}; // adj
const int dz[] = {0, 0, 0, 0, 1, -1}; // 3d
const int dxd[] = {1, 1, 1, 0, -1, -1, -1, 0};
const int dyd[] = {1, 0, -1, -1, -1, 0, 1, 1}; // diag

bool untied = 0;
void setIn(string s){freopen(s.c_str(), "r", stdin);}
void setOut(string s){freopen(s.c_str(), "w", stdout);}
void unsyncIO(){cin.tie(0) -> sync_with_stdio(0);}
void setIO(string s = ""){
	if(!untied) unsyncIO(), untied = 1;
	if(s.size()){
		setIn(s + ".in");
		setOut(s + "_output.out");
	}
}

int n;
vector<pair<int, int> > v;
int par[MX * 2], used[MX * 2];
map<int, int> mp;

int find(int x){
	if(par[x] < 0) return x;
	return par[x] = find(par[x]);
}

void uni(int x, int y){
	if((x = find(x)) == (y = find(y))) return;
	if(par[x] > par[y]) swap(x, y);
	par[x] += par[y];
	par[y] = x;
}

int main(){
	setIO();

	cin >> n;
	v.resize(n);
	for(int i = 0; i < n; i ++){
		cin >> v[i].first >> v[i].second;
		par[i] = par[i + n] = -1;
	}

	sort(v.begin(), v.end());

	for(int i = 0; i < n; i ++){
		for(auto itL = mp.lower_bound(v[i].first), itR = mp.lower_bound(v[i].second); itL != itR; itL ++, itR ++){
			uni(i, (itL -> second) + n);
			uni(i + n, (itL -> second));
			if(find((-- itR) -> second) == find(itL -> second)) break;
		}

		mp[v[i].second] = i;
	}

	int ans = 1;
	for(int i = 0; i < n; i ++){
		if(find(i) == find(i + n)) ans = 0;
		else used[find(i)] = used[find(i + n)] = 1;
	}

	for(int i = 0; i < n; i ++)
		if(used[i]) (ans += ans) %= mod;
	cout << ans << endl;
	return 0;
}

Compilation message (stderr)

port_facility.cpp: In function 'void setIn(std::string)':
port_facility.cpp:27:29: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 | void setIn(string s){freopen(s.c_str(), "r", stdin);}
      |                      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
port_facility.cpp: In function 'void setOut(std::string)':
port_facility.cpp:28:30: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 | void setOut(string s){freopen(s.c_str(), "w", stdout);}
      |                       ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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