Submission #1184086

#	Time	Username	Problem	Language	Result	Execution time	Memory
1184086		mfmme23	Port Facility (JOI17_port_facility)	C++20	0 / 100	0 ms	320 KiB

port_facility

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <queue>
using namespace std;

const int MOD = 1000000007;

int main() {
    int N;
    cin >> N;
    vector<pair<int, int>> intervals(N);
    for (int i = 0; i < N; ++i) {
        cin >> intervals[i].first >> intervals[i].second;
    }

    // Контейнеруудыг орж ирэх цагаар эрэмбэлнэ
    sort(intervals.begin(), intervals.end());

    // Граф үүсгэх
    vector<vector<int>> graph(N);
    set<pair<int, int>> active; // {гарах цаг, индекс}

    for (int i = 0; i < N; ++i) {
        int a = intervals[i].first;
        int b = intervals[i].second;

        // active сетээс давхцаж буй интервалуудыг хайж, ирмэг нэмнэ
        auto it = active.lower_bound({a, -1});
        for (auto itr = active.begin(); itr != it; ++itr) {
            int j = itr->second;
            int bj = intervals[j].second;
            if (b < bj) {
                // Хэсэгчлэн давхцаж, бүрэн агуулаагүй
                graph[i].push_back(j);
                graph[j].push_back(i);
            }
        }

        active.insert({b, i});
    }

    // Графыг хоёр өнгөөр будах
    vector<int> color(N, -1);
    int components = 0;
    bool is_bipartite = true;

    for (int i = 0; i < N; ++i) {
        if (color[i] == -1) {
            queue<int> q;
            q.push(i);
            color[i] = 0;
            while (!q.empty()) {
                int u = q.front(); q.pop();
                for (int v : graph[u]) {
                    if (color[v] == -1) {
                        color[v] = color[u] ^ 1;
                        q.push(v);
                    } else if (color[v] == color[u]) {
                        is_bipartite = false;
                        break;
                    }
                }
                if (!is_bipartite) break;
            }
            if (!is_bipartite) break;
            components++;
        }
    }

    if (!is_bipartite) {
        cout << 0 << endl;
    } else {
        // Хариу: 2^components модул MOD
        long long result = 1;
        for (int i = 0; i < components; ++i) {
            result = (result * 2) % MOD;
        }
        cout << result << endl;
    }

    return 0;
}

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