Submission #373089

#	Time	Username	Problem	Language	Result	Execution time	Memory
373089		Kevin_Zhang_TW	Port Facility (JOI17_port_facility)	C++17	22 / 100	29 ms	2412 KiB

port_facility

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T> void debug(T L, T R) { while (L != R) cerr << *L << " \n"[next(L) == R], ++L; }
#else
#define DE(...) 0
#define debug(...) 0
#endif
 
const int MAX_N = 300010, p = 1e9 + 7;
 
int n;
pair<int,int> sh[MAX_N];
 
bool valid (int i, int j) {
	if (i > j) swap(i, j);
	return sh[i].second < sh[j].first || sh[j].second < sh[i].second;
}
bool vis[MAX_N];
 
ll trykill(int x) {
	vector<int> gp[2];
	queue<pair<int,int>> q;
	q.emplace(x, 0);
	while (q.size()) {
		auto [x, g] = q.front(); q.pop();
		for (int u : gp[g])
			if (!valid(x, u)) return 0;
		gp[g].pb(x);

		for (int i = 0;i < n;++i) 
			if (!vis[i] && !valid(i, x)) {
				vis[i] = true;
				q.emplace(i, g^1);
			}
	}
	return 2;
}
int32_t main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin >> n;
	for (int i = 0;i < n;++i) 
		cin >> sh[i].first >> sh[i].second;
	sort(sh, sh + n);
 
	if (n > 2000) return -1;
 
	ll res = 1;
 
 
	for (int i = 0;i < n;++i) if (!vis[i]) {
		vis[i] = true;
		res = res * trykill(i) % p;
	}
 
	cout << res << '\n';
}

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