Submission #129847

#TimeUsernameProblemLanguageResultExecution timeMemory
129847nikolapesic2802Port Facility (JOI17_port_facility)C++14
22 / 100
6091 ms14968 KiB
#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, dsu[N<<1]; vector<pii> V; int find(int x) { return dsu[x] = dsu[x] == x ? x : find(dsu[x]);} void mge(int x, int y) { dsu[find(x)] = find(y); } int main() { scanf("%d", &n); V.reserve(n); iota(dsu, dsu+2*N, 0); 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) { auto it = pos.lower_bound(V[i].x), zz = pos.upper_bound(V[i].y); bool st = it != zz; if(zz != pos.begin()) zz--; if(st) for(;; ++it) { mge(i, it->y+n), mge(i+n, it->y); if(it == zz) break; } pos[V[i].y] = i; } for(int i = 0; i < n; ++i) if(find(i) == find(i+n)) return puts("0"), 0; int ans = 1; for(int i = 0; i < n; ++i) if(find(i) == i) ans = ans * 2 % M; printf("%d\n", ans); }

Compilation message (stderr)

port_facility.cpp: In function 'int main()':
port_facility.cpp:18:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
port_facility.cpp:21: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);
                                      ~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...