제출 #975763

#제출 시각아이디문제언어결과실행 시간메모리
975763starchanPort Facility (JOI17_port_facility)C++17
0 / 100
9 ms35672 KiB
#include<bits/stdc++.h> using namespace std; #define in array<int, 2> #define pb push_back #define pob pop_back #define fast() ios_base::sync_with_stdio(false); cin.tie(NULL) const int SMX = 1e6+5; const int MX = 2e6+3; const int LMX = 3e7+5e6; const int mod = 1e9+7; vector<int> g[SMX]; int lleft[LMX]; int rright[LMX]; int tree[LMX]; int nxt = 0; int New() { nxt++; lleft[nxt] = rright[nxt] = -1; return nxt; } int build(int l, int r) { int id = New(); int m = (l+r)/2; if(l==r) return id; lleft[id] = build(l, m); rright[id] = build(m+1, r); tree[id] = 0; return id; } int upd(const int &i, int pos, int id, int l, int r) { int id_n; if(l == r) id_n = i; else id_n = New(); tree[id_n] = 1; if(l == r) return id_n; lleft[id_n] = lleft[id]; rright[id_n] = rright[id]; int m = (l+r)/2; if(pos <= m) lleft[id_n] = upd(i, pos, lleft[id], l, m); else rright[id_n] = upd(i, pos, rright[id], m+1, r); return id_n; } void add(const int &pp, int ql, int qr, int id, int l, int r) { if(qr < l || r < ql) return; if((ql <= l) && (r <= qr)) { g[pp].pb(id); return; } int m = (l+r)/2; add(pp, ql, qr, lleft[id], l, m); add(pp, ql, qr, rright[id], m+1, r); return; } int pa[LMX]; bool col[LMX]; bool works = true; int leader(int u) { if(pa[u] < 0) return u; else { int p = leader(pa[u]); col[u] = col[u]^col[pa[u]]; return pa[u] = p; } } void merge(int u, int v, int xr) { int x = leader(u); int y = leader(v); if(x == y) { if(col[u]^col[v]^xr) works = false; return; } if(pa[x] < pa[y]) { swap(x, y); swap(u, v); } pa[y]+=pa[x]; pa[x] = y; col[x] = col[u]^col[v]^xr; return; } bitset<LMX> vis, ppl; void dfs(int u) { vis[u] = 1; if(lleft[u] != -1) { if((!vis[lleft[u]]) && tree[lleft[u]]) dfs(lleft[u]); if((!vis[rright[u]]) && tree[rright[u]]) dfs(rright[u]); if(tree[lleft[u]]){ //cout << "cat_L_Calling " << lleft[u] << " from " << u << endl; merge(u, lleft[u], 0);} if(tree[rright[u]]){ //cout << "cat_R_Calling " << rright[u] << " from " << u << endl; merge(u, rright[u], 0);} return; } for(int v: g[u]) { if(!tree[v]) continue; merge(u, v, 1); if(vis[v]) { //cout << "Tried to call " << v << " from " << u << endl; continue; } //cout << "Calling " << v << " from " << u << "\n"; dfs(v); } return; } signed main() { fast();//During debugging, this should ideally be removed. int n; cin >> n; vector<in> vv(n); for(int i = 0; i < n; i++) cin >> vv[i][0] >> vv[i][1]; sort(vv.begin()+1, vv.end()); int sn = 0; nxt = n; int root = build(1, 2*n); //cout << "nxt = " << nxt << endl; int b[n]; for(int i = 0; i < n; i++) { lleft[i] = rright[i] = -1; root = upd(i, vv[i][1], root, 1, 2*n); add(i, vv[i][0], vv[i][1]-1, root, 1, 2*n); //cout << "b[sn] = " << b[sn] << endl; } int N = nxt; for(int i = 0; i <= N; i++) pa[i] = -1; for(int i = 0; i < n; i++) dfs(i); if(!works) { cout << "0\n"; return 0; } int ans = 1; for(int i = 0; i < n; i++) { if(ppl[leader(i)]) continue; ppl[leader(i)] = 1; ans*=2; ans%=mod; } cout << ans << "\n"; return 0; }

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

port_facility.cpp: In function 'int main()':
port_facility.cpp:147:6: warning: unused variable 'sn' [-Wunused-variable]
  147 |  int sn = 0; nxt = n; int root = build(1, 2*n); //cout << "nxt = " << nxt << endl;
      |      ^~
port_facility.cpp:149:6: warning: unused variable 'b' [-Wunused-variable]
  149 |  int b[n];
      |      ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...