제출 #863128

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
863128		Pyqe	Soccer Stadium (IOI23_soccer)	C++17	100 / 100	2233 ms	1037972 KiB

soccer

#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][6][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*2<=n;i++)
	{
		for(j=1;j<=n-(1<<i*2)+1;j++)
		{
			sp[xx][x][i][j]=min({sp[xx][x][i-1][j],sp[xx][x][i-1][j+(1<<(i-1)*2)],sp[xx][x][i-1][j+(1<<(i-1)*2)*2],sp[xx][x][i-1][j+(1<<(i-1)*2)*3]});
		}
	}
}

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][min(lb+(1<<e*2),rb-(1<<e*2)+1)],sp[xx][x][e][min(lb+(1<<e*2)*2,rb-(1<<e*2)+1)],sp[xx][x][e][rb-(1<<e*2)+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;k/=4,lg2[i]++);
		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;
}

• Subtask 0: 0 / 0
• Subtask 1: 6 / 6
• Subtask 2: 8 / 8
• Subtask 3: 22 / 22
• Subtask 4: 18 / 18
• Subtask 5: 16 / 16
• Subtask 6: 30 / 30