Submission #230903

#	Time	Username	Problem	Language	Result	Execution time	Memory
230903		frodakcin	Virus Experiment (JOI19_virus)	C++11	0 / 100	6 ms	896 KiB

virus

#include <cstdio>
#include <cassert>
#include <stack>
#include <algorithm>

template<typename T> bool ckmax(T& a, T b) {return a<b?a=b,1:0;}
template<typename T> bool ckmin(T& a, T b) {return b<a?a=b,1:0;}

//id = x*C+y
const int MN=6.4e3+10, MM=1e3+10, dx[]={-1,0,1,0}, dy[]={0,1,0,-1};
const char dir[]="NESW";
const int INF=1e6;

int M, R, C, a[MN], c[MN], cc=1, t[16], d[MN], l[MN], ctr, msz=MN, num, p[MN], r[MN];
bool u[MN], v[MN], out[MN];
char b[MM*2];

std::stack<int> st;
int find(int n) {return p[n]?p[n]=find(p[n]):n;}
bool merge(int a, int b)
{
	a=find(a), b=find(b);
	if(a==b) return 0;
	if(r[a]<r[b]) std::swap(a, b);
	p[b]=a,r[a]+=r[a]==r[b],r[b]=-1;
	return 1;
}
bool inf(int n, int x, int y)//[infect]
{
	if(!a[x*C+y]) return 0;
	n=find(n);
	int v=0;
	if(y+1<C && n==find(x*C+y+1)) v|=2;
	if(x+1<R && n==find(x*C+C+y)) v|=4;
	if(y && n==find(x*C+y-1)) v|=8;
	if(x && n==find(x*C-C+y)) v|=1;
	return t[v]>=a[x*C+y];
}
void dfs(int x, int y)
{
	assert(0 <= x && x < R);
	assert(0 <= y && y < C);
	int id=x*C+y;
	assert(!v[id]);
	st.push(id);
	u[id]=v[id]=1;
	l[id]=d[id]=ctr++;
	for(int z=0xf,j,nx,ny,nid;z;)
	{
		for(j=0;j<4;++j)
			if(z>>j&1)
			{
				z^=1<<j;
				nx=x+dx[j],ny=y+dy[j];
				if(nx < 0 || R <= nx || ny < 0 || C <= ny)
					continue;
				if(inf(id, nx, ny))
					break;
				else
					z|=1<<j;
			}
		if(j==4) break;
		nid=nx*C+ny;
		if(u[nid])
			ckmin(l[id], d[nid]), merge(id, nid);
		else if(v[nid])
			merge(id, nid), out[id]=1;
		else
		{
			dfs(nx, ny);
			ckmin(l[id], l[nid]);
			if(l[nid] > d[id])
				out[id]=1;
			else
				ckmin(l[id], l[nid]);
			merge(id, nid);
		}
	}
	if(l[id]==d[id])
	{
		bool good=1;
		int sz=0;
		for(int x;;)
		{
			x=st.top(); st.pop();
			c[x]=cc;
			u[x]=0;
			if(out[x])
				good=0;
			++sz;
			if(x==id) break;
		}
		++cc;
		if(good)
		{
			if(ckmin(msz, sz))
				msz=sz, num=sz;
			else if(sz==msz)
				num+=sz;
		}
	}
}
int main(void)
{
	scanf("%d%d%d", &M, &R, &C);
	scanf(" %s", b);
	for(int i=0;i<M;++i)
	{
		for(int j=0;j<4;++j)
			if(b[i]==dir[j])
			{
				b[i]=j;
				continue;
			}
		b[i+M]=b[i];
	}
	for(int i=0, c;i<16;++i)
	{
		c=0;
		for(int j=0;j<M*2;++j)
		{
			if(i>>b[j]&1)
				++c;
			else
				ckmax(t[i], c), c=0;
		}
		assert(c < M || c == 2*M);
		if(c==2*M)
			t[i]=INF;
	}
	for(int i=0;i<R*C;++i)
		scanf("%d", a+i);
	for(int i=0;i<R*C;++i)
		if(a[i]&&!v[i])
			dfs(i/C, i%C);
	printf("%d\n%d\n", msz, num);
	//for(int i=0;i<R*C;++i) printf("%2d%c", c[i], " \n"[!((i+1)%C)]);
	return 0;
}

Compilation message (stderr)

virus.cpp: In function 'int main()':
virus.cpp:105:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &M, &R, &C);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
virus.cpp:106:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf(" %s", b);
  ~~~~~^~~~~~~~~~
virus.cpp:132:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", a+i);
   ~~~~~^~~~~~~~~~~

• Subtask 1: 0 / 14
• Subtask 2: 0 / 6
• Subtask 3: 0 / 80