Submission #990385

#	Time	Username	Problem	Language	Result	Execution time	Memory
990385		LOLOLO	Port Facility (JOI17_port_facility)	C++17	22 / 100	6079 ms	15724 KiB

port_facility

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
#define           f     first
#define           s     second
#define           pb    push_back
#define           ep    emplace
#define           eb    emplace_back
#define           lb    lower_bound
#define           ub    upper_bound
#define       all(x)    x.begin(), x.end()
#define      rall(x)    x.rbegin(), x.rend()
#define   uniquev(v)    sort(all(v)), (v).resize(unique(all(v)) - (v).begin())
#define     mem(f,x)    memset(f , x , sizeof(f))
#define        sz(x)    (ll)(x).size()
#define  __lcm(a, b)    (1ll * ((a) / __gcd((a), (b))) * (b))
#define          mxx    *max_element
#define          mnn    *min_element
#define    cntbit(x)    __builtin_popcountll(x)
#define       len(x)    (int)(x.length())
 
const int N = 1e6 + 10;
pair <int, int> parent[N];
int rnk[N], bipartite[N], cnt, id[N * 2];

void make_set(int v) {
    parent[v] = make_pair(v, 0);
    rnk[v] = 0;
    bipartite[v] = true;
}

pair<int, int> find_set(int v) {
    if (v != parent[v].first) {
        int parity = parent[v].second;
        parent[v] = find_set(parent[v].first);
        parent[v].second ^= parity;
    }
    return parent[v];
}

bool add_edge(int a, int b) {
    pair<int, int> pa = find_set(a);
    a = pa.first;
    int x = pa.second;

    pair<int, int> pb = find_set(b);
    b = pb.first;
    int y = pb.second;

    if (a == b) {
        if (x == y)
            bipartite[a] = false;
    } else {
        cnt--;
        if (rnk[a] < rnk[b])
            swap (a, b);
        parent[b] = make_pair(a, x^y^1);
        bipartite[a] &= bipartite[b];
        if (rnk[a] == rnk[b])
            ++rnk[a];
    }

    return bipartite[a];
}

ll solve() {
    vector <pair <int, int>> seg;
    int n;
    cin >> n;

    cnt = n;

    for (int i = 1; i <= n; i++) {
        int a, b;
        cin >> a >> b;
        seg.pb({a, b});
    }

    sort(all(seg));

    set <int> save;

    for (int i = 0; i < n; i++) {
        make_set(i + 1);
        id[seg[i].f] = id[seg[i].s] = i + 1;
        auto it = save.lower_bound(seg[i].f);

        while (it != save.end() && *it < seg[i].s) {
            if (add_edge(i + 1, id[*it]) == 0)
                return 0;

            it = next(it);
        }

        save.insert(seg[i].s);
    }

    ll ans = 1, mod = 1e9 + 7;

    for (int i = 1; i <= cnt; i++) {
        ans = (ans + ans) % mod;
    }

    return ans;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    int t = 1;
    //cin >> t;
 
    while (t--) {
        cout << solve() << '\n';
    }
 
    return 0;
} 

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