Submission #555040

#	Time	Username	Problem	Language	Result	Execution time	Memory
555040		czhang2718	Virus Experiment (JOI19_virus)	C++17	0 / 100	285 ms	132916 KiB

virus

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

#define rep(i,a,b) for(int i=a; i<=b; i++)
typedef vector<int> vi;
typedef pair<int, int> pii;
#define pb push_back
#define all(x) x.begin(), x.end()
#define sz(x) (int) x.size()
#define f first
#define s second
#define nl '\n'

const int N=801;
int m, r,c ;
int u[N][N];
int dx[]={1,0,-1,0};
int dy[]={0,-1,0,1};
char dir[]={'S','W','N','E'};
map<char,int> mp={{'S',0},{'W',1},{'N',2},{'E',3}};
string D;
int mx[1<<4];
set<int> adj[N*N];
vi nodes[N*N];
int par[N*N];
bool vis[N*N];
stack<int> st;
bool seen[N*N];
map<pii, bool> have;
int rec;
bool dead[N*N];

int h(int i, int j){
	return c*(i-1)+j;
}

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

void join(int x, int y){
	int a=find(x);
	int b=find(y);
	if(a==b) return;
	if(sz(nodes[a])<sz(nodes[b])) swap(a,b);
	par[b]=a;
	vector<pii> todo;
	for(int u:nodes[b]){
		have[{a, u}]=1;
		int x=(u-1)/c+1, y=(u-1)%c+1;
		rep(k,0,3) todo.pb({x+dx[k], y+dy[k]});
		nodes[a].pb(u);
	}
	for(int u:adj[b]) if(find(u)!=a) adj[a].insert(u);
	// for(int x:nodes[a]) cout << "have " << a << " " << x << nl;
	for(pii p:todo){
		int mask=0;
		int x=p.f, y=p.s;
		if(!x || x>r || !y || y>c || !u[x][y]) continue;
		rep(k,0,3){
			int nx=x+dx[k], ny=y+dy[k];
			if(!nx || nx>r || !ny || ny>c || !u[nx][ny]) continue;
			// cout << "reach " << nx << " " << ny << " " << have[{a, h(nx,ny)}] << nl;
			if(have[{a, h(nx,ny)}]) mask^=(1<<k);
		}
		// cout << "try " << x << " " << y << " get " << mask << " vs " << u[x][y] << nl;
		if(mx[mask]>=u[x][y]){
			// cout << "adj " << a << " add " << h(x,y) << nl;
			adj[a].insert(h(x,y));
		}
	}
}

void dfs(int x){
	x=find(x);
	vis[x]=seen[x]=1;
	st.push(x);
	vi g;
	for(int u:adj[x]) g.pb(find(u));
	sort(all(g));
	g.erase(unique(all(g)), g.end());
	for(int k:g){
		int kk=find(k);
		if(kk==x) continue;
		if(seen[kk]){
			// cout << "cycle " << kk << " ";
			while(st.top()!=kk){
				join(st.top(), x);
				// cout << st.top() << " ";
				seen[st.top()]=0;
				st.pop();
				assert(sz(st));
			}
			// cout << nl;
			assert(sz(st));
			join(st.top(), x);
			seen[kk]=0;
			st.pop();
			seen[x]=0;
			x=find(x);
			dfs(x);
			return;
		}
		if(vis[kk]){
			// cout << x << "->" << kk << nl;
			// cout << x << " dead\n";
			dead[x]=1;
			break;
		}
		dfs(kk);
		if(!sz(st) || st.top()!=x) return;
	}
	seen[find(x)]=0;
	assert(sz(st));
	st.pop();
}

int main(){
	cin.tie(0)->sync_with_stdio(0);

	cin >> m >> r >> c >> D;
	rep(i,1,r) rep(j,1,c){
		cin >> u[i][j];
		nodes[h(i,j)]={h(i,j)};
		have[{h(i,j), h(i,j)}]=1;
		par[h(i,j)]=h(i,j);
	}

	for(int mask=0; mask<(1<<4); mask++){
		int cur=0;
		for(int i=0; i<2*m; i++){
			cur++;
			if(!(mask&(1<<mp[D[i%m]]))) cur=0;
			mx[mask]=max(mx[mask], cur);
		}
		// cout << "max " << mask << " " << mx[mask] << nl;
	}

	int cnt=0;
	rep(i,1,r){
		rep(j,1,c){
			if(!u[i][j]) continue;
			rep(k,0,3){
				int x=i+dx[k], y=j+dy[k];
				if(!x || x>r || !y || y>c || !u[x][y]) continue;
				if(mx[1<<((k+2)%4)]>=u[x][y]){
					// cout << i << "," << j << "-> " << x << "," << y << nl;
					adj[h(i,j)].insert(h(x,y));
				}
			}
			if(!sz(adj[h(i,j)])){
				// cout << i << j << " bad\n";
				cnt++;
			}
		}
	}
	if(cnt){
		cout << "1\n" << cnt; return 0;
	}

	rep(i,1,r*c){
		if(!u[(i-1)/c+1][(i-1)%c+1]) continue;
		if(vis[find(i)]) continue;
		assert(find(i)==i);
		dfs(i);
	}

	set<int> s;
	rep(i,1,r*c){
		if(!u[(i-1)/c+1][(i-1)%c+1]) continue;
		s.insert(find(i));
	}

	pii ans={1e9,0};
	for(int c:s){
		// cout << "comp " << c << nl;
		if(dead[c]) continue;
		
		// for(int x:nodes[c]) cout << x << " ";
			// cout << nl;
		if(sz(nodes[c])<ans.f) ans={sz(nodes[c]), sz(nodes[c])};
		else ans.s+=sz(nodes[c]);
	}
	cout << ans.f << " " << ans.s;
}
// when did i become so sad?

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