이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define pb push_back
#define all(v) ((v).begin(), (v).end())
#define sortv(v) sort(all(v))
#define sz(v) ((int)(v).size())
#define uniqv(v) (v).erase(unique(all(v)), (v).end())
#define umax(a, b) (a)=max((a), (b))
#define umin(a, b) (a)=min((a), (b))
#define FOR(i,a,b) for(int i = (a); i <= (b); i++)
#define rep(i,n) FOR(i,1,n)
#define rep0(i,n) FOR(i,0,(int)(n)-1)
#define FI first
#define SE second
#define INF 2000000000
#define INFLL 1000000000000000000LL
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const ll DIV = 1000000007;
const int MAX_N = 1000000;
int N;
vector<pii> vt;
bool zero = false;
vector<int> gp[MAX_N*2+1];
int c[MAX_N*2+1];
struct UNIONFIND{
int SZ;
vector<int> group;
vector<int> sz;
void init(int x){
SZ = x;
group.reserve(x+1);
sz.reserve(x+1);
for(int i=0; i<=SZ; i++){
group.pb(i);
sz.pb(1);
}
}
int find_g(int x){
return x==group[x] ? x : group[x] = find_g(group[x]);
}
void union_g(int x, int y){
x = find_g(x); y = find_g(y);
if(sz[x]>sz[y]) {
int tmp = x; x = y; y = tmp;
}
group[x] = y;
sz[y]+=sz[x];
}
int calc_num(){
int ret = 0;
for(int i=1; i<=SZ; i++){
if(find_g(i)==i) ret++;
}
return ret;
}
};
UNIONFIND UF;
struct SEG{
struct NODE{
int l=-1, r=-1;
vector<int> v;
int sz=0;
};
vector<NODE> seg;
int SZ, cnt;
void Init(int x){
SZ = x; seg.resize(SZ*2);
cnt = 1;
init(0, 1, SZ);
}
void init(int idx, int s, int e){
seg[idx].v.reserve(e-s+1);
if(s==e) return;
seg[idx].l = cnt++; seg[idx].r = cnt++;
init(seg[idx].l, s, (s+e)/2);
init(seg[idx].r, (s+e)/2+1, e);
}
void Update(int x){
update(0, 1, SZ, x);
}
void update(int idx, int s, int e, int k){
//cout<<idx<<" "<<s<<" "<<e<<" "<<x<<" "<<y<<endl;
seg[idx].v.pb(k);
if(s==e) return;
if(k<=(s+e)/2){
update(seg[idx].l, s, (s+e)/2, k);
}else{
update(seg[idx].r, (s+e)/2+1, e, k);
}
}
void Calc(int x, int y){
calc(0, 1, SZ, x, y);
}
void calc(int idx, int s, int e, int x, int y){
if(seg[idx].v.empty()) return;
//cout<<idx<<" "<<s<<" "<<e<<" "<<x<<" "<<y<<endl;
if(x<=s && e<=y){
int k=0;
//cout<<idx<<" "<<s<<" "<<e<<" "<<x<<" "<<y<<endl;
while(!seg[idx].v.empty()){
int t = seg[idx].v.back(); seg[idx].v.pop_back();
k = max(k, t);
gp[t].pb(y); gp[y].pb(t);
UF.union_g(t, y);
}
if(k!=0) seg[idx].v.pb(k);
return;
}else if(x>e || y<s) return;
calc(seg[idx].l, s, (s+e)/2, x, y);
calc(seg[idx].r, (s+e)/2+1, e, x, y);
}
};
SEG Seg;
void bfs(int x){
for(int i : gp[x]){
if(c[i]==0){
c[i] = 3 - c[x];
bfs(i);
}else if(c[i]==c[x]){
zero=true;
return;
}
}
}
int main(){
scanf("%d", &N);
for(int i=1; i<=N; i++){
int a, b;
scanf("%d%d", &a, &b);
vt.pb({a, b});
}
sort(vt.begin(), vt.end());
int idx = 0;
UF.init(N*2);
Seg.Init(N*2);
for(int i=1; i<=N*2; i++){
if(idx<N && vt[idx].first==i){
//cout<<vt[idx].first<<" "<<vt[idx].second<<endl;
Seg.Calc(vt[idx].first, vt[idx].second);
Seg.Update(vt[idx].second);
idx++;
}
}
for(int i=1; i<=N*2; i++){
if(c[i]==0) {
c[i] = 1;
bfs(i);
if(zero){
printf("0");
return 0;
}
}
}
int t = UF.calc_num()-N;
ll ans = 1;
for(int i=1; i<=t; i++){
ans = (ans*(ll)2)%DIV;
}
cout<<ans;
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
port_facility.cpp: In function 'int main()':
port_facility.cpp:142:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &N);
~~~~~^~~~~~~~~~
port_facility.cpp:145:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &a, &b);
~~~~~^~~~~~~~~~~~~~~~
# | 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... |