Submission #448314

#	Time	Username	Problem	Language	Result	Execution time	Memory
448314		koioi.org-koosaga	바이러스 (JOI19_virus)	C++17	0 / 100	752 ms	262148 KiB

virus

#include <bits/stdc++.h>
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
using namespace std;
using lint = long long;
using pi = pair<int, int>;
const int MAXN = 808;
const int MAXV = 1300000;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

struct disj{
	int pa[MAXV];
	void init(){
		iota(pa, pa + MAXV, 0);
	}
	int find(int x){
		return pa[x] = (pa[x] == x ? x : find(pa[x]));
	}
	bool uni(int p, int q){
		p = find(p);
		q = find(q);
		if(p == q) return 0;
		pa[q] = p; return 1;
	}
}disj;

int n, m, dead[MAXN][MAXN], good[MAXV][16];

int V;
int idx[MAXN][MAXN];
int pa[MAXV], nxt[MAXV], sz[MAXV];
vector<pi> nei[MAXV];

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

int find_next(int x){
	for(auto &[p, q] : nei[x]){
		if(find(p) == x) continue;
		if(good[p][q]) return p;
	}
	return x;
}

void merge_to(int u, int v){
	u = find(u);
	if(u == v) return;
	pa[u] = v;
	sz[v] += sz[u];
	vector<pi> total;
	for(auto &i : nei[u]) total.push_back(i);
	for(auto &i : nei[v]) total.push_back(i);
	nei[u].clear(); nei[v].clear();
	sort(all(total));
	for(int i = 0; i < sz(total); ){
		int e = i;
		int msk = 0;
		while(e < sz(total) && total[i].first == total[e].first){
			msk |= total[e++].second;
		}
		nei[v].emplace_back(total[i].first, msk);
		i = e;
	}
}

void solve(){
	auto ok = [&](int x, int y){
		return x >= 0 && x < n && y >= 0 && y < m && !dead[x][y];
	};
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++){
			for(int k = 0; k < 4; k++){
				if(ok(i + dx[k], j + dy[k])){
					nei[idx[i][j]].emplace_back(idx[i + dx[k]][j + dy[k]], 1 << k);
				}
			}
		}
	}
	disj.init();
	iota(pa, pa + MAXV, 0);
	fill(sz, sz + V, 1);
	for(int i = 0; i < V; i++){
		nxt[i] = find_next(i);
	}
	int curV = V;
	for(int i = 0; i < V; i++){
		if(find(i) != i) continue;
		if(i == find(nxt[i])) continue;
		if(!disj.uni(i, nxt[i])){
			for(int j = find(nxt[i]); find(j) != find(V); j = find(nxt[j])){
				merge_to(j, V);
			}
			disj.uni(i, V);
			nxt[V] = find_next(V);
			V++;
		}
	}
	vector<int> ans(V);
	int dap = 1e9;
	int cnt = 0;
	for(int i = 0; i < curV; i++){
		int r = find(i);
		if(find(r) == find(nxt[r])){
			if(dap > sz[r]){
				dap = sz[r];
				cnt = 0;
			}
			if(dap == sz[r]) cnt++;
		}
	}
	printf("%d\n%d\n", dap, cnt);
}

char buf[200005];

int main(){
	int mp[256];
	mp['N'] = 0;
	mp['W'] = 1;
	mp['S'] = 2;
	mp['E'] = 3;
	int k;
	scanf("%d %d %d",&k,&n,&m);
	scanf("%s", buf);
	for(int i=0; i<k; i++){
		buf[i + k] = buf[i];
	}
	k <<= 1;
	int maxt[16] = {};
	for(int i=0; i<16; i++){
		int cnt = 0;
		for(int j=0; j<k; j++){
			if((i >> mp[buf[j]]) & 1){
				cnt++;
				maxt[i] = max(maxt[i], cnt);
			}
			else{
				cnt = 0;
			}
		}
		if(maxt[i] == k) maxt[i] = 1e9;
	}
	for(int i=0; i<n; i++){
		for(int j=0; j<m; j++){
			int x; scanf("%d",&x);
			if(x == 0){
				dead[i][j] = 1;
				continue;
			}
			idx[i][j] = V;
			for(int k=0; k<16; k++){
				if(x <= maxt[k]) good[V][k] = 1;
			}
			V++;
		}
	}
	solve();
}

Compilation message (stderr)

virus.cpp: In function 'int main()':
virus.cpp:135:21: warning: array subscript has type 'char' [-Wchar-subscripts]
  135 |    if((i >> mp[buf[j]]) & 1){
      |                ~~~~~^
virus.cpp:125:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  125 |  scanf("%d %d %d",&k,&n,&m);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~
virus.cpp:126:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  126 |  scanf("%s", buf);
      |  ~~~~~^~~~~~~~~~~
virus.cpp:147:16: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  147 |    int x; scanf("%d",&x);
      |           ~~~~~^~~~~~~~~

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