Submission #413418

#	Time	Username	Problem	Language	Result	Execution time	Memory
413418		Aryan_Raina	Port Facility (JOI17_port_facility)	C++17	0 / 100	1 ms	204 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;

struct UFDS {
    vector<int> p; int cc;
    UFDS(int n) : p(n,-1), cc(n) {}
    int fin(int v) { return p[v] < 0 ? v : p[v] = fin(p[v]); }
    bool join(int a, int b) {
        a = fin(a), b = fin(b);
        if (a == b) return false; --cc;
        if (-p[a] < -p[b]) swap(a, b);
        p[a] += p[b]; p[b] = a; return true;
    }
};

void solve() {
    int N; cin >> N;
    vector<ar<int,2>> A(N);
    for (auto &i : A) cin >> i[0] >> i[1];
    UFDS ufds(N);
    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])) {
                ufds.join(i,j);
                g[i].push_back(j);
                g[j].push_back(i);
            }
        }
    }
    vector<int> val(N, -1);
    function<bool(int,int)> isBipartite = [&](int u, int x) {
        val[u] = x;
        for (int v : g[u]) if (val[v] == -1) {
            if (!isBipartite(v, x^1)) return false;
        } else if (val[v]^x^1) {
            return false;
        }
        return true;
    };

    auto P = [&](int x, int p) {
        int res = 1;
        while (p) {
            if (p&1) res = (res*x)%MOD;
            x = (x*x)%MOD; p >>= 1;
        }
        return res;
    };
    
    if (isBipartite(0,0)) cout << P(2, ufds.cc);
    else cout << 0 << '\n';
}

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

Compilation message (stderr)

port_facility.cpp: In member function 'bool UFDS::join(int64_t, int64_t)':
port_facility.cpp:17:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   17 |         if (a == b) return false; --cc;
      |         ^~
port_facility.cpp:17:35: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   17 |         if (a == b) return false; --cc;
      |                                   ^~

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