Submission #861614

#TimeUsernameProblemLanguageResultExecution timeMemory
861614PyqeSoccer Stadium (IOI23_soccer)C++17
100 / 100
2013 ms1360772 KiB
#include <bits/stdc++.h> #include "soccer.h" using namespace std; #define mp make_pair #define fr first #define sc second int n,ht[2069],lg2[2069],dp[8000069],dsu[8000069],z=0; bitset<2069> a[2069]; pair<pair<int,int>,pair<int,int>> ky[8000069]; pair<int,int> sp[2][2069][11][2069]; vector<int> al[8000069]; bitset<8000069> vtd; inline int god(int xx,int x,int y) { return xx*n*n+(x-1)*n+y; } inline void spbd(int xx,int x) { int i,j; for(i=1;i<=n;i++) { sp[xx][x][0][i]={ht[i],i}; } for(i=1;1<<i<=n;i++) { for(j=1;j<=n-(1<<i)+1;j++) { sp[xx][x][i][j]=min(sp[xx][x][i-1][j],sp[xx][x][i-1][j+(1<<i-1)]); } } } inline pair<int,int> spqr(int xx,int x,int lb,int rb) { int e=lg2[rb-lb+1]; return min(sp[xx][x][e][lb],sp[xx][x][e][rb-(1<<e)+1]); } inline void ae(int x,int y) { al[x].push_back(y); } int fd(int x) { if(dsu[x]!=x) { dsu[x]=fd(dsu[x]); } return dsu[x]; } inline int dnc(int xx,int x,int lb,int rb) { if(lb<=rb) { int u,k,l,p,p2,e,clb,crb; pair<int,int> tmp=spqr(xx,x,lb,rb),tmp2; u=!xx*2-1; clb=x-(tmp.fr-1)*u; crb=x; if(xx) { swap(clb,crb); } if(clb<=crb) { p=god(xx,x,tmp.sc); ky[p]={{clb,crb},{lb,rb}}; } else { p=-1; } for(k=lb,l=rb;k<=l;k=e+1) { tmp2=spqr(xx,x,k,l); if(tmp2.fr!=tmp.fr) { break; } e=tmp2.sc; p2=dnc(xx,x,k,e-1); if(p!=-1&&p2!=-1) { ae(p,p2); } } p2=dnc(xx,x,k,l); if(p!=-1&&p2!=-1) { ae(p,p2); } if(p!=-1) { tmp2=spqr(!xx,x-(tmp.fr-1)*u,lb,rb); p2=god(!xx,x-(tmp.fr-1)*u,tmp2.sc); if(tmp2.fr!=tmp.fr) { ae(p,p2); } else { dsu[fd(p2)]=fd(p); } } return p; } else { return -1; } } void dfs(int x) { int i,sz=al[x].size(),l,w,clb,crb,lb,rb,lb2,rb2; vtd[x]=1; dp[x]=0; for(i=0;i<sz;i++) { l=fd(al[x][i]); clb=ky[x].fr.fr; crb=ky[x].fr.sc; lb=ky[l].fr.fr; rb=ky[l].fr.sc; lb2=ky[l].sc.fr; rb2=ky[l].sc.sc; w=(rb-lb-(crb-clb))*(rb2-lb2+1); if(!vtd[l]) { dfs(l); } dp[x]=max(dp[x],dp[l]+w); } lb=ky[x].fr.fr; rb=ky[x].fr.sc; lb2=ky[x].sc.fr; rb2=ky[x].sc.sc; z=max(z,dp[x]+(rb-lb+1)*(rb2-lb2+1)); } int biggest_stadium(int on,vector<vector<int>> oa) { int i,j,ii,u,k,l,sz; n=on; for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { a[i][j]=oa[i-1][j-1]; } for(k=i;k>1;k/=2,lg2[i]++); } for(ii=0;ii<2;ii++) { u=!ii*2-1; for(i=1;i<=n;i++) { ht[i]=0; } for(i=1+(n-1)*ii;i&&i<=n;i+=u) { for(j=1;j<=n;j++) { ht[j]=(ht[j]+1)*!a[i][j]; } spbd(ii,i); } } for(i=1;i<=n*n*2;i++) { dsu[i]=i; } for(ii=0;ii<2;ii++) { u=!ii*2-1; for(i=1+(n-1)*ii;i&&i<=n;i+=u) { dnc(ii,i,1,n); } } for(i=1;i<=n*n*2;i++) { if(fd(i)!=i) { sz=al[i].size(); for(j=0;j<sz;j++) { l=al[i][j]; al[fd(i)].push_back(l); } } } for(i=1;i<=n*n*2;i++) { if(ky[i].fr.fr&&!vtd[i]) { dfs(i); } } return z; }

Compilation message (stderr)

soccer.cpp: In function 'void spbd(int, int)':
soccer.cpp:34:64: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   34 |    sp[xx][x][i][j]=min(sp[xx][x][i-1][j],sp[xx][x][i-1][j+(1<<i-1)]);
      |                                                               ~^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...