제출 #27114

#제출 시각아이디문제언어결과실행 시간메모리
27114samir_droubiPort Facility (JOI17_port_facility)C++14
0 / 100
3 ms65504 KiB
#include <bits/stdc++.h> using namespace std; int n; const int mxn=(1e6)+5; pair<int,int>a[mxn]; int st[mxn*8]; void update(int p,int l,int r,int i) { if(l==r) { ++st[p]; return; } int md=(l+r)/2; if(i<=md)update(p*2,l,md,i); else update(p*2+1,md+1,r,i); st[p]=st[p*2]+st[p*2+1]; } int sum(int p,int l,int r,int i,int j) { if(r<i||l>j)return 0; if(l>=i&&r<=j)return st[p]; int md=(l+r)/2; int x=sum(p*2,l,md,i,j); int y=sum(p*2+1,md+1,r,i,j); return x+y; } map<int,int>in; vector<int>gr[mxn]; bool vis[mxn]; int ans=1; void dfs(int v,int p) { vis[v]=true; for(int i=0;i<gr[v].size();++i) { int u=gr[v][i]; if(vis[u]) { if(u==p)continue; else ans=0; } else dfs(u,v); } } int main() { scanf("%d",&n); for(int i=1;i<=n;++i) scanf("%d%d",&a[i].first,&a[i].second); sort(a+1,a+n+1); int m=0; for(int i=1;i<=n;++i) { m+=sum(1,1,2*n,a[i].first,a[i].second); update(1,1,2*n,a[i].second); } if(m>=n) { puts("0"); return 0; } for(int i=1;i<=n;++i) { map<int,int>::iterator it=in.lower_bound(a[i].first); for(it;it!=in.end()&&(it->first)<a[i].second;++it) { gr[i].push_back(it->second); gr[it->second].push_back(i); } in[a[i].second]=i; } for(int i=1;i<=n;++i) { if(vis[i])continue; dfs(i,-1); ans*=2; } printf("%d\n",ans); return 0; }

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

port_facility.cpp: In function 'void dfs(int, int)':
port_facility.cpp:37:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<gr[v].size();++i)
                ^
port_facility.cpp: In function 'int main()':
port_facility.cpp:70:11: warning: statement has no effect [-Wunused-value]
     for(it;it!=in.end()&&(it->first)<a[i].second;++it)
           ^
port_facility.cpp:50:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&n);
                 ^
port_facility.cpp:52:43: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&a[i].first,&a[i].second);
                                           ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...