Submission #651655

#	Time	Username	Problem	Language	Result	Execution time	Memory
651655		Lobo	Port Facility (JOI17_port_facility)	C++17	22 / 100	86 ms	63912 KiB

port_facility

#include<bits/stdc++.h>
using namespace std;
const long long inf = (long long) 1e18 + 10;
const int inf1 = (int) 1e9 + 10;
#define int long long
#define dbl long double
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()

const int maxn = 2e3+10;
const int mod = 1e9+7;

int n, a[maxn], b[maxn], ds[maxn], dsz[maxn], bad[maxn][maxn];
vector<int> bads[maxn];
pair<int,int> c[maxn];

int find(int v) {
    if(v == ds[v]) return v;
    return ds[v] = find(ds[v]);
}

void join(int u, int v) {
    if(dsz[u] < dsz[v]) swap(u,v);
    ds[v] = u;
    dsz[u]+= dsz[v];
}

void solve() {
    cin >> n;

    for(int i = 1; i <= n; i++) {
        cin >> a[i] >> b[i];
        c[i] = mp(a[i],b[i]);
    }
    sort(c+1,c+1+n);

    for(int i = 1; i <= n; i++) {
        a[i] = c[i].fr;
        b[i] = c[i].sc;
    }

    for(int i = 1; i <= n; i++) {
        ds[i] = i;
        dsz[i] = 1;
    }

    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            if(a[i] < a[j] && a[j] < b[i] && b[i] < b[j]) {
                bads[i].pb(j);
                bad[i][j] = 1;
            }

            if(a[j] < a[i] && a[i] < b[j] && b[j] < b[i]) {
                bads[i].pb(j);
                bad[i][j] = 1;
            }
        }
        if(bads[i].size()) {
            for(int j = 1; j < bads[i].size(); j++) {
                if(find(bads[i][j-1]) != find(bads[i][j])) join(find(bads[i][j-1]),find(bads[i][j]));
            }
        }
    }

    int ans = 1;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            if(find(i) == find(j) && bad[i][j]) ans = 0;
        }
    }
    if(ans == 0) {
        cout << 0 << endl;
        return;
    }

    for(int i = 1; i <= n; i++) {
        if(bads[i].size() && find(bads[i][0]) != find(i)) join(find(bads[i][0]),find(i));
    }

    for(int i = 1; i <= n; i++) {
        if(find(i) == i) {
            ans*= 2;
            ans%= mod;
        }
    }
    cout << ans << endl;
}

int32_t main() {
    ios::sync_with_stdio(false); cin.tie(0);

    // freopen("in.in", "r", stdin);
    // freopen("out.out", "w", stdout);
    int tt = 1;
    // cin >> tt;
    while(tt--) {
        solve();
    }

}

Compilation message (stderr)

port_facility.cpp: In function 'void solve()':
port_facility.cpp:64:30: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |             for(int j = 1; j < bads[i].size(); j++) {
      |                            ~~^~~~~~~~~~~~~~~~

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