Submission #1282118

#	Time	Username	Problem	Language	Result	Execution time	Memory
1282118		Bui_Quoc_Cuong	Port Facility (JOI17_port_facility)	C++20	22 / 100	32 ms	16476 KiB

port_facility

#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for (int i = a; i <= (int)b; i++)
#define FORD(i, a, b) for (int i = a; i >= (int)b; i--)
#define pb push_back
#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define sz(a) (int)a.size()
#define MASK(a) (1LL<<(a))
#define BIT(mask, a) ((mask >> (a))&1)
#define mp make_pair
#define ll long long
#define vI vector <int>
#define pII pair <int, int>
#define vL vector <long long>
template <class A, class B> bool minimize (A &a, const B b) {if (a > b) {a = b;return true;} return false;}
template <class A, class B> bool maximize (A &a, const B b) {if (a < b) {a = b;return true;} return false;}
const int MAXN = 2e5 + 5;
const int MOD = 1e9 + 7;

void add (int &x, const int y) {
    x+= y;
    if (x >= MOD) x-= MOD;
}

int n;
pII a[MAXN];

void init (void) {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i].fi >> a[i].se;
    }
}

struct DisjointSet {
    int lab[MAXN], ssc;
    int bipartite = true;

    int find (int x) {
        return lab[x] < 0 ? x : lab[x] = find(lab[x]);
    }

    bool joint (int u, int v) {
        int x = find(u), y = find(v);
        if (x == y) return false;
        if (lab[x] > lab[y]) swap (x, y);
        lab[x]+= lab[y];
        lab[y] = x;
        ssc--;
        return true;
    }

    void addNode (int u, int v) {
        joint (u, v + n);
        joint (v, u + n);
        if (find(u) == find(u + n)) {
            bipartite = false;
        }
        if (find(v) == find(v + n)) {
            bipartite = false;
        }
    }
} DSU;

namespace sub2 {
    vector <int> G[MAXN];
    int vis[MAXN];

    void dfs (int u) {
        vis[u] = 1;
        for (int &v : G[u]) if (!vis[v]) {
            dfs(v);
        }
    }

    void solve() {
        FOR(i, 1, 2 * n) {
            DSU.lab[i] = - 1;
            DSU.bipartite = true;
        }
        DSU.ssc = 2 * n;

        sort (a + 1, a + 1 + n, [&] (pII u, pII v) {
            return u.second < v.second;
        });

        FOR(i, 1, n) {
            FOR(j, 1, i - 1) {
                if ((!(a[i].first > a[j].second)) && (!(a[i].first < a[j].first))) {
                    DSU.addNode (i, j);
                    G[i].push_back(j); G[j].push_back(i);
                }
            }
        }

        if (!DSU.bipartite) {
            cout << 0;
            return;
        }

        int cnt = 0;
        FOR(i, 1, n) if (!vis[i]) {
            cnt++;
            dfs(i);
        }

        int ans = 1;
        FOR(i, 1, cnt) ans = 1LL * ans * 2 % MOD;
        cout << ans;
    }
}

void process (void) {
    if (n <= 2000) {
        return sub2::solve();
    }
}

signed main (void) {
    ios_base::sync_with_stdio(0); cin.tie(0);
    #define kieuoanh "concac"
    if (fopen(kieuoanh".inp", "r")) {
        freopen(kieuoanh".inp", "r", stdin);
        freopen(kieuoanh".out", "w", stdout);
    }
    init();
    process();
    return 0;
}

Compilation message (stderr)

port_facility.cpp: In function 'int main()':
port_facility.cpp:125:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  125 |         freopen(kieuoanh".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
port_facility.cpp:126:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  126 |         freopen(kieuoanh".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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