Submission #953481

#	Time	Username	Problem	Language	Result	Execution time	Memory
953481		Pring	Port Facility (JOI17_port_facility)	C++17	22 / 100	27 ms	32760 KiB

port_facility

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

#ifdef MIKU
string dbmc = "\033[1;38;2;57;197;187m", dbrs = "\033[0m";
#define debug(x...) cout << dbmc << "[" << #x << "]: ", dout(x)
void dout() { cout << dbrs << endl; }
template <typename T, typename ...U>
void dout(T t, U ...u) { cout << t << (sizeof...(u) ? ", " : ""); dout(u...); }
#else
#define debug(...) 39
#endif

#define int long long
#define fs first
#define sc second
#define mp make_pair
#define FOR(i, j, k) for (int i = j, Z = k; i < Z; i++)
typedef pair<int, int> pii;

const int MXN = 2005, mod = 1000000007;
int n;
pii p[MXN];
vector<int> edge[MXN];
int clr[MXN];

bool OVERLAP(pii a, pii b) {
    if (a.sc < b.fs) return false;
    return a.sc < b.sc;
}

bool DFS(int id, int c) {
    clr[id] = c;
    for (auto &i : edge[id]) {
        if (clr[i] == 0) {
            if (!DFS(i, c * -1)) return false;
        } else if (clr[i] == c) return false;
    }
    return true;
}

int miku() {
    cin >> n;
    FOR(i, 0, n) cin >> p[i].fs >> p[i].sc;
    sort(p, p + n);
    FOR(i, 0, n) FOR(j, i + 1, n) {
        if (OVERLAP(p[i], p[j])) {
            edge[i].push_back(j);
            edge[j].push_back(i);
        }
    }
    int ans = 1;
    FOR(i, 0, n) {
        if (clr[i]) continue;
        ans *= 2;
        ans -= (ans >= mod ? mod : 0);
        if (!DFS(i, 1)) return 0;
    }
    return ans;
}

int32_t main() {
    cin.tie(0) -> sync_with_stdio(false);
    cin.exceptions(cin.failbit);
    cout << miku() << '\n';
    return 0;
}

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