Submission #1142756

#	Time	Username	Problem	Language	Result	Execution time	Memory
1142756		VMaksimoski008	Port Facility (JOI17_port_facility)	C++20	10 / 100	1616 ms	47968 KiB

port_facility

#include <bits/stdc++.h>
#define ar array
//#define int long long

using namespace std;

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

const int mod = 1e9 + 7;
const ll inf = 1e18;
const int maxn = 1e6 + 5;

bool ok = 1;
int col[maxn];
vector<int> G[maxn];
vector<ar<int, 2> > a(maxn);

void dfs(int u, int c=1) {
    col[u] = c;
    for(int v : G[u]) {
        // if(col[v] == col[u]) ok = 0;
        if(!col[v]) dfs(v, 3 - c);
    }
}

bool edge(int i, int j) {
    return (a[j][0] < a[i][1] && a[i][1] < a[j][1]);
}

signed main() {
    ios_base::sync_with_stdio(false);
    cout.tie(0); cin.tie(0);

    int n; cin >> n;
    for(int i=1; i<=n; i++) cin >> a[i][0] >> a[i][1];
    sort(a.begin()+1, a.begin()+n+1);

    for(int i=1; i<=n; i++) {
        for(int j=i+1; j<=n; j++) {
            if(edge(i, j)) {
                G[i].push_back(j);
                G[j].push_back(i);
            }
        }
    }

    for(int i=1; i<=n; i++)
        for(int j=i+1; j<=n; j++)
            for(int k=j+1; k<=n; k++)
                if(edge(i, j) && edge(j, k) && edge(i, k)) ok = 0;

    ll ans = 1;
    for(int i=1; i<=n; i++) {
        if(col[i]) continue;
        ans = (ans * 2) % mod;
        dfs(i);
    }

    cout << (ok ? ans : 0) << '\n';
}

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