# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
22954 | sbansalcs | Port Facility (JOI17_port_facility) | C++14 | 33 ms | 226636 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <iostream>
#include <vector>
#include <set>
#include <assert.h>
using namespace std;
const int N = 1e6+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[a]>sz[b]) swap(a,b);
for(int i=0;i<2;i++) {
for(auto c:st[a][i]) {
st[b][i^d].insert(c);
st2[b][i^d].insert(B[c]);
parent[c]=b;
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;
}
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]);
}
for(int i=1;i<=2*N;i++) {
if(!in[i]) continue;
int v = ver[i];
vector<int> vt;
for(auto c:ms) {
if(c>A[v]) break;
vt.push_back(c);
}
for(auto c:vt) {
assert(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;
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) 메시지
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |