제출 #22971

#제출 시각아이디문제언어결과실행 시간메모리
22971sbansalcsPort Facility (JOI17_port_facility)C++14
22 / 100
3369 ms986412 KiB
#include <iostream> #include <vector> #include <set> #include <assert.h> using namespace std; const int N = 2e5+5; set<int> st[N][2]; set<int> st2[N][2]; int A[N],B[N]; // pair<int,int> arr[N]; int comps; bool in[2*N]; int ver[2*N]; int rel[N]; int parent[N]; int sz[N]; set<int> ms; int read() { int x;return scanf("%d",&x),x; } bool addE(int a, int b) { // cout<<"addE : "<<a<<" "<<b<<endl; int u = parent[a],v=parent[b]; // cout<<"oh : "<<u<<" "<<v<<endl; if(u==v) { return rel[a]!=rel[b]; } comps--; int d = !(rel[a]^rel[b]); if(sz[u]>sz[v]) swap(u,v); for(int i=0;i<2;i++) { for(auto c:st[u][i]) { st[v][i^d].insert(c); st2[v][i^d].insert(B[c]); parent[c]=v; rel[c]^=d; } } return 1; } int get_replacement(int x, int a) { int p = parent[x]; int d = rel[x]; set<int>::iterator it; it = st2[p][d].lower_bound(a+1); if(it!=st2[p][d].end()) return *it; return -1; } void ass(bool x) { while(!x) { } } int main() { int n=read(); comps=n; for(int i=1;i<=n;i++) { A[i]=read();B[i]=read(); in[A[i]]=1; ver[A[i]]=ver[B[i]]=i; parent[i]=i; st[i][0].insert(i); sz[i]=1; st2[i][0].insert(B[i]); } vector<int> vt; for(int i=1;i<=2*n;i++) { if(!in[i]) continue; vt.clear(); int v = ver[i]; ass(A[v]==i); for(auto c:ms) { if(c>A[v]) break; vt.push_back(c); } for(auto c:vt) { assert(c<A[v]); // assert(c!=A[v]); // while(c==A[v]) { // } int h = get_replacement(ver[c],A[v]); assert(h>A[v] || h==-1); // cout<<"erased : "<<c<<" and inserted: "<<h<<endl; ms.erase(ms.find(c)); if(h!=-1) ms.insert(h); } bool f=0; vt.clear(); for(auto c:ms) { if(c>B[v]) break; if(!addE(v,ver[c])) { // cout<<"fuck : "<<v<<" "<<c<<" "<<ver[c]<<endl; // assert(0); cout<<0;return 0; } if(f==0) f=1; else vt.push_back(c); } for(auto c:vt) { ms.erase(ms.find(c)); } ms.insert(B[v]); } // cout<<"yeah : \n"; // cout<<comps<<endl; long long ans=1;int mod=1e9+7; for(int i=1;i<=comps;i++) { ans=(ans*2)%mod; } cout<<ans; return 0; }

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

port_facility.cpp: In function 'int read()':
port_facility.cpp:21:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int x;return scanf("%d",&x),x;
                               ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...