Submission #39757

#	Time	Username	Problem	Language	Result	Execution time	Memory
39757		aome	Port Facility (JOI17_port_facility)	C++14	78 / 100	6000 ms	946680 KiB

port_facility

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

typedef pair<int, int> ii;
typedef pair<int, bool> p;
const int N = 1000005;
const int MOD = 1e9 + 7;

int n, cnt, c[N];
int it[8 * N];
int prv[25 * N];
p val[25 * N];
vector<ii> a;
vector<p> G[N];

void NO() {
    cout << 0 << '\n'; exit(0);
}

void addEdge(int u, int v, bool w) {
    G[u].push_back(p(v, w)), G[v].push_back(p(u, w));
}

void upd(int i, int l, int r, int x, int id) {
    ++cnt, prv[cnt] = it[i], val[cnt] = p(id, 0), it[i] = cnt;
    if (l == r) return;
    int mid = (l + r) >> 1;
    if (mid >= x) upd(i << 1, l, mid, x, id);
    else upd(i << 1 | 1, mid + 1, r, x, id);
}

void get(int i, int l, int r, int u, int v, int id) {
    if (l > v || u > r) return;
    if (u <= l && r <= v) {
        if (!it[i]) return;
        int cur = it[i];
        while (cur) {
            addEdge(id, val[cur].first, val[cur].second ^ 1), cur = prv[cur];
        }
        val[it[i]] = ii(id, 1), prv[it[i]] = 0;
        return;
    }
    int mid = (l + r) >> 1;
    get(i << 1, l, mid, u, v, id);
    get(i << 1 | 1, mid + 1, r, u, v, id);
}

void dfs(int u) {
    for (auto v : G[u]) {
        if (c[v.first] != -1 && (c[u] ^ v.second) != c[v.first]) NO();
        if (c[v.first] != -1) continue;
        c[v.first] = c[u] ^ v.second, dfs(v.first);
    }
}

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        int x, y;
        scanf("%d %d", &x, &y);
        a.push_back(ii(x, y));
    }
    sort(a.begin(), a.end());
    for (int i = 0; i < n; ++i) {
        get(1, 1, 2 * n, a[i].first, a[i].second, i);
        upd(1, 1, 2 * n, a[i].second, i);
    }
    memset(c, -1, sizeof(c));
    int num = 0;
    for (int i = 0; i < n; ++i) {
        if (c[i] != -1) continue;
        c[i] = 1, dfs(i), num++;
    }
    int res = 1;
    for (int i = 0; i < num; ++i) res = 1LL * res * 2 % MOD;
    cout << res << '\n';
}

Compilation message (stderr)

port_facility.cpp: In function 'int main()':
port_facility.cpp:57:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
                    ^
port_facility.cpp:60:31: 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: 0 / 22