Submission #294547

#	Time	Username	Problem	Language	Result	Execution time	Memory
294547		Pyqe	I want to be the very best too! (NOI17_pokemonmaster)	C++14	27 / 100	5070 ms	15872 KiB

pokemonmaster

#include <bits/stdc++.h>

using namespace std;

#define mp make_pair
#define fr first
#define sc second

long long n,m,nn=0,wg[50069],aa[50069],dsu[50069],a[50069],pst[50069],sbt[50069],pr[50069][16],bl[50069],ls[50069],vy[4]={-1,0,1,0},vx[4]={0,1,0,-1};
pair<long long,long long> as[50069];
bitset<50069> vtd;
vector<long long> al[50069];

long long fd(long long x)
{
	if(dsu[x]!=x)
	{
		dsu[x]=fd(dsu[x]);
	}
	return dsu[x];
}

void dfs(long long x)
{
	long long i,j,sz=al[x].size(),l;
	
	nn++;
	a[nn]=aa[x];
	pst[x]=nn;
	sbt[x]=1;
	for(i=0;i<sz;i++)
	{
		l=al[x][i];
		pr[l][0]=x;
		for(j=1;j-1<bl[pr[l][j-1]];j++)
		{
			pr[l][j]=pr[pr[l][j-1]][j-1];
		}
		bl[l]=j;
		dfs(l);
		sbt[x]+=sbt[l];
	}
}

int main()
{
	long long t,rr,i,j,im,ky,p,y,x,w,yy,xx,pp,z;
	
	scanf("%lld%lld%lld",&n,&m,&t);
	for(i=0;i<n;i++)
	{
		for(j=0;j<m;j++)
		{
			p=i*m+j;
			scanf("%lld",wg+p);
			as[p]={wg[p],p};
		}
	}
	sort(as,as+n*m);
	for(i=0;i<n;i++)
	{
		for(j=0;j<m;j++)
		{
			p=i*m+j;
			scanf("%lld",aa+p);
		}
	}
	for(i=0;i<n*m;i++)
	{
		p=as[i].sc;
		y=p/m;
		x=p%m;
		vtd[p]=1;
		dsu[p]=p;
		for(im=0;im<4;im++)
		{
			yy=y+vy[im];
			xx=x+vx[im];
			pp=yy*m+xx;
			if(yy>=0&&xx>=0&&yy<n&&xx<m&&vtd[pp]&&fd(pp)!=p)
			{
				al[p].push_back(fd(pp));
				dsu[fd(pp)]=p;
			}
		}
	}
	dfs(p);
	for(rr=1;rr<=t;rr++)
	{
		scanf("%lld%lld%lld%lld",&ky,&x,&y,&w);
		y--;
		x--;
		p=y*m+x;
		if(ky==1)
		{
			a[pst[p]]=w;
		}
		else if(wg[p]>w)
		{
			printf("0\n");
		}
		else
		{
			for(i=15;i+1;i--)
			{
				if(i<bl[p]&&wg[pr[p][i]]<=w)
				{
					p=pr[p][i];
				}
			}
			z=0;
			for(i=pst[p];i<=pst[p]+sbt[p]-1;i++)
			{
				z+=ls[a[i]]<rr;
				ls[a[i]]=rr;
			}
			printf("%lld\n",z);
		}
	}
}

Compilation message (stderr)

pokemonmaster.cpp: In function 'int main()':
pokemonmaster.cpp:49:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   49 |  scanf("%lld%lld%lld",&n,&m,&t);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
pokemonmaster.cpp:55:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   55 |    scanf("%lld",wg+p);
      |    ~~~~~^~~~~~~~~~~~~
pokemonmaster.cpp:65:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   65 |    scanf("%lld",aa+p);
      |    ~~~~~^~~~~~~~~~~~~
pokemonmaster.cpp:90:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   90 |   scanf("%lld%lld%lld%lld",&ky,&x,&y,&w);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
pokemonmaster.cpp:87:5: warning: 'p' may be used uninitialized in this function [-Wmaybe-uninitialized]
   87 |  dfs(p);
      |  ~~~^~~

• Subtask 1: 11 / 11
• Subtask 2: 16 / 16
• Subtask 3: 0 / 20
• Subtask 4: 0 / 24
• Subtask 5: 0 / 29