Submission #135639

#	Time	Username	Problem	Language	Result	Execution time	Memory
135639		PeppaPig	Port Facility (JOI17_port_facility)	C++14	100 / 100	1839 ms	85524 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]); }

int n;
vector<pii> vec;
map<int, int> mp;

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);
    }
    sort(vec.begin(), vec.end());
    for(int i = 0; i < n; i++) {
        auto st = mp.lower_bound(vec[i].x), en = mp.upper_bound(vec[i].y);
        if(en != mp.begin()) for( ; st != en; st++) {
            par[find(i)] = find(st->y + n);
            par[find(i + n)] = find(st->y);
            if(find(st->y) == find(prev(en)->y)) break;
        }
        mp[vec[i].y] = i;
    }
    for(int i = 0; i < n; i++) if(find(i) == find(i + n)) return !printf("0\n");
    long ans = 1;
    for(int i = 0; i < n; i++) 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:24:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
port_facility.cpp:26: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: 10 / 10
• Subtask 2: 12 / 12
• Subtask 3: 56 / 56
• Subtask 4: 22 / 22