제출 #1289372

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1289372		SamueleVid	Port Facility (JOI17_port_facility)	C++20	22 / 100	6093 ms	16632 KiB

port_facility

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

constexpr ll MOD = 1e9 + 7;

ll fp(ll a, ll b) {
    if (!b) return 1;
    ll h = fp(a, b / 2);
    h = (h * h) % MOD;
    if (b % 2) h = (h * a) % MOD;
    return h;
}

void dfs(int u, vector<int> &v, vector<int> &color, vector<vector<int>> &adj) {
    v[u] = 1;
    for (auto x : adj[u]) {
        if (v[x]) continue;
        color[x] = 1 - color[u];
        dfs(x, v, color, adj);
    }
}

int bipartite(int N, vector<vector<int>> &adj) {
    vector<int> color(N, -1);
    vector<int> v(N);
    bool bipartite = 1;
    int comps = 0;
    for (int i = 0; i < N; i ++) {
        if (v[i]) continue;
        comps ++;
        dfs(i, v, color, adj);
    }

    for (int i = 0; i < N; i ++) {
        for (auto x : adj[i]) {
            if (color[i] == color[x]) return 0;
        }
    }

    // cout << "comps : " << comps << '\n';

    return comps;
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int N; cin >> N;
    vector<int> A(N), B(N);
    for (int i = 0; i < N; i ++) cin >> A[i] >> B[i];

    vector<vector<int>> adj(N);

    // cout << "creato adj" << '\n';

    for (int i = 0; i < N; i ++) {
        for (int j = i + 1; j < N; j ++) {
            int a = i, b = j;
            if (A[a] > A[b]) swap(a,b);
            // a è a sinistra
            if (A[b] < B[a] && B[b] > B[a]) {
                // si intersecano
                adj[a].push_back(b);
                adj[b].push_back(a);
            }
        }
    }

    // for (int i = 0; i < N; i ++) {
    //     cout << "adj di " << i << " ab : " << A[i] << " " << B[i] << '\n';
    //     for (auto x : adj[i]) {
    //         cout << "- " << x << " con ab " << A[x] << " " << B[x] << '\n';
    //     }
    // }

    // cout << "riempito adj" << '\n';

    int sol = bipartite(N, adj);
    // cout << "ho sol" << '\n';
    if (sol == 0) cout << 0 << '\n';
    else cout << fp(2, sol) << '\n';       
}

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