제출 #227237

#제출 시각아이디문제언어결과실행 시간메모리
227237stefanbalaz2Port Facility (JOI17_port_facility)C++14
22 / 100
5583 ms797596 KiB
/* */ #include <bits/stdc++.h> using namespace std; #define ff first #define ss second #define pb push_back ///#define ll long long typedef pair<int,int> pii; const int maxn=1e6+10; int mod=1e9+7,e; int levi[maxn],color[maxn],n,kolko,rez,grane; pii niz[2*maxn]; vector<int>vect[maxn]; set<int>tree[(1<<22)+10]; void update(int x,int l,int r,int id,int val,int tip){ if(tip)tree[x].insert(val); else tree[x].erase(val); if(l==r)return; int mid=(l+r)/2; if(id<=mid)update(x*2,l,mid,id,val,tip); else update(x*2+1,mid+1,r,id,val,tip); } void go(int x,int l,int r,int ll,int rr,int nd){ if(l>=ll && r<=rr){ for(set<int>::iterator it=tree[x].begin();it!=tree[x].end();it++){ int id=(*it); vect[nd].pb(id); vect[id].pb(nd); grane++; /// printf("%d IDID\n",id); } return; } int mid=(l+r)/2; if(ll>mid)go(x*2+1,mid+1,r,ll,rr,nd); else if(rr<=mid)go(x*2,l,mid,ll,rr,nd); else{ go(x*2,l,mid,ll,rr,nd); go(x*2+1,mid+1,r,ll,rr,nd); } } void dfs(int x,int col){ color[x]=col; for(int i=0;i<vect[x].size();i++){ int id=vect[x][i]; if(color[id]==col)rez=0; else if(color[id]==-1)dfs(id,col^1); } } int main(){ ///freopen("test.txt","r",stdin); clock_t start=clock(); scanf("%d",&n); ///int limit=30000000; ///if(n<=2000)limit=1e9; memset(color,-1,sizeof(color)); for(int i=1;i<=n;i++){ int a,b; scanf("%d %d",&a,&b); niz[a]={i,1}; niz[b]={i,-1}; levi[i]=a; } for(int i=1;i<=2*n;i++){ if(niz[i].ss>0)update(1,1,2*n,i,niz[i].ff,1); else{ int id=niz[i].ff; int lb=levi[id]; update(1,1,2*n,lb,id,0); ///printf("%d AAAAA\n",id); go(1,1,2*n,lb,i,id); /*if(grane>limit){ printf("0\n"); return 0; }*/ clock_t sad=clock(); if((double)(sad-start)/CLOCKS_PER_SEC>5){ printf("0\n"); return 0; } } } rez=1; for(int i=1;i<=n;i++){ if(color[i]==-1){ dfs(i,0); rez+=rez; if(rez>=mod)rez-=mod; } } printf("%d\n",rez); return 0; }

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

port_facility.cpp: In function 'void dfs(int, int)':
port_facility.cpp:55:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<vect[x].size();i++){
                 ~^~~~~~~~~~~~~~~
port_facility.cpp: In function 'int main()':
port_facility.cpp:67:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
     ~~~~~^~~~~~~~~
port_facility.cpp:73:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d",&a,&b);
         ~~~~~^~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...