oj.uz

답안 #174562

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
174562 2020-01-06T12:31:21 Z Bruteforceman 바이러스 (JOI19_virus) C++11
100 / 100
 1680 ms 123896 KB 
#include <bits/stdc++.h>
using namespace std;
#define count cnt
string s;
const int dx[] = {0, 0, 1, -1};
const int dy[] = {1, -1, 0, 0};
const char dir[] = {'E', 'W', 'S', 'N'};
 
typedef pair <int, int> pii;
 
bool done[805][805];
bool vis[805][805];
bool infect[1 << 4][805][805];
int a[805][805];
int ans[805][805];
int optimal;
int count;
int r, c;
unordered_set <int> reachable[805][805];
int par[801 * 801];

int root(int x) {
	if(par[x] == x) return x;
	return par[x] = root(par[x]);
}
void join(int x, int y) {
	x = root(x);
	y = root(y);
	if(x != y) {
		par[x] = y;
	}
}
inline int convert(int i, int j) {
	return j + i * c;
}
inline bool inside(int x, int y) {
	return (0 <= x && x < r) && (0 <= y && y < c);
}
inline int check(int i, int j) {
	int mask = 0;
	for(int p = 0; p < 4; p++) {
		int x = i + dx[p];
		int y = j + dy[p];
		if(inside(x, y) && vis[x][y]) {
			mask |= 1 << p;
		}
	}
	return infect[mask][i][j];
}
void solve(int x, int y) {
	queue <pii> Q;
	vector <pii> reach; 
	vis[x][y] = true;
	Q.push(pii(x, y));
	bool bad = false;
	while(!Q.empty()) {
		int p = Q.front().first;
		int q = Q.front().second;
		Q.pop();
		reach.push_back(pii(p, q));
		if(bad) continue;
		for(int i = 0; i < 4; i++) {
			int nx = p + dx[i];
			int ny = q + dy[i];
			if(!inside(nx, ny) || vis[nx][ny]) continue;
			if(check(nx, ny)) {
				int anc = root(convert(nx, ny));
				nx = (anc / c);
				ny = (anc % c);
				if(done[nx][ny]) {
					if(ans[nx][ny] == optimal && reachable[nx][ny].find(convert(x, y)) != reachable[nx][ny].end()) {
						++count;
						ans[x][y] = ans[nx][ny];
						join(convert(x, y), anc);
					} else {
						ans[x][y] = INT_MAX;
					}
					bad = true;
					break;
				}
				Q.push(pii(nx, ny));
				vis[nx][ny] = true;
			}
		}
	}
	for(auto i : reach) {
		vis[i.first][i.second] = false;
	}
	done[x][y] = true;
	if(!bad) {
		ans[x][y] = reach.size();
		if(optimal == ans[x][y]) {
			++count;
		} else if (ans[x][y] < optimal) {
			optimal = ans[x][y];
			count = 1;
		}
  		reachable[x][y].max_load_factor(0.25); //updated !
		for(auto i : reach) {
			reachable[x][y].insert(convert(i.first, i.second));
		}
	}
}
int main() {
	ios_base :: sync_with_stdio(false);
	cin.tie(0);
	
	int n;
	cin >> n >> r >> c;
	cin >> s;
	s = s + s;
	for(int x = 0; x < r; x++) {
		for(int y = 0; y < c; y++) {
			cin >> a[x][y];
		}
	}
	for(int i = 0; i < (1 << 4); i++) {
		set <char> allow;
		for(int j = 0; j < 4; j++) {
			if((i >> j) & 1) {
				allow.insert(dir[j]);
			}
		}
		int opt = 0;
		int cur = 0;
		for(int j = 0; j < (int) s.size(); j++) {
			int num;
			if(allow.find(s[j]) == allow.end()) {
				num = 0;
			} else num = 1;
			if(num == 0) cur = 0;
			else {
				cur += 1;
				opt = max(opt, cur);
			}
		}
		if(opt == n + n) {
			opt = INT_MAX;
		} 
		for(int x = 0; x < r; x++) {
			for(int y = 0; y < c; y++) {
				if(a[x][y] > 0 && a[x][y] <= opt) {
					infect[i][x][y] = true;
				}
			}
		}
	}
	optimal = INT_MAX;
	count = 0;
	vector <pii> order;
	for(int i = 0; i < r; i++) {
		for(int j = 0; j < c; j++) {
			par[convert(i, j)] = convert(i, j); 
			order.push_back(pii(i, j));
		}
	}
	random_shuffle(order.begin(), order.end());
	for(auto pt : order) {
		if(a[pt.first][pt.second] == 0) continue;
		solve(pt.first, pt.second);
	}
	cout << optimal << endl;
	cout << count << endl;
	return 0;
}

Subtask #1
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 42 ms 36344 KB Output is correct
2 Correct 845 ms 115396 KB Output is correct
3 Correct 890 ms 107208 KB Output is correct
4 Correct 899 ms 103212 KB Output is correct
5 Correct 797 ms 115700 KB Output is correct
6 Correct 48 ms 48376 KB Output is correct
7 Correct 1198 ms 98644 KB Output is correct
8 Correct 317 ms 67912 KB Output is correct

Subtask #2
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 37 ms 36092 KB Output is correct
2 Correct 46 ms 36508 KB Output is correct
3 Correct 75 ms 36532 KB Output is correct
4 Correct 45 ms 36508 KB Output is correct
5 Correct 78 ms 36380 KB Output is correct
6 Correct 73 ms 37536 KB Output is correct
7 Correct 38 ms 36088 KB Output is correct
8 Correct 71 ms 37528 KB Output is correct
9 Correct 45 ms 37112 KB Output is correct
10 Correct 46 ms 36508 KB Output is correct
11 Correct 40 ms 36984 KB Output is correct
12 Correct 41 ms 37240 KB Output is correct
13 Correct 69 ms 37532 KB Output is correct
14 Correct 69 ms 37432 KB Output is correct
15 Correct 69 ms 37408 KB Output is correct
16 Correct 77 ms 37580 KB Output is correct
17 Correct 56 ms 37240 KB Output is correct
18 Correct 42 ms 37144 KB Output is correct
19 Correct 72 ms 36984 KB Output is correct

Subtask #3
80.0 / 80.0

# 결과 실행 시간 메모리 Grader output
1 Correct 42 ms 36344 KB Output is correct
2 Correct 845 ms 115396 KB Output is correct
3 Correct 890 ms 107208 KB Output is correct
4 Correct 899 ms 103212 KB Output is correct
5 Correct 797 ms 115700 KB Output is correct
6 Correct 48 ms 48376 KB Output is correct
7 Correct 1198 ms 98644 KB Output is correct
8 Correct 317 ms 67912 KB Output is correct
9 Correct 37 ms 36092 KB Output is correct
10 Correct 46 ms 36508 KB Output is correct
11 Correct 75 ms 36532 KB Output is correct
12 Correct 45 ms 36508 KB Output is correct
13 Correct 78 ms 36380 KB Output is correct
14 Correct 73 ms 37536 KB Output is correct
15 Correct 38 ms 36088 KB Output is correct
16 Correct 71 ms 37528 KB Output is correct
17 Correct 45 ms 37112 KB Output is correct
18 Correct 46 ms 36508 KB Output is correct
19 Correct 40 ms 36984 KB Output is correct
20 Correct 41 ms 37240 KB Output is correct
21 Correct 69 ms 37532 KB Output is correct
22 Correct 69 ms 37432 KB Output is correct
23 Correct 69 ms 37408 KB Output is correct
24 Correct 77 ms 37580 KB Output is correct
25 Correct 56 ms 37240 KB Output is correct
26 Correct 42 ms 37144 KB Output is correct
27 Correct 72 ms 36984 KB Output is correct
28 Correct 1596 ms 120104 KB Output is correct
29 Correct 1416 ms 120516 KB Output is correct
30 Correct 1086 ms 87472 KB Output is correct
31 Correct 1381 ms 84508 KB Output is correct
32 Correct 1365 ms 112744 KB Output is correct
33 Correct 1016 ms 112600 KB Output is correct
34 Correct 1680 ms 122288 KB Output is correct
35 Correct 1229 ms 113960 KB Output is correct
36 Correct 1520 ms 105428 KB Output is correct
37 Correct 1669 ms 107684 KB Output is correct
38 Correct 1559 ms 120080 KB Output is correct
39 Correct 1212 ms 117768 KB Output is correct
40 Correct 1236 ms 108780 KB Output is correct
41 Correct 1014 ms 104272 KB Output is correct
42 Correct 1384 ms 96680 KB Output is correct
43 Correct 1324 ms 123896 KB Output is correct
44 Correct 329 ms 68364 KB Output is correct