Submission #1210956

#	Time	Username	Problem	Language	Result	Execution time	Memory
1210956		nguyn	Port Facility (JOI17_port_facility)	C++20	100 / 100	1165 ms	67140 KiB

port_facility

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

#define ll long long 
#define F first
#define S second
#define pb push_back 
#define pii pair<int,int>

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

struct DSU {
	int n; 
	vector<int> lab;

	DSU() {}
	DSU(int _n) : n(_n) {
		lab.assign(n + 3, -1); 
	}

	int find(int x) {
		return lab[x] < 0 ? x : lab[x] = find(lab[x]); 
	}

	void join(int x, int y) {
		if ((x = find(x)) == (y = find(y))) return;
		if (lab[x] > lab[y]) swap(x, y); 
		lab[x] += lab[y];
		lab[y] = x;  
	} 
} dsu;

int n;
pii a[N]; 
int vis[N];

void add(int &x, int y) {
    x += y;
    if (x >= mod) x -= mod;
}

signed main(){
    ios_base::sync_with_stdio(false) ; 
    cin.tie(0) ; cout.tie(0) ; 
    if (fopen("INP.INP" ,"r")) {
        freopen("INP.INP" ,"r" , stdin) ;
        freopen("OUT.OUT" , "w" , stdout) ;
    }
    cin >> n;
    for (int i = 1; i <= n; i++) {
    	cin >> a[i].F >> a[i].S;
    }
    sort(a + 1, a + 1 + n);
    dsu = DSU(2 * n); 
    // i + n = ~i; 
    set<pii> st; 
    for (int i = 1; i <= n; i++) {
        auto itl = st.lower_bound({a[i].F, 0});
        auto itr = st.lower_bound({a[i].S, 0}); 
        if (itr != st.begin() && itl != st.end() && itl != itr) {
            itr--; 
            while(1) {
                int v = itl->second; 
                dsu.join(i, v + n); 
                dsu.join(v, i + n); 
                // cout << i << ' ' << v << '\n';
                if (dsu.find(itr->second) == dsu.find(itl->second)) break;
                itl++; 
            }
        }
        st.insert({a[i].S, i});
    }
    for (int i = 1; i <= n; i++) {
        if (dsu.find(i) == dsu.find(i + n)) {
            cout << 0;
            return 0;
        }
    }
    int res = 1; 
    for (int i = 1; i <= n * 2; i++) {
        // cout << dsu.lab[i] << ' ';
        int t = dsu.find(i);
        if (!vis[t]) {
            vis[t] = 1;
            if (i <= n) vis[dsu.find(i + n)] = 1;
            add(res, res);
        }
    }
    cout << res;
}

Compilation message (stderr)

port_facility.cpp: In function 'int main()':
port_facility.cpp:47:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |         freopen("INP.INP" ,"r" , stdin) ;
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
port_facility.cpp:48:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |         freopen("OUT.OUT" , "w" , stdout) ;
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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