Submission #231546

#	Time	Username	Problem	Language	Result	Execution time	Memory
231546		frodakcin	Virus Experiment (JOI19_virus)	C++11	100 / 100	781 ms	150624 KiB

virus

#include <cstdio>
#include <cstring>
#include <cassert>
#include <vector>
#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.4e5+10, MM=1e5+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::vector<int> adj[MN], nb[MN], nil;
std::stack<int> st;
 
int find(int n) {return ~p[n]?p[n]=find(p[n]):n;}
std::vector<int> &merge(int a, int b)
{
	a=find(a), b=find(b);
	if(a==b) return nil;
	if(r[a]<r[b]) std::swap(a, b);
	p[b]=a,r[a]+=r[a]==r[b],r[b]=-1;
	if(nb[a].size() < nb[b].size()) std::swap(nb[a], nb[b]);
	for(auto x:nb[b]) nb[a].push_back(x);
	return nb[b];
}
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++;
	int nx, ny, nid;
	for(int i=0;i<4;++i)
	{
		nx=x+dx[i],ny=y+dy[i];
		if(nx < 0 || R <= nx || ny < 0 || C <= ny)
			continue;
		adj[id].push_back(nx*C+ny);
	}
	for(;!adj[id].empty();)
	{
		nid=adj[id].back(); adj[id].pop_back();
		nx=nid/C, ny=nid-nx*C;
 
		if(!inf(id, nx, ny)) continue;//time bottleneck here
 
		if(u[nid])
			ckmin(l[id], d[nid]);
		else if(v[nid])
			out[id]=1;
		else
		{
			dfs(nx, ny);
			if(l[nid] == d[nid])
				out[id]=1;
			else
				ckmin(l[id], l[nid]);
		}
		std::vector<int> &on = merge(id, nid);
		for(;!on.empty();on.pop_back())
		{
			int xv=on.back()/C, yv=on.back()-xv*C;
			if(xv) adj[id].push_back((xv-1)*C+yv);
			if(yv) adj[id].push_back(xv*C+yv-1);
			if(xv+1<R) adj[id].push_back((xv+1)*C+yv);
			if(yv+1<C) adj[id].push_back(xv*C+yv+1);
		}
	}
	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))
				num=sz;
			else if(sz==msz)
				num+=sz;
		}
	}
}
int main(void)
{
	memset(p, -1, sizeof p);
	scanf("%d%d%d", &M, &R, &C);
	for(int i=0;i<R*C;++i) nb[i].push_back(i);
	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;
				break;
			}
		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;
		}
		ckmax(t[i], c);
		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), assert(st.empty());
	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:117: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:119:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf(" %s", b);
  ~~~~~^~~~~~~~~~
virus.cpp:146:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", a+i);
   ~~~~~^~~~~~~~~~~

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