제출 #120405

#제출 시각아이디문제언어결과실행 시간메모리
120405tinderPort Facility (JOI17_port_facility)C++14
0 / 100
185 ms188308 KiB
#include <bits/stdc++.h> using namespace std; using ii = pair<int, int>; const int maxn = 2e6 + 6; const int mod = 1e9 + 7; int n, s[maxn], t[maxn]; vector<int> g[maxn], w[maxn]; void add_edge(int u, int v, int col) { w[u].emplace_back(col); w[v].emplace_back(col); g[u].emplace_back(v); g[v].emplace_back(u); } struct info { int x, id; info () {} info (int _x, int _id) { x = _x, id = _id; } bool operator < (const info &that) const { return x < that.x; } }; vector<info> ft[maxn]; vector<int> p[maxn]; void insert(int i, info j) { for(; i <= (n << 1); i += i & -i) { ft[i].emplace_back(j); } } int lptr[maxn], rptr[maxn]; void update(int i, int l, int r, int id) { if(l > r) return; int L, R; for(; i > 0; i -= i & -i) { while(lptr[i] < ft[i].size() and ft[i][lptr[i]].x < l) lptr[i]++; while(rptr[i] < ft[i].size() and ft[i][rptr[i]].x <= r) rptr[i]++; L = lptr[i]; R = rptr[i]; if(R > L) { R--; p[i][L]++; p[i][R]--; add_edge(id, ft[i][L].id, 1); } } } int vis[maxn]; int col[maxn]; void dfs(int u) { vis[u] = 1; for(int i = 0; i < g[u].size(); i++) { int v = g[u][i], c = w[u][i]; if(!vis[v]) { col[v] = col[u] ^ c; dfs(v); } } } bool valid() { vector<int> id(2 * n + 5), op(2 * n + 5); for(int i = 1; i <= n; i++) { id[s[i]] = i, op[s[i]] = +1; id[t[i]] = i, op[t[i]] = -1; } vector<int> A, B; for(int i = 1; i <= (2 * n); i++) { if(op[i] == +1) { col[id[i]] ? A.push_back(id[i]) : B.push_back(id[i]); } else { vector<int> &w0t = col[id[i]] ? A : B; if(w0t.empty() or w0t.back() != id[i]) { return false; } else { w0t.pop_back(); } } } return true; } int main(int argc, char const *argv[]) { scanf("%d", &n); vector<ii> tmp; for(int i = 1; i <= n; i++) { scanf("%d %d", &s[i], &t[i]); tmp.emplace_back(s[i], t[i]); } sort(tmp.begin(), tmp.end()); for(int i = 0; i < n; i++) { s[i + 1] = tmp[i].first; t[i + 1] = tmp[i].second; } for(int i = 1; i <= n; i++) { insert(s[i], info(t[i], i)); } for(int i = 1; i <= (n << 1); i++) { sort(ft[i].begin(), ft[i].end()); p[i].assign(ft[i].size(), 0); } for(int i = 1; i <= n; i++) { update(s[i] - 1, s[i] + 1, t[i] - 1, i); } for(int i = 1; i <= (n << 1); i++) { for(int j = 1; j < p[i].size(); j++) { p[i][j] += p[i][j - 1]; } for(int j = 0; j < (int)p[i].size() - 1; j++) { if(p[i][j]) { add_edge(ft[i][j].id, ft[i][j + 1].id, 0); } } } int ans = 1; for(int i = 1; i <= n; i++) { if(!vis[i]) { ans <<= 1; if(ans >= mod) { ans -= mod; } dfs(i); } } if(valid()) { printf("%d\n", ans); } else { puts("0"); } return 0; }

컴파일 시 표준 에러 (stderr) 메시지

port_facility.cpp: In function 'void update(int, int, int, int)':
port_facility.cpp:43:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(lptr[i] < ft[i].size() and ft[i][lptr[i]].x < l) lptr[i]++;
         ~~~~~~~~^~~~~~~~~~~~~~
port_facility.cpp:44:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(rptr[i] < ft[i].size() and ft[i][rptr[i]].x <= r) rptr[i]++;
         ~~~~~~~~^~~~~~~~~~~~~~
port_facility.cpp: In function 'void dfs(int)':
port_facility.cpp:61:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < g[u].size(); i++) {
                 ~~^~~~~~~~~~~~~
port_facility.cpp: In function 'int main(int, const char**)':
port_facility.cpp:115:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 1; j < p[i].size(); j++) {
                  ~~^~~~~~~~~~~~~
port_facility.cpp:93:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
port_facility.cpp:96:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &s[i], &t[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...