Submission #413426

#	Time	Username	Problem	Language	Result	Execution time	Memory
413426		Aryan_Raina	Port Facility (JOI17_port_facility)	C++17	22 / 100	6008 ms	32488 KiB

port_facility

#include <bits/stdc++.h>
using namespace std;

#define int int64_t
#define ld long double
#define ar array
 
const int INF = 1e12;
const int MOD = 1e9+7;

void solve() {
    int N; cin >> N;
    vector<ar<int,2>> A(N);
    for (auto &i : A) cin >> i[0] >> i[1];
    vector<int> g[N];
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < i; j++) {
            bool inbet1 = (A[i][0] <= A[j][0] && A[j][1] <= A[i][1]);
            bool inbet2 = (A[j][0] <= A[i][0] && A[i][1] <= A[j][1]);
            if (!(inbet1 || inbet2 || A[i][1] <= A[j][0] || A[j][1] <= A[i][0])) {
                g[i].push_back(j);
                g[j].push_back(i);
            }
        }
    }
    vector<int> val(N, -1);
    function<bool(int,int)> dfs = [&](int u, int x) {
        val[u] = x;
        for (int v : g[u]) if (val[v] == -1) {
            if (!dfs(v, x^1)) return false;
        } else if (val[v]^x^1) {
            return false;
        }
        return true;
    };

    int ans = 1;
    for (int i = 0; i < N; i++) if (val[i] == -1) {
        if (dfs(i,0)) ans = (ans << 1) % MOD;
        else ans = 0;
    }

    cout << ans << '\n';
}

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
 
    int t = 1; //cin >> t;
    while (t--) solve();   
}  

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