Submission #154256

#	Time	Username	Problem	Language	Result	Execution time	Memory
154256		ryansee	Virus Experiment (JOI19_virus)	C++14	100 / 100	360 ms	22916 KiB

virus

#include "bits/stdc++.h"
using namespace std;

#define FAST ios_base::sync_with_stdio(false); cin.tie(0);
#define pb push_back
#define eb emplace_back
#define ins insert
#define ph push
#define f first
#define s second
#define cbr cerr << "hi\n"
#define mmst(x, v) memset((x), v, sizeof ((x)))
#define siz(x) ((ll)x.size())
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
#define btinpct(x) __builtin_popcountll((x))
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());    //can be used by calling rng() or shuffle(A, A+n, rng)
inline long long rand(long long x, long long y) { return (rng() % (y+1-x)) + x; } //inclusivesss
string to_string(char c) {string s(1,c);return s;} template<typename T> inline T gcd(T a,T b){if(a>b)swap(a,b);if(a==0)return b;return gcd(b%a,a);}

#define ll /*long long*/ int 
#define ld long double
#define FOR(ii, ss, ee) for(ll ii = (ss); ii <= (ll)(ee); ++ii)
#define DEC(ii, ss, ee) for(ll ii = (ss); ii >= (ll)(ee); --ii)
typedef pair <ll, ll> pi; typedef pair <ll, pi> spi; typedef pair <pi, pi> dpi;

#define LLINF ((long long) 1e18)//1234567890987654321
#define INF 1234567890ll
// #define cerr if(0)cout
#define MAXN (640006)
ll k, n, m, grid[801][801];
string S;
int dx[]={1,-1,0,0};
int dy[]={0,0,1,-1};
int add[]={1<<2,1<<0,1<<1,1<<3};
// N,E,S,W
int gm(char ch) {
	if(ch == 'N') return 1<<0;
	if(ch == 'E') return 1<<1;
	if(ch == 'S') return 1<<2;
	return 1<<3;
}
ll best[1<<4];
ll ans[801][801];
ll hsh(ll x,ll y){return x*m + y; }
struct ufds_ {
	int p[MAXN], sz[MAXN];
	ufds_ () { FOR(i,0,MAXN-1) p[i]=i, sz[i]=1; }
	void merge(ll x,ll y){ 
		x=find(x), y=find(y); 
		if(x==y)return; 
		assert(~sz[x] && ~sz[y]);
		sz[y] += sz[x], sz[x]=0; 
		p[x]=y; 
	}
	ll find(ll x) { return (p[x]==x)?x:p[x]=find(p[x]); }
	bool same(ll a,ll b){return find(a)==find(b);}
} ufds;
ll vis[801][801];
ll vis_cnt;
void join(ll x,ll y){
	x=ufds.find(x), y=ufds.find(y);
	assert(x!=y);
	if(ufds.sz[y] == -1) {
		ufds.sz[x] = -1;
		return;
	}
	ufds.merge(x,y);
}
bool bfs(ll x,ll y){
	queue<pi> q; vector<pi> all;
	ll num=0;
	++ vis_cnt;
	vis[x][y]=vis_cnt;
	q.emplace(x, y); all.eb(x,y);
	while(q.size()) {
		ll x=q.front().f, y=q.front().s;
		q.pop();
		++ num;
		FOR(i,0,3) {
			ll nx=x+dx[i];
			ll ny=y+dy[i];
			if(nx < 0 || ny < 0 || nx >= n || ny >= m || grid[nx][ny] == 0 || vis[nx][ny] == vis_cnt) continue;
			ll mask=0;
			FOR(j,0,3) {
				ll resx=nx+dx[j];
				ll resy=ny+dy[j];
				if(resx < 0 || resy < 0 || resx >= n || resy >= m || vis[resx][resy] != vis_cnt) continue;
				 mask |= add[j];
			}
			// if(x==1&&y==0 && nx==0&&ny==0) cerr<<mask<<": "<<best[mask]<<"\n";
			// cerr<<mask<<" "<<best[mask]<<"\n";
			if(grid[nx][ny] > best[mask]) continue;
			if(ufds.same(hsh(x,y), hsh(nx,ny))) {
				vis[nx][ny]=vis_cnt;
				q.emplace(nx,ny); all.eb(nx,ny);
			} else {
				join(hsh(x,y), hsh(nx,ny));
				return 1;
			}
		}
	}
	// cerr<<x<<' '<<y<<' '<<num<<"\n";
	assert(ufds.find(hsh(x,y)) == hsh(x,y));
	ufds.sz[hsh(x, y)] = -1;
	for(auto i:all) ans[i.f][i.s] = num;
	return 0;
}
int main()
{
	FAST
	cin>>k>>n>>m>>S;
	ll mx=0;
	FOR(i,0,n-1) FOR(j,0,m-1) cin>>grid[i][j],mx=max(mx,grid[i][j]);
	string tmp=S;
	while(S.size() <= mx) {
		S+=tmp;
	} S+=tmp; assert(S.size() <= (int)3e5);
	// cerr<<S<<"\n";
	FOR(i,0,(1<<4)-1) {
		ll p=0, mx=0;
		FOR(j,0,siz(S)-1) {
			if(gm(S[j]) & i) ++ p;
			else p=0;
			mx=max(mx, p);
		}
		// cerr<<i<<' '<<mx<<'\n';
		best[i] = mx;
	}
	FOR(i,0,n-1) FOR(j,0,m-1) ans[i][j]=1e9;
	while(1) {
		bool have=0;
		FOR(i,0,n-1) FOR(j,0,m-1) if(grid[i][j] && ufds.find(hsh(i,j))==hsh(i,j) && ~ufds.sz[hsh(i,j)]) {
			have |= bfs(i, j);
		}
		if(!have) break;
	}
	pi anss=pi(1e9,0);
	FOR(i,0,n-1) FOR(j,0,m-1) if(ans[i][j] != 1e9) {
		if(ans[i][j] < anss.f) anss.f = ans[i][j], anss.s = 1;
		else if(ans[i][j] == anss.f) ++ anss.s;
	}
	cout<<anss.f<<"\n"<<anss.s<<"\n";
}

Compilation message (stderr)

virus.cpp: In function 'int main()':
virus.cpp:117:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(S.size() <= mx) {
        ~~~~~~~~~^~~~~

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