Submission #135589

#	Time	Username	Problem	Language	Result	Execution time	Memory
135589		PeppaPig	Port Facility (JOI17_port_facility)	C++14	0 / 100	11 ms	8184 KiB

port_facility

#include <bits/stdc++.h>

#define long long long
#define pii pair<int, int>
#define x first
#define y second

using namespace std;

const int N = 1e6+5;
const int M = 1e9+7;

int par[N << 1];

int find(int x) { return par[x] = x == par[x] ? x : find(par[x]); }

struct item {
    int x, y, idx;
    item(int x, int y, int idx) : x(x), y(y), idx(idx) { }
    friend bool operator<(const item &a, const item &b) {
        return a.y < b.y;
    }
};

int n;
vector<item> vec;
set<item> S;

int main() {
    iota(par, par + (N << 1), 0);

    scanf("%d", &n);
    for(int i = 1, x, y; i <= n; i++) {
        scanf("%d %d", &x, &y);
        vec.emplace_back(x, y, i);
    }
    sort(vec.begin(), vec.end(), [&](const item &a, const item &b) {
        return a.x < b.x;
    });
    for(item now : vec) {
        while(!S.empty() && S.begin()->y < now.x) S.erase(S.begin());
        auto f = S.upper_bound(item(0, now.y, 0));
        if(!S.empty()) for(auto it = S.begin(); it != f; it++) {
            int u = now.idx, v = it->idx;
            par[find(u)] = find(v + n);
            par[find(v + n)] = find(u);
            if(find(v) == find(prev(f)->idx)) break;
        }
        S.emplace(now);
    }
    long ans = 1;
    for(int i = 1; i <= n; i++) {
        if(find(i) == find(i + n)) return !printf("0\n");
        if(find(i) == i) ans = ans * 2 % M;
    }
    printf("%lld\n", ans);

    return 0;
}

Compilation message (stderr)

port_facility.cpp: In function 'int main()':
port_facility.cpp:32:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
port_facility.cpp:34:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &x, &y);
         ~~~~~^~~~~~~~~~~~~~~~~

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