Submission #77892

#	Time	Username	Problem	Language	Result	Execution time	Memory
77892		win11905	Port Facility (JOI17_port_facility)	C++11	22 / 100	6069 ms	796360 KiB

port_facility

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

#define pii pair<int, int>
#define x first
#define y second

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

int n, cnt, col[N];
vector<pii> V;
vector<int> g[N];

void dfs(int u) {
    for(int v : g[u]) if(!col[v]) col[v] = col[u] ^ 3, dfs(v);
    else if(col[v] != (col[u] ^ 3)) cnt = -1e9;
}

int main() {
    scanf("%d", &n);
    V.reserve(n);
    for(int i = 0, a, b; i < n; ++i) scanf("%d %d", &a, &b), V.emplace_back(a, b);
    sort(V.begin(), V.end());
    map<int, int> pos;
    for(int i = 0; i < n; ++i) {
        for(auto it = pos.lower_bound(V[i].x); it != pos.upper_bound(V[i].y); ++it) {
            g[i].emplace_back(it->y), g[it->y].emplace_back(i);
        }
        pos[V[i].y] = i;
    }
    
    for(int i = 0; i < n; ++i) if(!col[i]) {
        col[i] = 1, cnt++;
        queue<int> Q; Q.emplace(i);
        while(!Q.empty()) {
            int now = Q.front(); Q.pop();
            for(int v : g[now]) 
                if(!col[v]) Q.emplace(v), col[v] = col[now] ^ 3;
                else if(col[v] != (col[now] ^ 3)) cnt = -1e9;
        }
    }
    if(cnt < 0) return puts("0"), 0;
    int ans = 1;
    for(int i = 0; i < cnt; ++i) ans = (ans << 1) % M;
    printf("%d\n", ans);
}

Compilation message (stderr)

port_facility.cpp: In function 'int main()':
port_facility.cpp:21:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
port_facility.cpp:23:60: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i = 0, a, b; i < n; ++i) scanf("%d %d", &a, &b), V.emplace_back(a, b);
                                      ~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

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