Submission #147449

#	Time	Username	Problem	Language	Result	Execution time	Memory
147449		username	Virus Experiment (JOI19_virus)	C++14	100 / 100	407 ms	19176 KiB

virus

#pragma GCC optimize("O3")
#define MIN(x,y) (x=min(x,(y)))
#define MAX(x,y) (x=max(x,(y)))
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
#define REP(i,j,k) for(register int i=(j);i<(k);++i)
#define pb push_back
#define f first
#define s second
#define endl '\n'
#define IOS cin.tie(0),cout.tie(0),ios_base::sync_with_stdio(false)

const int maxm=2e5+9,maxr=809,maxn=maxr*maxr,inf=1e9,dx[4]={1,0,0,-1},dy[4]={0,-1,1,0};
int m,n,r,c,cl=0,u[maxn],t[1<<4],fa[maxn],sz[maxn],p[maxn],fin[maxn],vis[maxn];
string d;
map<char,int>mp;

void init(int k){REP(i,0,k)fa[i]=i,sz[i]=1;}

int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}

void unite(int x,int y){
	if(sz[x]>sz[y])swap(x,y);
	fa[x]=y,sz[y]+=sz[x];
}

bool ok(pii x){return 0<=x.f&&x.f<r&&0<=x.s&&x.s<c;}

main(){
	IOS;
	mp['N']=0,mp['E']=1,mp['W']=2,mp['S']=3;
	cin>>m>>r>>c,n=r*c;
	cin>>d;
	REP(i,0,r)REP(j,0,c)cin>>u[i*c+j];
	d+=d,m+=m;
	REP(i,0,1<<4){
		int le,ri=0;
		while(ri<m){
			le=ri;
			while(ri<m&&((i>>mp[d[ri]])&1))++ri;
			MAX(t[i],ri-le);
			++ri;
		}
		if(t[i]==m)t[i]=inf;
	}
	init(n);
	REP(i,0,n)p[i]=i;
	pii res={n,0};
	for(int z=1;z<=n;z<<=1){
		REP(i,0,r){
			REP(j,0,c){
				++cl;
				int id=i*c+j,b=find(id);
				if(u[id]&&p[b]==id&&sz[b]<2*z&&!fin[p[b]]){
					assert(sz[b]>=z);
					queue<pii>q;
					q.push({i,j}),vis[id]=cl;
					int cnt=0;
					while(!q.empty()){
						pii h=q.front();q.pop();
						++cnt;
						REP(k,0,4){
							pii nh={h.f+dx[k],h.s+dy[k]};
							int nid=nh.f*c+nh.s;
							if(ok(nh)&&u[nid]&&vis[nid]!=cl){
								int msk=0;
								REP(l,0,4){
									pii rh={nh.f+dx[l],nh.s+dy[l]};
									if(ok(rh)&&vis[rh.f*c+rh.s]==cl)msk|=1<<3-l;
								}
								if(u[nid]<=t[msk]){
									vis[nid]=cl;
									q.push(nh);
									int nb=find(nid);
									if(b!=nb){
										p[b]=p[nb];
										unite(b,nb);
										goto bot;
									}
								}
							}	
						}
					}
					fin[id]=1;
					if(cnt==res.f)res.s+=cnt;
					else if(cnt<res.f)res={cnt,cnt};
				}
				bot:;
			}
		}
	}
	cout<<res.f<<" "<<res.s<<endl;
}

Compilation message (stderr)

virus.cpp:30:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^
virus.cpp: In function 'int main()':
virus.cpp:70:51: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
          if(ok(rh)&&vis[rh.f*c+rh.s]==cl)msk|=1<<3-l;
                                                  ~^~

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